Sudoku Algorithmus Backtracking

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Sudoku Algorithmus Backtracking

    Zur Benutzung dieses Sudokus Algorithmus'
    java -jar <option> <puzzle> <puzzle> <puzzle> <...>

    <option> = Option
    Option 1) = Zeige Sudoku
    Option 2) = Löse Sudoku mit Backtracking
    Option 3) = Löse Sudoku mit optimiertem Backtracking
    <puzzle> = Dateiname
    Die Puzzles werden nacheinander abgearbeitet

    Beispielsudokus sind diesem Thread angehängt

    Das ADSTool kümmert sich um Zeitenmessung und um das Einlesen der Dateien. Ihr findet es außerdem als Dateianhang

    Quellcode

    1. package ads;
    2. /**
    3. * Autoren: Marco May & Torben Brodt
    4. */
    5. import fhw.ADSTool;
    7. public class SudokuPlay {
    8. public static void main(String[] args) {
    9. if(args.length < 2)
    10. System.out.println("Zur Backtracking Loesung 2 als Paramter uebergeben\nZum intelligenten Loesen eine 3");
    12. ADSTool.resetTime();
    13. if(args.length > 1)
    14. for(int i=1; i<args.length; i++) {
    15. Sudoku feld = new Sudoku(9, args[0], args[i]);
    16. System.out.println(feld);
    17. ADSTool.showRTime();
    18. System.out.println();
    19. }
    20. }
    21. }
    23. class Sudoku {
    24. // Konstante fuer die Anzahl an Blöcken(9er/12er Sudoku) und die Breite einer Box (3 oder 4)
    25. public final int n, box_n;
    27. // Zaehlt die Anzahl der erprobten Platzierungen
    28. public int tries=0;
    30. // Sudoku Feld (noch nicht vorbelegt, da 9^12 moeglich sind)
    31. public byte[][] feld;
    33. /**
    34. * Konstruktor
    35. * args[0] = dateiname
    36. * args[1] = smart
    37. */
    38. public Sudoku(int n, String what, String filename) {
    40. this.n = n;
    41. this.box_n = (int)Math.sqrt(n);
    42. this.feld = new byte[n][n];
    44. //Datei einlesen
    45. read(filename);
    47. //und loesen
    48. if(what.equals("2")) {
    49. solveBacktrack(0,0);
    51. } else if(what.equals("3")) {
    52. smartSolve();
    54. } else if(what.equals("1")) {
    55. // belassen fuer einfache Ausgabe
    56. }
    58. }
    60. /**
    61. * Liest ein Raetsel ein
    62. */
    63. public void read(String filename) {
    64. int i=0, j=0;
    66. try {
    67. int[] file = ADSTool.readIntArray(filename);
    69. for(int digit : file) {
    70. if(j == n) {
    71. j = 0;
    72. i++;
    73. }
    74. feld[i][j] = (byte)digit;
    75. j++;
    76. }
    77. } catch(Exception e) {
    78. System.out.println("Bitte mit dem korrekten Dateinamen als Konsolenparameter starten");
    79. System.exit(0);
    80. }
    81. }
    83. /**
    84. * Loest das Raetsel durch Backtracking
    85. */
    86. public boolean solveBacktrack(int i, int j) {
    87. if(j == n) { /* Zeilenende erreicht,
    88. * fange wieder links an,
    89. * gehe eine Zeile nach unten
    90. * oder breche ab, wenn du ganz fertig bist
    91. */
    92. i++;
    93. if(i == n)
    94. return true;
    95. j = 0;
    96. }
    98. if(feld[i][j] > 0) // Das Feld ist erfolgreich gesetzt
    99. // Funktionsaufruf mit naechster Spalte
    100. return solveBacktrack(i, j+1);
    102. for(byte a=1; a<n+1; a++) {
    103. if(check(i, j, a) == false) {
    104. feld[i][j] = a;
    105. if(solveBacktrack(i, j+1))
    106. return true;
    107. }
    108. }
    110. feld[i][j] = 0; // Der Versuch war wohl nichts
    111. return false;
    112. }
    115. /**
    116. * Prueft ob dieses Feld gesetzt werden kann (ruft dabei 3 Subfunktionen auf)
    117. * @return-> Gibt true zurueck, wenn der Wert bereits existiert
    118. */
    119. public boolean check(int i, int j, int value) {
    120. tries++;
    122. // Fuer die Ausgabe mit SudokuSmart
    123. // System.out.println(""+i+"/"+j);
    125. if(checkHorizontal(j, value))
    126. return true;
    128. if(checkVertical(i, value))
    129. return true;
    131. if(checkBox(i, j, value))
    132. return true;
    134. return false;
    135. }
    137. /**
    138. * Prueft ob der Wert bereits in der (horizontalen) SPALTE existiert
    139. * @return-> Gibt true zurueck, wenn der Wert bereits existiert
    140. */
    141. public boolean checkHorizontal(int j, int value) {
    142. for(int a=0; a<n; a++)
    143. if(feld[a][j] == value)
    144. return true;
    146. return false;
    147. }
    149. /**
    150. * Prueft ob der Wert bereits in der (vertikalen) REIHE existiert
    151. * @return-> Gibt true zurueck, wenn der Wert bereits existiert
    152. */
    153. public boolean checkVertical(int i, int value) {
    154. for(int a=0; a<n; a++)
    155. if(feld[i][a] == value)
    156. return true;
    158. return false;
    159. }
    161. /**
    162. * Prueft ob der Wert bereits in der BOX existiert
    163. * @return-> Gibt true zurueck, wenn der Wert bereits existiert
    164. */
    165. public boolean checkBox(int i, int j, int value) {
    166. // oberes, linkes Eck der Box herausfinden (2|8 zu 0|6)
    167. int i_start = (int)(i/box_n) * box_n;
    168. int j_start = (int)(j/box_n) * box_n;
    170. for(int a=i_start; a<i_start+box_n; a++)
    171. for(int b=j_start; b<j_start+box_n; b++)
    172. if(feld[a][b] == value)
    173. return true;
    175. return false;
    176. }
    178. /**
    179. * SMART: Loest das Raetsel intelligenter
    180. */
    181. public boolean smartSolve() {
    182. int[] best = smartChoice();
    183. int i=best[0], j=best[1];
    185. if(i == -1 && j == -1) //Das Sudoku funktioniert - es gibt keine leeren Felder mehr
    186. return true;
    188. for(byte a=1; a<n+1; a++) {
    189. // System.out.print("pruefe wert "+a+" in ");
    190. if(check(i, j, a) == false) {
    191. feld[i][j] = a;
    192. if(smartSolve())
    193. return true;
    194. }
    195. }
    197. feld[i][j] = 0; // Der Versuch war wohl nichts
    198. return false;
    199. }
    202. /**
    203. * Sucht die Position der besten Möglichkeit
    204. * gibt es eine Anzahl von Moeglichkeiten oefter, dann
    205. * dann wird die letzte Zahl als beste Moeglichkeit gewaehlt,
    206. * um in einem späteren Schleifendurchläufen Performance zu sparen
    207. * @return: Gibt die Koordinaten zurueck
    208. */
    209. public int[] smartChoice()
    210. {
    211. int minCount=n, minI=-1, minJ=-1;
    212. for(int i=0; i<n; i++) {
    213. for(int j=0; j<n; j++) {
    214. if(feld[i][j] == 0) {
    215. int c = smartCount(i,j);
    216. if(c <= minCount) {
    217. minCount = c;
    218. minI = i;
    219. minJ= j;
    220. }
    221. }
    222. }
    223. }
    224. int[] results = {minI, minJ};
    225. return results;
    226. }
    229. /**
    230. * SMART: Zaehlt die leeren Felder (die Anzahl an moeglichen Loesungen)
    231. */
    232. public int smartCount(int i, int j) {
    233. boolean[] list = new boolean[10];
    235. for(int a=0; a<n; a++) {
    236. if(feld[i][a] > 0)
    237. list[feld[i][a]] = true; // Durch "true" schliessen wir die Felder mit Wert aus
    238. if(feld[a][j] > 0)
    239. list[feld[a][j]] = true;
    240. }
    242. //Box
    243. int i_start = (int)(i/box_n) * box_n;
    244. int j_start = (int)(j/box_n) * box_n;
    245. for(int a=i_start; a<i_start+box_n; a++)
    246. if(a != i)
    247. for(int b=j_start; b<j_start+box_n; b++)
    248. if(feld[a][b] > 0 && b != j)
    249. // >0 schliesst mehr Felder aus, dadurch an Pos1 der Abfrage
    250. list[feld[a][b]] = true;
    252. // Jetzt zaehlen wir die Felder, die wir gefunden haben
    253. byte max=0, possible=0;
    254. for(byte a=1; a<=n; a++) {
    255. if(list[a] == false)
    256. max++;
    257. else
    258. possible = a;
    259. }
    261. if(max == 1) {
    262. feld[i][j] = possible;
    263. }
    265. return max;
    266. }
    269. /**
    270. * Ueberschreibt die Ausgabefunktion
    271. * Wir verwenden hier nur einen Zaehler
    272. * n*n Stringerweiterungungen sind langsamer als StringBuffer
    273. */
    274. public String toString() {
    275. StringBuffer returns = new StringBuffer();
    277. for(int i=0; i<n*n; i++) {
    279. if(i%n == 0 && i > 0) {
    280. returns.append("\n");
    281. if(i%(box_n*n) == 0)
    282. returns.append("-----------------------\n");
    283. }
    285. if (i%box_n == 0 && i%n != 0)
    286. returns.append(" |");
    288. returns.append(feld[i/n][i%n] == 0 ? " " : " "+feld[i/n][i%n]);
    289. }
    290. returns.append("\nEs wurden "+tries+" Platzierungen ausprobiert in ");
    291. return returns.toString();
    292. }
    293. }
    Alles anzeigen
    Dateien

    • fhwads.jar

      (29,85 kB, 2.621 mal heruntergeladen, zuletzt: )

    • sudokupuzzles.zip

      (1,82 kB, 2.648 mal heruntergeladen, zuletzt: )

  • Ich bin auf dieses Forum durch Google gestoßen, da ich auf der Suche nach einem Script zum Lösen von Sudokus war. Dieses hier gefällt mir im Gegensatz zu den anderen richtig gut und habe es auch gleich nach PHP umgeschrieben 8)
    Nun möchte ich aber noch einen Sudoku-Generator programmieren, für den ich die Anzahl der Lösungen für ein Sudoku benötige, um ein eindeutig lösbares Sudoku zu erhalten. Ich sitze jetzt schon zwei Tage daran und habe noch keine funktionierende Lösung gefunden. Könnte ihr mir da weiterhelfen?

  • Cool, poste doch mal die PHP Variante.
    Obwohl ich PHP eigentlich besser beherrsche als Java, bin ich beim PHP Sudoku gescheitert.
    Die Objektverwaltung macht PHP halt etwas anders.

    Einen Sudoku Generator habe ich nicht selbst geschrieben.
    Wiki beschreibt grob das Vorgehen
    http://de.wikipedia.org/wiki/Sudoku#Erstellung_neuer_Sudokus

    1. Weg: Ein leeres Puzzlefeld wird Zelle für Zelle durch „Auswürfeln“ (Zufallsgenerator) mit Ziffern befüllt. Sobald es zu einem Regelverstoß kommt, muss per Backtracking-Methode eine andere Belegung probiert werden. Dies ist weniger trivial als beim Lösen des Puzzles: Da eine möglichst „zufällige“ Belegung des Puzzlefeldes benötigt wird, kann man nicht einfach alle Ziffern der Reihe nach durchprobieren. Es hindert aber nicht, alle Ziffern, sobald sie einmal „ausgewürfelt“ wurden, als künftig – für die jeweilige Zelle – gesperrt „abzuhaken“ (in einer Tabelle zu markieren)

    2. Weg: Neun Einsen ohne Regelverstoß im Puzzelfeld verteilen. Dann neun Zweier, neun Dreier, usw. verteilen. Auch hier muss ein Backtracking-Algorithmus angewandt werden.

    3. Weg: Man füllt eine Zeile oder eine Spalte in beliebiger Reihenfolge mit den erlaubten Ziffern, verschiebt dann mit jeder weiteren Zeile/Spalte die Ziffernfolge, bis man am Schluss alle möglichen Varianten untereinander/nebeneinander in einer n × n-Matrix vorliegen hat. Dies alleine wäre ein äußerst trivial zu lösendes Rätsel, da sich die Ziffernfolgen wiederholen; deswegen sollte man über erlaubte Transformationen diese Matrix nun schrittweise so verändern, dass die Ursprungsziffernfolge sowie die ausgeführten Transformationen nicht mehr nachvollziehbar sind. Erlaubte Transformationen sind z. B. das Invertieren, das Spiegeln (vertikal, horizontal, schräg), Rotieren, Vertauschen ganzer Zeilen oder Spalten, sofern sie innerhalb eines Mini-Quadrates bleiben, oder das Vertauschen ganzer Zeilen und Spalten von Miniquadraten. Etliche dieser Transformationen hintereinander verwischen (fast) alle Hinweise auf die ursprüngliche Ziffernfolge. Von den hier vorgestellten Erstellungsmethoden ist diese die am wenigsten aufwendige aber rechenintensivste.


    Auf hexadoku.de setze ich pysdk ein - das solltest du dir auch mal im Source anzeigen. Ist wirklich "relativ" wenig Code.

  • pysdk sieht sehr gut aus, vielen Dank für den Link :) Dann werde ich das benutzen, enthält ja sowohl Solver als auch Generator.

    Woran bist du an der PHP Variante gescheitert? Ich habe den Code eigentlich 1:1 mit den entsprechenden Funktionen in PHP umgewandelt, jedoch auf die Methoden solveBacktrack und check mit seinen Submethoden reduziert.
    Den Code kann ich noch posten, muss ihn nur noch mal etwas sortieren und übersichtlicher schreiben :wink:

  • Ich hatte gerade mal ein wenig zeit und hab mir mal den Sudoku Code angeschaut.

    1. Könnte es sein, dass die "smart"-Variante nicht so smart ist, wie man glauben soll?
    Bei mir produziert dieser Algorithmus ein paar 9er zu viel.

    2. Das ist jetzt nicht böse gemeint, aber dein Quellcode ist nicht gerade leserlich bzw. leicht verständlich. Ein paar mehr Leerzeichen bzw. Leerzeilen, aber vor allem eine konsequente Klammersetzung wären von vorteil.

    3. Ansonsten: repekt ;)
    Ubuntu Edgy * Kernel 2.6.17 * Gnome 2.16 * Beryl
    2 x Athlon MP 1900 * MSI K7D Master-L * 1024 MB ECC DDR333
    Hercules 9800XT 256 MB Ram * 1x 250 GB IDE
    Wasserkühlung

  • @1: unser Proff hat zumindest keine Fehler beanstandet. Kannst du mir ein Beispiel nennen, wo das Ergebnis falsch ist?

    @2: Im realen Leben streiten sich die Männer wer den längsten hat, beim Coden gehts nunmal drum, wer den kürzesten Code hat. Und da wir die Aufgabe alle machen mussten, hatte man konnte man direkt vergleichen.
    Aber "konsequent" ist es doch. Alles was einen Einzeier zur Folge hat, ist nicht geklammert - alles andere schon.

  • Hehe wer den kürzesten Code hat ;)
    Das ist gut, solltet wohl mit Assembler anfangen.

    Hab das Programm mit "3" und "puzzle1.sudoku" aufgerufen und bekomm das hier als Ergebnis.

    9 9 9 | 1 3 8 | 4 7 9
    6 9 9 | 9 9 5 | 2 9 8
    7 5 2 | 9 9 4 | 1 3 9
    -----------------------
    8 7 9 | 3 9 2 | 9 5 4
    5 4 1 | 9 9 9 | 6 2 3
    9 2 3 | 5 4 6 | 7 8 1
    -----------------------
    9 9 7 | 8 6 1 | 3 4 5
    4 8 6 | 7 5 3 | 9 9 2
    9 1 9 | 4 2 9 | 9 6 7
    Es wurden 134 Platzierungen ausprobiert in

    Und zum Thema konsequenter Klammerung. Nein du hast mindestens einmal ne if-Anweisung drinnen, bei der ein "Einzeiler" geklammert wurde (Aus rein leserlichen Gründen würde ich prinzipiell auch bei Einzeilern die Klammern dazumachen.
    Ubuntu Edgy * Kernel 2.6.17 * Gnome 2.16 * Beryl
    2 x Athlon MP 1900 * MSI K7D Master-L * 1024 MB ECC DDR333
    Hercules 9800XT 256 MB Ram * 1x 250 GB IDE
    Wasserkühlung

  • Ich habe mir das Ganze mal etwas genauer angesehen.
    * Das normale Backtracking funktioniert problemlos.
    * Bei der Smart-Variante liegt der Fehler in den Zeilen 261-263; das gehört schlichtweg raus. Beim Vorwärts-Weg wird hier ein Wert (possible) eingetragen, aber beim Rückwärts-Weg gibt es kein entsprechendes Löschen(0). Wie schon gesagt: Die drei Zeilen raus, und alles läuft bestens.

    Die Vorgabe aus puzzle1:
    9 | 1 3 8 | 7
    6 | | 8
    2 | | 1
    -------+-------+------
    8 7 | 3 2 | 5 4
    | 9 |
    9 2 | 5 6 | 8 1
    -------+-------+------
    7 | | 3
    4 | | 2
    1 | 4 2 9 | 6

    Die Lösung dazu mit Smart:
    5 9 4 | 1 3 8 | 2 7 6
    6 3 1 | 2 7 5 | 4 9 8
    7 8 2 | 9 6 4 | 1 3 5
    -------+-------+------
    8 7 6 | 3 1 2 | 9 5 4
    1 4 5 | 8 9 7 | 6 2 3
    9 2 3 | 5 4 6 | 7 8 1
    -------+-------+------
    2 5 7 | 6 8 1 | 3 4 9
    4 6 9 | 7 5 3 | 8 1 2
    3 1 8 | 4 2 9 | 5 6 7
    Es wurden 253 Platzierungen ausprobiert in 1.39 s

    Ich habe zudem damit noch verschiedene Erweiterungen (z.B. 2x3, 2x4, X-Sudoku) implementiert; das Beispiel war die ideale Basis. Fazit: Ich als Prof hätte eine glatte 1-2 vergeben ;-).

    Hägar

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von hägar ()