import java.io.*;import java.util.ArrayList;/** * Kontrollklassen */class Doku{ // MVC Board board; View view; 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); } /** * Avslutter med feilmelding */ public void quit(String s) { view.giveError(s + "\nAvslutter..."); System.exit(0); }}/** * Utsyn */class View{ View() {} void showSolutions(ArrayList<String> solution) { System.out.println("" + solution.size() + " løsninger:\n"); for(int i = 0; i < solution.size() && i < 10; i++) { System.out.println("Løsning " + i + ":"); System.out.println(solution.get(i)); } } void giveError(String s) { System.out.println("Feil:\n\t" + s); for(int i = 0; i < 128; i++) { System.out.println(i + (i % 16 == 15 ? "\n" : " "); } }}/** * Klasse for et brett med en gitt størrelse. * Brettet er dynamisk og kan endre på egne ruter, * men vil ikke overskrive verdier som er gitt * eller lage ulovlige kombinasjoner. */class Board{ // MVC 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, i); } // 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+x%boxWidth, f); } } } /** * Starter i øverste venstre hjørne og prøver å fylle ut brettet. */ void solve() { save(); field[0][0].tryAllDigitsAndNext(length); } /** * Lagrer en ascii av brettet i en liste i kontrollobjektet. */ void save() { //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 */ Field getNextField(Field f) { int index = f.getY() * length + f.getX() + 1; return field[index / length][index % length]; } /** * Returnerer et ascii-brett som en streng. */ public String toString() { StringBuffer sb = new StringBuffer(); 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?'=':'+')):(y%(2*boxHeight)==0?'=':'-')):(x%4==0?(x%(4*boxWidth)==0?'$':'|'):(x%4==2?field[y/2][x/4]:' ')))); sb.append('\n'); } return sb.toString(); }}class Field{ 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, hopp til neste. */ void tryAllDigitsAndNext(int length) { // hopp over loop hvis ruten er utfylt if(hasValue()) { // fortsett hvis det finnes flere ruter if(board.hasMoreFieldsAfter(this)) board.getNextField(this).tryAllDigitsAndNext(length); // hvis dette er siste rute, lagre brettet else board.save(); } // hvis ikke, prøv alle siffer else { for(int i = 1; i <= length; i++) { boolean digitOK = true; // test i alle grupper digitOK &= !row.contains(i); digitOK &= !col.contains(i); digitOK &= !box.contains(i); if(digitOK) { value = i; // fortsett hvis det finnes flere ruter if(board.hasMoreFieldsAfter(this)) board.getNextField(this).tryAllDigitsAndNext(length); // 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); }}abstract class FieldGroup{ protected Field[] field; FieldGroup(int l) { field = new Field[l]; } void setField(int n, Field f) { field[n] = f; } /** * 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) { boolean b = false; for(Field f : field) b |= (f == null ? false : (f.hasValue() ? f.getValue() == value : false)); return b; }}class Row extends FieldGroup{ Row(int l) { super(l); } void setField(int n, Field f) { field[n] = f; f.setRow(this); }}class Column extends FieldGroup{ Column(int l) { super(l); } void setField(int n, Field f) { field[n] = f; f.setCol(this); }}class Box extends FieldGroup{ int index; Box(int l, int i) { super(l); index = i; } void setField(int n, Field f) { field[n] = f; f.setBox(this); } int getIndex() { return index; }}