001 package de.hska.java.aufgaben.backtracking;
002
003 import java.util.ArrayList;
004 import java.util.List;
005
006 /**
007 * <p>Sudoku lößt Sudoku-Rätsel mit einem Backtracking
008 * Algorithmus.
009 * Der Suchraum für eine Lösung ist sehr gross - insbesonders,
010 * wenn nur wenige Zahlen vorgegeben wurden. In diesen
011 * Fällen kann es sein, dass der Algorithmus zu lange braucht.</p>
012 * <p>
013 * Um den Suchraum klein zu halten, wird pro Zeile, Spalte und jede
014 * von den 3 x 3 Boxen eine
015 * bereits gesetzt Zahl vermerkt: Ein Schritt (neue Zahl z) ist nur dann gültig, wenn
016 * sie noch nicht in der Zeile, Spalte oder Box vorhanden ist.
017 * Dieser Ansatz ist ähnlich zur Lösung des Acht-Damen-Problems und sehr effektiv.
018 * </p>
019 *
020 * <p>
021 * <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/backtracking.html#sudoku">Zurück zum Aufgabentext</a>
022 * </p>
023 * @author Christian Pape
024 */
025 public class Sudoku {
026
027 private List<SudokuListener> sudokuListeners = new ArrayList<SudokuListener>();
028
029 public static final int LEERES_FELD = -1;
030
031 /**
032 * zeile[z][x] ist true genau dann, wenn in Zeile z die Zahl x gesetzt ist
033 */
034 private boolean [] [] zeile = new boolean[9][10];
035
036 /**
037 * spalte[s][x] ist true genau dann, wenn in Spalte s die Zahl x gesetzt ist
038 */
039 private boolean [] [] spalte = new boolean[9][10];
040
041 /**
042 * box[][] ist true genau dann, wenn in der zugehörigen 3 x 3 Box die zahl x gesetzt ist
043 * Ein Zelle (z,s) ist in Box mit Index 3 * (z / 3) + (s / 3)
044 */
045 private boolean [] [] box = new boolean[9][10];
046
047 /**
048 * das "spielfeld"
049 */
050 private int [] [] zahlenfeld = new int[9][9];
051
052 /**
053 * Eine vorgegebene Teillösung
054 */
055 private int [] [] teilloesung ;
056
057 /**
058 * Erzeugt ein neues Sudoku mit der übergebenen Teillösung.
059 */
060 public Sudoku(int [] [] teilloesung ) {
061 this.teilloesung = teilloesung;
062 initialisieren();
063 }
064
065 private void initialisieren() {
066 for (int boxnummer = 0; boxnummer < 9; boxnummer++) {
067 for (int zahl = 1; zahl < 10; zahl++) {
068 this.box[boxnummer][zahl] = false;
069 }
070 }
071 for (int zeile = 0; zeile < 9; zeile++) {
072 for (int spalte = 0; spalte < 9; spalte++) {
073 this.zeile[zeile][spalte + 1] = false;
074 this.spalte[zeile][spalte + 1] = false;
075 this.zahlenfeld[zeile][spalte] = LEERES_FELD;
076
077 if (! isLeeresFeld(teilloesung[zeile][spalte])) {
078 // Falls an dieser Stelle ein bestimmter Wert hingehört,
079 // so wird dies in den entsprechenden Datenstrukturen eingetragen.
080 this.zahlenfeld[zeile][spalte] = teilloesung[zeile][spalte];
081 this.zeile[zeile][teilloesung[zeile][spalte]] = true;
082 this.spalte[spalte][teilloesung[zeile][spalte]] = true;
083 this.box[getBoxNummer(zeile, spalte)][teilloesung[zeile][spalte]] = true;
084 }
085 }
086 }
087 }
088
089 private boolean isLeeresFeld(int zahl) {
090 return zahl <= 0 || zahl > 9;
091 }
092
093
094
095 /**
096 * Gibt den Inhalt des Spielfelds am Bildschirm aus.
097 */
098 public void print() {
099 for (int zeile = 0; zeile < 9; zeile++) {
100 for (int spalte = 0; spalte < 9; spalte++) {
101 System.out.print(zahlenfeld[zeile][spalte] + "\t");
102 }
103 System.out.println();
104 }
105 }
106
107
108 /**
109 * Sucht mit Backtracking rekursiv nach einer Lösung für das
110 * Sudoku.
111 * @param zaehler Gibt die Anzahl bisher belegter Zellen an - Startwert ist 0
112 * @return true, falls eine Lösung gefunden wurde
113 */
114 public boolean sucheLoesung(int zaehler) {
115 int zeile = zaehler / 9;
116 int spalte = zaehler % 9;
117
118 for (int zahl = 1; zahl < 10; zahl++) {
119 if (istGueltigerSchritt(zeile, spalte, zahl) ) {
120 boolean z = this.zeile[zeile][zahl];
121 boolean s = this.spalte[spalte][zahl];
122 boolean b = this.box[getBoxNummer(zeile, spalte)][zahl];
123 this.zahlenfeld[zeile][spalte] = zahl;
124 this.zeile[zeile][zahl] = true;
125 this.spalte[spalte][zahl] = true;
126 this.box[getBoxNummer(zeile, spalte)][zahl] = true;
127 zahlHatSichGeaendert(zeile, spalte);
128 if (zaehler < 80) {
129 if (sucheLoesung(zaehler + 1) ) {
130 return true;
131 } else {
132 this.zahlenfeld[zeile][spalte] = teilloesung[zeile][spalte];
133 this.zeile[zeile][zahl] = z;
134 this.spalte[spalte][zahl] = s;
135 this.box[getBoxNummer(zeile, spalte)][zahl] = b;
136 zahlHatSichGeaendert(zeile, spalte);
137 }
138 } else {
139 return true;
140 }
141 }
142 }
143 return false;
144 }
145
146
147
148
149
150 private int getBoxNummer(int zeile, int spalte) {
151 return 3 * (zeile / 3) + (spalte / 3);
152 }
153
154
155
156 /**
157 * Erzeugt ein Sudoku auf Basis zufälliger Vorgabezahlen.
158 *
159 * @param anzahlVorgaben Anzahl der Vorgabezahlen
160 */
161 public void erzeugeSudoku(int anzahlVorgaben) {
162 do {
163 for (int zeile = 0; zeile < teilloesung.length; zeile++) {
164 for (int spalte = 0; spalte < teilloesung[zeile].length; spalte++) {
165 teilloesung[zeile][spalte] = LEERES_FELD;
166 }
167 }
168 initialisieren();
169
170 for (int i = 0; i < anzahlVorgaben; i++) {
171 int zeile = (int) (Math.random() * 9);
172 int spalte = (int) (Math.random() * 9);
173 int zahl = 1 + (int) (Math.random() * 9);
174 if (istGueltigerSchritt(zeile, spalte, zahl)) {
175 this.zahlenfeld[zeile][spalte] = zahl;
176 this.zeile[zeile][zahl] = true;
177 this.spalte[spalte][zahl] = true;
178 this.box[getBoxNummer(zeile, spalte)][zahl] = true;
179 teilloesung[zeile][spalte] = zahl;
180 }
181 }
182 print();
183 System.out.println();
184 initialisieren();
185 } while ( ! sucheLoesung(0));
186
187 print();
188 initialisieren();
189 }
190
191 /**
192 * Gibt true zurück, wenn die gegebene zahl noch nicht in
193 * der gegeben spalte, zeile oder zugehörigen 3 x 3 Box vorkommt
194 */
195 private boolean istGueltigerSchritt(int zeile, int spalte, int zahl) {
196 return (teilloesung[zeile][spalte] == zahl || isLeeresFeld(teilloesung[zeile][spalte])
197 && ! this.zeile[zeile][zahl]
198 && ! this.spalte[spalte][zahl]
199 && ! this.box[getBoxNummer(zeile, spalte)][zahl]);
200 }
201
202
203 public void zahlHatSichGeaendert(int zeile, int spalte) {
204 for (SudokuListener sudokuListener : sudokuListeners ) {
205 sudokuListener.zahlHatSichGeaendert(zeile, spalte, zahlenfeld[zeile][spalte]);
206 }
207 }
208
209 public void addSudokuListener(SudokuListener sudokuListener) {
210 sudokuListeners.add(sudokuListener);
211 }
212
213 public void remoeSudokuListener(SudokuListener sudokuListener) {
214 sudokuListeners.remove(sudokuListener);
215 }
216
217 public int getZahl(int zeile, int spalte) {
218 return this.zahlenfeld[zeile][spalte];
219 }
220
221 public int [] [] getTeilloesung() {
222 return teilloesung;
223 }
224
225 public void printBoxNummern() {
226 for (int zeile = 0; zeile < 9; zeile++) {
227 for (int spalte = 0; spalte < 9; spalte++) {
228 System.out.print(getBoxNummer(zeile, spalte));
229 }
230 System.out.println();
231 }
232 }
233 public static void main(String argv[]) {
234
235 Sudoku sudoku = new Sudoku(new int[][] {
236 { 9, -1, 3, -1, 1, -1, 7, -1, -1},
237 {-1, 6, -1, -1, -1, 8, 5, -1, -1},
238 {-1, 5, -1, -1, -1, -1, -1, 9, 6},
239 {-1, -1, -1, -1, 3, -1, 6, -1, 4},
240 {-1, 4, -1, 9, -1, 1, 3, 7, 2},
241 {-1, -1, -1, 8, 7, 4, -1, 1, -1},
242 {-1, -1, 5, -1, -1, 3, 2, -1, 1},
243 { 6, 8, 7, -1, -1, -1, -1, -1, -1},
244 { 3, -1, -1, -1, -1, -1, -1, 5, -1}
245 });
246
247 sudoku.printBoxNummern();
248 /*
249 long t1 = System.nanoTime();
250
251 if ( sudoku.sucheLoesung(0) ) {
252 System.out.println("Lösung gefunden");
253 sudoku.print();
254 } else {
255 System.out.println("Keine Lösung gefunden");
256 }
257
258 long t2 = System.nanoTime() - t1;
259
260 System.out.println("Zeit: " + t2 + " ns / " + (t2 / 1000000) + " ms");
261 */
262 }
263 }