Backtracking-Algorithmus zur Lösung eines Sudokus

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

  • Backtracking-Algorithmus zur Lösung eines Sudokus

    Ich habe ein Programm geschrieben, das automatisch Sudokus lösen soll. Ich bin auch schon relativ weit gekommen nur leider weiß ich jetzt nicht genau wo mein Fehler nun steckt. Ich habe unter anderem zum Lösen einen backtracking-ähnlichen Algorithmus implementiert, der allerdings nicht so arbeitet wie er eigentlich sollte obwohl ich das ganze schon x-mal durchgegangen bin^^
    Vielleicht kann mir ja hier jemand weiterhelfen...
    Ich hab mal versucht alles wichtige im Quellcode zu kommentieren.

    Quellcode

    1. class Sudoku {
    3. int[][][] grid = new int[9][9][10]; // Sudoku-Feld; grid[x][y][0] speichert sichere Werte;
    4. // grid[x][y][1-9] ist 1-9 falls die entsprechende Ziffer
    5. // hier eine mögliche Lösung ist
    7. // Hier wird einiges unwichtiges ausgelassen ...
    9. Sudoku() {
    10. int i,j,k;
    11. // initializing grid
    12. for (i=0;i<9;i++) {
    13. for (j=0;j<9;j++) {
    14. for (k=0;k<10;k++) {
    15. grid[i][j][k] = k;
    16. }
    17. }
    18. }
    19. }
    21. // Hier wird einiges unwichtiges ausgelassen ...
    23. boolean gridSolved() { // prüft ob das Sudoku vollständig ist
    24. int i,j;
    25. boolean solved = true;
    26. for (i=0;i<9;i++) {
    27. for (j=0;j<9;j++) {
    28. if (grid[i][j][0] == 0)
    29. solved = false;
    30. }
    31. }
    32. return solved;
    33. }
    36. boolean contradiction(int x, int y) { // prüft den neu durch backtracking eingefügten Wert (ist die Zahl
    37. // in dieser Spalte/Zeile/diesem Unterquadrat doppelt?)
    38. // hier vermute ich den Fehler
    40. int i,j;
    41. boolean ok = true;
    43. HashSet<Integer> Co = new HashSet<Integer>(); // Spalte
    44. HashSet<Integer> Ro = new HashSet<Integer>(); // Zeile
    45. HashSet<Integer> Sq = new HashSet<Integer>(); // Unterquadrat
    47. for (i=0;i<9;i++) {
    48. if (grid[x][i][0]!=0) {
    49. ok = Co.add(grid[x][i][0]);
    50. if (!ok)
    51. return true; // Widerspruch -> return true;
    52. }
    53. if (grid[i][y][0]!=0) {
    54. ok = Ro.add(grid[i][y][0]);
    55. if (!ok)
    56. return true;
    57. }
    58. }
    60. for (i=x-(x%3);i<=x-(x%3)+2;i++) {
    61. for (j=y-(y%3);j<=y-(y%3)+2;j++) {
    62. if (grid[i][j][0]!=0) {
    63. ok = Sq.add(grid[i][j][0]);
    64. if (!ok)
    65. return true;
    66. }
    67. }
    68. }
    70. return false; // kein Widerspruch gefunden -> return false;
    71. }
    73. int[] setCoord(int x, int y) { // wird beim backtracking verwendet um ins nächste Feld zu wechseln
    74. int[] Coord = new int[2];
    75. if (x==8) {
    76. x=0;
    77. y++;
    78. } else {
    79. x++;
    80. }
    81. Coord[0] = x;
    82. Coord[1] = y;
    83. return Coord;
    84. }
    86. boolean backtrack(int x, int y) {
    87. int i;
    88. int[] Coord = new int[2];
    90. if (this.contradiction(x,y))
    91. return false; // Widerspruch -> falscher Pfad
    93. if (this.gridSolved())
    94. return true; // Sudoku gelöst?
    96. if (x!=0 || y!=0) { // wenn nicht am anfang, gehe zum nächsten Feld
    97. Coord = setCoord(x,y);
    98. x = Coord[0];
    99. y = Coord[1];
    100. }
    102. if (grid[x][y][0] != 0) { // wenn dieses Feld bereits belegt ist...
    103. Coord = setCoord(x,y); // springe zum nächsten Feld
    104. x = Coord[0];
    105. y = Coord[1];
    106. if (this.backtrack(x,y)) // und führe die selbe Funktion damit aus
    107. return true;
    108. }
    110. for (i=1;i<10;i++) { // wenn das Feld noch nicht belegt ist
    111. if (grid[x][y][i]==i) { //... und i eine mögliche Belegung ist
    112. grid[x][y][0]=i; //... dann setze das aktuelle Feld gleich i
    113. if (this.backtrack(x,y)) // und führe diese Funktion damit aus
    114. return true;
    115. }
    116. }
    118. return false; // wenn noch nichts zurückgegeben wurde, gebe false zurück
    120. }
    122. }
    Alles anzeigen
    Dateien

    • Konsole.java

      (12,13 kB, 664 mal heruntergeladen, zuletzt: )