import java.io.*;import java.util.ArrayList;/** * Kontrollklassen */class Doku{ // MVC private Board board; private View view; private ArrayList<String> listOfBoards; /** * Klasse main, oppretter nytt kontrollobjekt som starter løsning. */ public static void main(String[] args) { if(args.length < 1) { System.out.println("Ingen fil angitt, avslutter."); System.exit(0); } else { new Doku(args[0]); } } private Doku(String fileName) { // opprett utsyn view = new View(); // opprett modell fileToBoard(fileName); // løs brettet og lagre alle løsninger listOfBoards = new ArrayList<String>(); board.solve(); // vis løsninger showSolutions(); } /** * Leser inn data til brettet. * Oppretter brettet med riktige dimensjoner * og setter forhåndsutfylte ruter. * * Metoden antar at filen har et strengt format, * hvor de tre første linjene angir * lengde på brettside, * høyde til en boks, * bredde til en boks, * og hvor de neste linjene hver består av en rad på brettet. */ private void fileToBoard(String fileName) { try { BufferedReader in = new BufferedReader(new FileReader(fileName)); String s; // kast første linje (sidelengde, ubrukelig) s = in.readLine(); // les inn bokshøyde og boksbredde int boxHeight = Integer.parseInt(in.readLine().trim()); int boxWidth = Integer.parseInt(in.readLine().trim()); int length = boxHeight * boxWidth; // opprett et brett med tomme ruter board = new Board(boxWidth, boxHeight, this); // les inn rutene for(int y = 0; y < length; y++) { s = in.readLine().trim(); for(int x = 0; x < length; x++) { int n = Field.DIGIT.indexOf(s.charAt(x)); if(n != -1) board.setField(x, y, n); } } in.close(); } catch(FileNotFoundException e) { quit("Kan ikke åpne fil " + fileName + ": " + e); } catch(IOException e) { quit("Kan ikke lukke fil " + fileName + ": " + e); } } /** * Legger inn et ferdig utfylt brett i listen over disse. */ void saveBoard(String s) { listOfBoards.add(s); } /** * Skriver løsninger til utsyn. */ void showSolutions() { view.showSolutions(listOfBoards, 50); } /** * Avslutter med feilmelding. */ public void quit(String s) { view.giveError(s + "\nAvslutter..."); System.exit(0); }}/** * Utsyn */class View{ View() {} /** * Skriver ut løsningene til terminal. * Dersom det er flere enn <i>max</i> løsninger, * skriv bare de <i>max</i> første. */ void showSolutions(ArrayList<String> solution, int max) { int n = solution.size(); System.out.print((n == 0 ? "Ingen" : n)); System.out.print(" løsning"); System.out.print((n <= 1 ? "" : "er")); System.out.print((n > max ? ", viser de " + max + " første" : "")); System.out.print((n == 0 ? "." : ":")); System.out.println("\n"); for(int i = 0; i < n && i < 50; i++) { if(n > 1) System.out.println("Løsning " + (i + 1) + ": "); System.out.println(solution.get(i)); } } void giveError(String s) { System.out.println("Feil:\n\t" + s); }}/** * Klasse for et brett med en gitt størrelse. * Brettet kan endre egne ruter, * men vil ikke overskrive verdier som er gitt på forhånd * eller lage ulovlige kombinasjoner. */class Board{ // MVC private Doku control; private int boxWidth, boxHeight, length; private Field[][] field; private Row[] row; private Column[] col; private Box[] box; Board(int bw, int bh, Doku control) { this.control = control; boxWidth = bw; boxHeight = bh; // lengde pa side = antall siffer i en boks = bw * bh length = boxWidth * boxHeight; // initialiser arrayer field = new Field[length][length]; row = new Row[length]; col = new Column[length]; box = new Box[length]; for(int i = 0; i < length; i++) { row[i] = new Row(length); col[i] = new Column(length); box[i] = new Box(length); } // initialiser ruter og tilordne grupper for(int y = 0; y < length; y++) { for(int x = 0; x < length; x++) { Field f = new Field(x, y, this); field[y][x] = f; row[y].setField(x, f); col[x].setField(y, f); box[(y/boxHeight)*boxHeight+x/boxWidth].setField((y%boxHeight)*boxWidth+x%boxWidth, f); } } } /** * Starter i øverste venstre hjørne og prøver å fylle ut brettet. */ void solve() { field[0][0].tryAllDigitsAndNext(); } /** * Lagrer en strengrepresentasjon av brettet i en liste i kontrollobjektet. */ int bretthittil = 0; void save() { System.out.print(++bretthittil + " : "); System.out.println(toString()); control.saveBoard(toString()); } /** * Setter en rute til en bestemt verdi. */ void setField(int x, int y, int value) { field[y][x].setValue(value); } /** * Undersøker om en rute er den siste ruten på brettet. */ boolean hasMoreFieldsAfter(Field f) { return !((f.getX() == length - 1) && (f.getY() == length - 1)); } /** * Returnerer påfølgende rute. */ int maxIndex = 0; Field getNextField(Field f) { int index = f.getY() * length + f.getX() + 1; if(index > maxIndex) { maxIndex = index; System.out.println(maxIndex); } return field[index / length][index % length]; } /** * Gir lengden på en brettside */ int getLength() { return length; } /** * Returnerer en strengrepresentasjon av brettet. */ public String toString() { StringBuffer sb = new StringBuffer(); // pent asciibrett if(true) for(int y = 0; y < length * 2 + 1; y++) { for(int x = 0; x < length * 4 + 1; x++) sb.append((y%2==0?(x%4==0?(x%(4*boxWidth)==0?'#':(y%(2*boxHeight)==0?'=':'+')):(y%(2*boxHeight)==0?'=':'-')):(x%4==0?(x%(4*boxWidth)==0?'#':'|'):(x%4==2?field[y/2][x/4]:' ')))); sb.append('\n'); } // en løsning per linje else for(int y = 0; y < length; y++) { for(int x = 0; x < length; x++) sb.append(field[y][x]); sb.append("// "); } return sb.toString(); }}/** * Klasse for en enkel rute. */class Field{ /** Mulige siffere. */ public final static String DIGIT = "0123456789abcdefghijklmnopqrstuvwxyz@"; private int value, x, y; // pekere til grupper ruten tilhører private Board board; private Row row; private Column col; private Box box; /** * Initialiserer en rute uten verdi. */ Field(int x, int y, Board b) { board = b; this.x = x; this.y = y; value = -1; } /** * Setter ruten til en forhåndsbestemt verdi. */ void setValue(int v) { value = v; } /** * Angir hvilken rad ruten ligger i */ void setRow(Row r) { row = r; } /** * Angir hvilken kolonne ruten ligger i. */ void setCol(Column c) { col = c; } /** * Angir hvilken boks ruten ligger i. */ void setBox(Box b) { box = b; } /** * Tester om ruten er utfylt. */ boolean hasValue() { return value != -1; } int getValue() { return value; } int getX() { return x; } int getY() { return y; } /** * Tester alle siffer for dette og påfølgende tomme ruter. * Fortsetter til brettet ikke har flere ruter, * og lagrer da det ferdig utfylte brettet. * Dersom ruten er utfylt, test bare dette sifferet. */ void tryAllDigitsAndNext() { // test bare ett siffer hvis ruten er utfylt if(hasValue()) { int i = value; value = -1; // test i alle grupper if(!row.contains(i) && !col.contains(i) && !box.contains(i)) { value = i; // fortsett hvis det finnes flere ruter if(board.hasMoreFieldsAfter(this)) board.getNextField(this).tryAllDigitsAndNext(); // hvis dette er siste rute, lagre brettet else board.save(); } } // hvis ikke, prøv alle siffer else { for(int i = 1; i <= board.getLength(); i++) { // test i alle grupper if(!row.contains(i) && !col.contains(i) && !box.contains(i)) { value = i; // fortsett hvis det finnes flere ruter if(board.hasMoreFieldsAfter(this)) board.getNextField(this).tryAllDigitsAndNext(); // hvis dette er siste rute, lagre brettet else board.save(); } } // rens ruten value = -1; } } /** * Returner et tegn som representerer verdien. * Returnerer "." hvis ruten ikke har noen verdi. */ public String toString() { return value == -1 ? "." : "" + DIGIT.charAt(value); }}/** * Superklasse til rader, kolonner og bokser. */abstract class FieldGroup{ protected Field[] field; FieldGroup(int l) { field = new Field[l]; } /** * Undersøker om gruppen inneholder en verdi. * * @param value Verdien som skal letes etter. * @return <i>true</i> hvis verdien finnes, ellers <i>false</i>. */ boolean contains(int value) { for(Field f : field) if(f.hasValue() && f.getValue() == value) return true; return false; }}/** * Klasse for rad, har pekere til en gruppe ruter. */class Row extends FieldGroup{ Row(int l) { super(l); } void setField(int n, Field f) { field[n] = f; f.setRow(this); }}/** * Klasse for kolonne, har pekere til en gruppe ruter. */class Column extends FieldGroup{ Column(int l) { super(l); } void setField(int n, Field f) { field[n] = f; f.setCol(this); }}/** * Klasse for boks, har pekere til en gruppe ruter. */class Box extends FieldGroup{ Box(int l) { super(l); } void setField(int n, Field f) { field[n] = f; f.setBox(this); }}