// 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) { 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; } } /*for (int x=0; x < brettData.length; x++) { String test = ""; for (int y = 0; y < brettData[x].length; y++) { test += " " + String.valueOf(brettData[x][y]); } innut.skrivTekst(test); }*/ Brett brett = new Brett(brettData, antallRuter, boksX, boksY); brett.finnLosninger(); }}/** * 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; 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(); } 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, kolonner og bokser for (int x = 0; x < str; x++) { rader[x] = new Rad(); kolonner[x] = new Kolonne(); } for (int x = 0; x < str/boksX; x++) { for (int y = 0; y < str/boksY; y++) { bokser[x][y] = new Boks(); } } // Loop for å opprette bokser for (int x = 0; x < str; x++) { for (int y = 0; y < str; y++) { int v; // Fyller brettet med ruter. if (data[x][y] == 0) { v = 0; } else { v = data[x][y]; } ruter[x][y] = new Rute(this, v, kolonner[x], rader[y], bokser[x / boksX][y / boksY]); } } // 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); } } } public void print() { StringBuffer sb = new StringBuffer(); for(int y = 0; y < str * 2 + 1; y++) { for(int x = 0; x < str * 4 + 1; x++) sb.append((y%2==0?(x%4==0?(x%(4*boksX)==0?'#':(y%(2*boksY)==0?'=':'+')):(y%(2*boksY)==0?'=':'-')):(x%4==0?(x%(4*boksX)==0?'#':'|'):(x%4==2?ruter[x/4][y/2]:' ')))); sb.append('\n'); } System.out.println(sb.toString()); } /** Selve algoritmen for å finne løsninger */ public void finnLosninger() { print(); ruter[0][0].provAlleSifferMegOgResten(str); System.out.println(ruter[0][0].antallLosninger); }}/** * 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 father; Rute(Brett brt, int v, Kolonne k, Rad r, Boks b) { father = brt; k.leggTil(this); r.leggTil(this); b.leggTil(this); this.ruteVerdi = v; this.egenKol = k; this.egenRad = r; this.egenBoks = b; if (v == 0) { erFast = false; } else erFast = true; } /** Setter verdi til ruta */ public void settVerdi(int i) { ruteVerdi = i; } 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 ruta */ 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); if (harNeste()) { hentNeste().provAlleSifferMegOgResten(str); } else { antallLosninger++; father.print(); } } // finn neste løsning settVerdi(0); } } else { // gå til neste if (harNeste()) { hentNeste().provAlleSifferMegOgResten(str); } else { antallLosninger++; father.print(); } } } public String toString() { return String.valueOf(ruteVerdi); }}/** * Super-klasse for boks, kolonne og rad. */abstract class Underdel { ArrayList <Rute> ruter = new ArrayList<Rute>(); public void leggTil(Rute r) { ruter.add(r); } public boolean sjekkTall(int i) { boolean erSatt = false; for (int x = 0; x < ruter.size(); x++) { Rute r = (Rute) ruter.get(x); if (r.hentVerdi() == i) erSatt = true; } return !erSatt; }}class Boks extends Underdel {}class Kolonne extends Underdel {}class Rad extends Underdel {}