// michaekt o-2/** * @author Michael Thung (michaekt@ifi.uio.no) */import java.io.*;import java.util.*;/** * Hovedklasse */class Sudoku { public static void main(String[] args) { Sudoku sudoku = new Sudoku(); sudoku.programLoop(args); } public void programLoop(String[] args) { minIO innut = new minIO(); String[] brettInfo = null; // Sjekk om brukeren har oppgitt et filnavn, og kun ett. if (args.length == 0) { innut.skrivTekst("Vennligst oppgi en fil! (Syntaksen er: java Sudoku filnavn)"); System.exit(0); } else if (args.length > 1) { innut.skrivTekst("Vennligst oppgi kun ett filnavn. (Syntaksen er: java Sudoku filnavn"); System.exit(0); } // Les innhold fra oppgitt fil. if (args[0] != null) { File fil = new File(args[0]); brettInfo = innut.lesFil(fil).split(System.getProperty("line.separator")); } // henter størrelser. int antallRuter = Integer.parseInt(brettInfo[0]); int boksX = Integer.parseInt(brettInfo[1]); int boksY = Integer.parseInt(brettInfo[2]); int[][] brettData = new int[antallRuter][antallRuter]; // hent data fra selve brettet. for (int x = 0; x < brettInfo.length - 3; x++) { char[] r = brettInfo[x + 3].toCharArray(); for (int y = 0; y < r.length; y++) { // sørger for at vi får riktige tall inn. if (r[y] == '.') brettData[x][y] = 0; else if ((int) r[y] - '0' < 10) brettData[x][y] = (int) r[y] - '0'; else if (r[y] == '@') brettData[x][y] = 36; else brettData[x][y] = (int) r[y] - 55; } } Brett brett = new Brett(brettData, antallRuter, boksX, boksY); int antLosninger = brett.finnLosninger(); if (antLosninger == 0) innut.skrivTekst("Ingen løsninger!"); else if (antLosninger == 1) innut.skrivTekst("Én løsning!"); else innut.skrivTekst("Flere løsninger! Totalt: " + antLosninger); }}/** * Min egen IO-klasse */class minIO { /** Leser innhold fra fil. */ public String lesFil(File filNavn) { StringBuffer innhold = new StringBuffer(); BufferedReader input = null; // Forsøker å lese fra filen, og skriv ut eventuelle feilmeldinger om noe går galt. try { input = new BufferedReader(new FileReader(filNavn)); String line = null; // Legg inn data. while ((line = input.readLine()) != null) innhold.append(line + System.getProperty("line.separator")); } catch (FileNotFoundException e) { skrivTekst("Filen du oppga eksisterer ikke! Prøv på nytt."); } catch (IOException e) { skrivTekst("Noe gikk galt. Sjekk filen og prøv på nytt."); } finally { try { // pass på at vi får lukket filen. if (input != null) input.close(); } catch (IOException e) { skrivTekst("Noe gikk galt. Sjekk filen og prøv på nytt."); } } return innhold.toString(); } /** Skriver tekst til skjerm */ public void skrivTekst(String s) { System.out.println(s); }}/** * Tar for seg hvert hele brett */class Brett { private final int str; private final int boksX; private final int boksY; private Rute[][] ruter; private Rad[] rader; private Kolonne[] kolonner; private Boks[][] bokser; /** Initialiserer brettet */ Brett(int[][] data, int str, int boksX, int boksY) { this.str = str; this.boksX = boksX; this.boksY = boksY; rader = new Rad[str]; kolonner = new Kolonne[str]; bokser = new Boks[str/boksX][str/boksY]; ruter = new Rute[str][str]; // Loop for å opprette rader og kolonner. for (int x = 0; x < str; x++) { rader[x] = new Rad(); kolonner[x] = new Kolonne(); } // Oppretter bokser. for (int x = 0; x < str/boksX; x++) for (int y = 0; y < str/boksY; y++) bokser[x][y] = new Boks(); // Loop for å opprette ruter for (int x = 0; x < str; x++) { for (int y = 0; y < str; y++) { int v; if (data[x][y] == 0) v = 0; else v = data[x][y]; // Fyller brettet med ruter ruter[x][y] = new Rute(v, kolonner[x], rader[y], bokser[x / boksX][y / boksY], this); } } // Fyll inn ruter ved siden av seg selv korrekt. for (int y = 0; y < str; y++) { for (int x = 0; x < str - 1; x++) ruter[x][y].settNeste(ruter[x + 1][y]); // Sørg for at vi går til neste rad på slutten. if (y < str - 1) ruter[str - 1][y].settNeste(ruter[0][y + 1]); // Pass på at siste rute på brettet får nullpeker ved siden av seg. else ruter[str - 1][y].settNeste(null); } } /** Selve algoritmen for å finne løsninger */ public int finnLosninger() { ruter[0][0].provAlleSifferMegOgResten(str); return ruter[0][0].antallLosninger; } public void print() { for (int x = 0; x < ruter.length; x++) { for (int y = 0; y < ruter[x].length; y++) { System.out.print(ruter[x][y]); } System.out.println(); } }}/** * Tar seg av hver enkeltrute */class Rute { static int antallLosninger; private int ruteVerdi; private boolean erFast; private Rute nesteRute; private Kolonne egenKol; private Rad egenRad; private Boks egenBoks; private Brett pappa; /** Konstruktør */ Rute(int v, Kolonne k, Rad r, Boks b, Brett brett) { this.ruteVerdi = v; this.egenKol = k; this.egenRad = r; this.egenBoks = b; this.pappa = brett; if (v == 0) erFast = false; else erFast = true; k.leggTil(this); r.leggTil(this); b.leggTil(this); } /** Setter verdi til ruta */ public void settVerdi(int i) { ruteVerdi = i; } /** Henter verdi fra ruta */ public int hentVerdi() { return ruteVerdi; } /** Setter rutas neste rute */ public void settNeste(Rute r) { nesteRute = r; } /** Henter ruta ved siden av seg */ public Rute hentNeste() { return nesteRute; } /** Sjekker om vi er på siste rute */ public boolean harNeste() { if (nesteRute == null) return false; return true; } /** Algoritme for å sette siffer i rutene */ public void provAlleSifferMegOgResten(int str) { // sjekk om ruten er forhåndsutfylt if (!erFast) { // sjekk om vi kan sette et tall i ruta. for (int t = 1; t <= str; t++) { if (egenBoks.sjekkTall(t) && egenRad.sjekkTall(t) && egenKol.sjekkTall(t)) { // Sett tall og gå videre. settVerdi(t); // gå til neste. if (harNeste()) hentNeste().provAlleSifferMegOgResten(str); // øk antall løsninger. else { antallLosninger++; pappa.print(); } } // finn neste mulige løsning settVerdi(0); } } else { // gå til neste if (harNeste()) hentNeste().provAlleSifferMegOgResten(str); // øk antall løsninger. else antallLosninger++; } } /** toString-metode */ public String toString() { return String.valueOf(ruteVerdi); }}/** * Super-klasse for boks, kolonne og rad. */abstract class Underdel { ArrayList <Rute> ruter = new ArrayList<Rute>(); /** Legger til en rute i lista */ public void leggTil(Rute r) { ruter.add(r); } /** Sjekker om et tall er satt i lista */ public boolean sjekkTall(int i) { boolean ikkeSatt = true; for (int x = 0; x < ruter.size(); x++) { Rute r = (Rute) ruter.get(x); if (r.hentVerdi() == i) ikkeSatt = false; } return ikkeSatt; }}class Boks extends Underdel {}class Kolonne extends Underdel {}class Rad extends Underdel {}