Sudoku Solver - Verständnisfrage

  • C

Es gibt 33 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Sudoku Solver - Verständnisfrage

    Hey Leute,

    ich hatte mir in den Kopf gesetzt einen Sudoku Solver zu programmieren. Ich habe bewusst NICHT im Internet danach gesucht und mir meine eignen Gedanken gemacht.
    Das Endprodukt war ein Solver, welcher an der Stelle aufgehört hat zu lösen, wo ein Widerspruch herauskam. Habe alles probiert, bin aber nicht weiter gekommen.
    Dann habe ich mich mal im Internet inspirieren lassen und damit letztendlich auch meinen Code so anpassen können, dass er funktioniert. Jedoch verstehe ich die Funktionsweise von
    solveField() nicht 100%. Wenn ich es mir Schrittweise debugge, dann stelle ich fest, dass der x Wert immer sobald es einen Widerspruch gibt in das zuletzt genutzte Feld springt.
    Dies ist mir aber aus dem Code nicht ersichtlich. Für mich wird x immer weiter erhöht und wenn die Zeile zu Ende ist, geht es in die Nächste. Das Zurückspringen ist echt irgendwie komisch.

    Ich hoffe mir kann jmd da auf die Sprünge helfen.

    Hier der Code:


    Spoiler anzeigen

    C-Quellcode

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <locale.h>
    5. #define G 9
    6. int feld[G][G] = {
    7. {0,4,5,7,0,0,0,6,1}, //Reihe 1
    8. {0,0,0,8,0,5,4,0,0}, //Reihe 2
    9. {0,0,7,6,4,0,0,0,2}, //Reihe 3
    10. {5,0,0,9,6,4,0,0,0}, //Reihe 4
    11. {6,0,8,5,0,1,0,3,0}, //Reihe 5
    12. {0,7,0,0,0,0,0,9,0}, //Reihe 6
    13. {3,0,2,4,0,0,1,0,0}, //Reihe 7
    14. {9,0,0,1,0,0,0,0,6}, //Reihe 8
    15. {0,0,0,0,0,3,8,0,0}};//Reihe 9
    17. void printField();
    18. void fillField();
    19. int solveField(int x, int y);
    20. int checkSudoku(int zahl, int x, int y);
    21. int getNextEmptyField(int *a, int *b);
    23. int main(void)
    24. {
    25. setlocale( LC_ALL, "" );
    27. //Programmablauf
    28. printField();
    29. printf("Taste drücken zum Starten...");
    30. getch();
    32. //Lösen
    33. solveField(0,0);
    35. printf("Sudoko gelöst!");
    36. getch();
    37. return 0;
    38. }
    40. //Sukoku Lösen
    41. int solveField(int x, int y)
    42. {
    43. if(x == G) //Zeilenende
    44. {
    45. y++;
    46. x = 0;
    47. }
    48. if(y == G)
    49. {
    50. //-> Solved
    51. return 1;
    52. }
    54. //Prüfen ob Feld gefüllt
    55. if(feld[y][x] > 0)
    56. {
    57. //Nächstes Feld
    58. return solveField(x+1, y);
    59. }
    61. //Zahl von 1-9 in aktuelles freies Feld einsetzen
    62. int z;
    63. for(z = 1; z < 10; z++)
    64. {
    65. //Zeilen prüfen - Spalten prüfen - 3er Päckchen prüfen
    66. if(checkSudoku(z,x,y) == 0)
    67. {
    68. feld[y][x] = z;
    69. //Auskommentieren zum Schrittweise anzeigen
    70. //printf("X: %d | Y: %d",x+1,y+1);
    71. //getch();
    72. //printField();
    74. if(solveField(x, y) == 1) //Gerade diese Zeile ist mir nicht ganz klar...
    75. {
    76. //Fertig -> Print
    77. printField();
    78. }
    79. } //else nächste Zahl z
    80. }
    81. feld[y][x] = 0; //Auch wenn die Zeile auf 0 gesetzt wird, dann ist doch x um +1 erhöht worden und es wäre jetzt ein Feld leer und übersprungen?
    82. return 0;
    83. }
    85. //Spielfeld nach den Regeln überprüfen
    86. int checkSudoku(int zahl, int x, int y)
    87. {
    88. int i,j;
    89. //Zeilen
    90. for(i = 0; i < 9; i++)
    91. {
    92. if(feld[y][i] == zahl)
    93. {
    94. return 1; //Vorhanden
    95. }
    96. }
    97. //Spalten
    98. for(i = 0; i < 9; i++)
    99. {
    100. if(feld[i][x] == zahl)
    101. {
    102. return 1; //Vorhanden
    103. }
    104. }
    106. //3er Kästchen
    107. int x_box, y_box;
    108. // Passende Ecke der Box herausfinden
    109. x_box = (int)(x / 3) * 3;
    110. y_box = (int)(y / 3) * 3;
    111. for(i = y_box; i < y_box + 3; i++)
    112. {
    113. for(j = x_box; j < x_box + 3; j++)
    114. {
    115. if(feld[i][j] == zahl)
    116. return 1; //Vorhanden
    117. }
    118. }
    120. return 0; //Nicht vorhanden.
    122. }
    124. //Funktion für späteres Vorhaben (zuerst auch für den algo. genutzt)
    125. int getNextEmptyField(int *a, int *b)
    126. {
    127. int i,j;
    128. for(i = 0; i < 9; i++)
    129. {
    130. for(j = 0; j < 9; j++)
    131. {
    132. if(feld[i][j] < 1)
    133. {
    134. //Treffer
    135. *a = i;
    136. *b = j;
    137. return 1;
    138. }
    139. }
    140. }
    141. //Kein Feld gefunden
    142. return 0;
    143. }
    145. //Funktion für späteres Vorhaben
    146. void fillField()
    147. {
    148. int x,y,w = 0;
    149. printf("Zeile: ");
    150. scanf("%d", &x);
    151. printf("Spalte: ");
    152. scanf("%d", &y);
    154. //Feld auf leere Stelle prüfen
    155. if(feld[y-1][x-1] < 1)
    156. { //Leer
    157. printf("Zahl: ");
    158. scanf("%d", &w);
    159. //Überprüfung einbauen ob Zahl korrekt
    160. feld[y-1][x-1] = w;
    161. }
    162. main();
    164. }
    166. //Ausgabe des Spielfeldes in der CMD
    167. void printField()
    168. {
    169. //Console leeren
    170. system("cls");
    171. system("color 0F");
    173. printf(" .:[Sudoku Solver v1]:.\n\n");
    175. int i,j;
    176. //Zeilen, Y-Achse
    177. printf(" 1 2 3 4 5 6 7 8 9\n");
    178. for(i=0; i<9; i++)
    179. {
    180. printf(" +---+---+---+---+---+---+---+---+---+\n");
    181. printf("%d |", i+1);
    182. //Spalten, X-Achse
    183. for(j=0; j<9; j++)
    184. {
    185. if(feld[i][j] < 1)
    186. { //Feld leer
    187. printf(" |");
    188. }
    189. else
    190. { //Feld gefüllt
    191. printf(" %d |", feld[i][j]);
    192. }
    193. }
    194. printf("\n");
    195. }
    196. printf(" +---+---+---+---+---+---+---+---+---+\n");
    197. }




    LG

    Michael

    MB-Tech schrieb:

    auf die Sprünge helfen.
    Wenn das Verhalten reproduzierbar merkwürdig ist, setz einen Haltepunkt rein und vergleiche das was er macht mit dem was er tun soll.
    Da solltest Du den Fehler eigentlich in 3 Minuten gefunden haben.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Der Trick ist, dass die Funktion rekursiv aufgerufen wird und die Variablen x und y auf dem Stack liegen. So kann man jederzeit zum alten Zustand zurück, wenn checkSudoku 1 zurückliefert und eine neue Zahl probieren.
    Bevor ich das jetzt versuche genau zu erklären, such mal im Netz etwas nach Backtracking.

    Das Backtracking habe ich mir durchgelesen aber nicht zu 100% verstanden. Wie genau kann man "zurückspringen"? Zudem verwirrt das Return 0 noch ein wenig.

    Gruß

    MB-Tech schrieb:

    Wie genau kann man "zurückspringen"?
    Du musst Dir beim Durchführen eines Schrittes den aktuellen Zustand merken. Wenn Du die 1 testest, weißt Du, dass danach die 2 dran ist. Wenn Du mit der 1 nicht durch kommst, holst Du Dir den letzten aktuellen Zustand zurück und machst mit der 2 weiter.
    Usw.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ok, aber wie wird der alte Zustand gemerkt? Die Funktion ruft sich ja immer selbst auf, aber mit den selben Werten oder eben mit x+1.

    MB-Tech schrieb:

    aber wie wird der alte Zustand gemerkt?
    In einem Array, wo die bisherigen Werte abgelegt werden.
    In .NET würde ich dazu eine List(Of T) verwenden.
    Vielleicht entwickelst Du den Algo zunächst in .NET, bevor Du ihn nach native c / c++ überträgst.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich finde, so wirr, wie die Frage gestellt ist, kann man eiglich gar nicht helfen, ausser die Wirrsal zu spiegeln, und den TE auffordern, seine Frage klar zu stellen.

    Also was ich an "Informationen" empfangen habe ist:
    • 197 Zeilen c++ - Code, und wir sollen dir nun "auf die Sprünge helfen"
    • Das Zurückspringen ist echt irgendwie komisch.
    • Das Backtracking haste durchgelesen aber nicht zu 100% verstanden.
    • Wie genau kann man "zurückspringen"?
    • das Return 0 verwirrt dich
    Wie gesagt: Ich hab ühaupt keine Idee, wie man darauf sinnvoll antworten kann.


    Übrigens braucht man beim Backtracking mittels Rekursion nicht ständig eine List(Of T) mitzuführen.
    Diese Liste wird erst erstellt, wenn die erste Lösung gefunden wurde, und der Algo beendet - gewissermassen auf dem "Nachhauseweg", wenn alle verschachtelten Aufrufe returnen.
    Das ist glaub auch die Bedeutung des Begriffs "Back-Tracking" - "Rück-Verfolgung" (oder? mein Englisch ist nicht wirklich berühmt :/ )

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

    ErfinderDesRades schrieb:

    197 Zeilen c++ - Code, und wir sollen dir nun "auf die Sprünge helfen"


    Dann konzentrieren wir uns auf die solve Funktion. Das ist ja der Knackpunkt.

    C-Quellcode

    1. //Sukoku Lösen
    2. int solveField(int x, int y)
    3. {
    4. if(x == G) //Zeilenende
    5. {
    6. y++;
    7. x = 0;
    8. }
    9. if(y == G)
    10. {
    11. //-> Solved
    12. return 1;
    13. }
    15. //Prüfen ob Feld gefüllt
    16. if(feld[y][x] > 0)
    17. {
    18. //Nächstes Feld
    19. return solveField(x+1, y);
    20. }
    22. //Zahl von 1-9 in aktuelles freies Feld einsetzen
    23. int z;
    24. for(z = 1; z < 10; z++)
    25. {
    26. //Zeilen prüfen - Spalten prüfen - 3er Päckchen prüfen
    27. if(checkSudoku(z,x,y) == 0)
    28. {
    29. feld[y][x] = z;
    30. //Auskommentieren zum Schrittweise anzeigen
    31. //printf("X: %d | Y: %d",x+1,y+1);
    32. //getch();
    33. //printField();
    35. if(solveField(x, y) == 1) //Gerade diese Zeile ist mir nicht ganz klar...
    36. {
    37. //Fertig -> Print
    38. printField();
    39. }
    40. } //else nächste Zahl z
    41. }
    42. feld[y][x] = 0; //Auch wenn die Zeile auf 0 gesetzt wird, dann ist doch x um +1 erhöht worden und es wäre jetzt ein Feld leer und übersprungen?
    43. return 0;
    44. }


    Das Zurückspringen ist wie gesagt noch meine Frage. Da bin ich noch nicht ganz hinter gestiegen.
    Ich erkläre mal soweit ich es verstanden habe:

    Funktion wird aufgerufen mit den x,y Werten 0. Danach prüft er, ob x der max Anzahl vom Array entspricht, falls ja y++.
    Falls y max Arraysize ist, dann das Sudokufeld komplett durchgelaufen und er returnt 1. (Könnte man hier nicht auch das "Ende" der Funktion setzen?
    Weil weiter unten wird ja abgefragt if(solveField(x,y) == 1)...?)

    Dann wird geprüft, ob etwas im Feld steht. Falls ja, dann rekrusiv aufrufen mit x+1 für das nächste Feld.
    Hat nichts drin gestanden, dann werden alle Zahlen von 1-9 ausprobiert. Sobald die Zahl die Sudokuregeln nicht verletzt wird diese genommen.
    Ergibt die Funktion 1, dann ist das Sudoku am Ende und das Feld wird ausgegeben. (Warum so und nicht direkt bei return 1 weiter oben?)

    Am Ende wird der Wert immer wieder auf 0 gesetzt und 0 returned. Warum?

    Ich hoffe meine Fragen sind nun klarer gestellt.

    Grüße

    ja, ist ein rekursiver versuch, aber mit logischem Fehler drin.

    Geplant ist scheinbar, dass die Methode 1 zurückgibt, wenn das sudoku gelöst ist.
    also müsste es beim if(checkSudoku()==0) noch einen else-Zweig geben, der 1 returnt, und damit die Suche abbricht.
    ebenfalls mit return 1 abgebrochen werden muss, wenn der rekursive Aufruf in #35 1 ergibt, denn dann ist ja eine Lösung gefunden.

    Wie du die Lösung dann präsentierst weiß ich nicht - das gehört auch nicht in die methode hinein - also das mit printfield wird glaub nix.

    Ja funktioniert. Deswegen bin ich ja so ratlos und frage die ganze Zeit...

    ah - jetzt sehe ich:
    #12: return 1;, wenn y die 10. Zeile erreicht hat. (ich nehme an G = 9)
    Dann nämlich sind alle 9 Zeilen erfolgreich ausgefüllt.

    Der Algo beendet beim ersten Erfolg nicht, sondern printet, und sucht dann weiter.

    Es werden die 9 Ziffern getestet, und wenn checkSudoku() eine Zahl als widerspruchsfrei attestiert wird diese ins feld eingetragen und der Selbst-Aufruf erfolgt mit erhöhtem Index.

    Also der Selbstaufruf erhöht den Index nur bei widerspruchsfrei eingetragener Zahl.
    Und 1 wird zurückgegeben, wenn der Index out of range ist - dann ist nämlich alles ausgefüllt.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

    RushDen schrieb:

    Das kann gar nicht funktionieren, x und y werden nicht als Referenz übergeben (das wäre hier nämlich die einzige Möglichkeit, da der rekursive aufruf (also der zweite) mit den gleichen Parametern aufgerufen wird und es dadurch nie zu einer Abbruchbedingung kommen kann, selbst wenn eine gegeben wäre)


    Kopier dir den Source aus dem ersten Post mal in eine C IDE (Dev++ z.B.) und führe es aus. Es wird klappen.


    Der Selbstaufruf mit x+1 erfolgt doch nur, wenn ein Feld nicht leer ist, oder?

    Gruß

    Doppelpost zusammengefügt. ~Thunderbolt

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Thunderbolt“ ()

    naja, das ist schon sehr verschroben.
    Also wenn der Check erfolgreich, dann wird das feld gesetzt - #29 und er ruft sich selbst auf.
    Im Selbstaufruf dann stellter in #16 fest, dass das feld besetzt ist und ruft sich mit erhöhtem x auf.

    also ziemlich krank.

    Ich habs in vb bisserl gradlieniger:

    VB.NET-Quellcode

    1. Private Sub Solve()
    2. ReadFields()
    3. If Solve(0, 0) Then
    4. WriteFields(True)
    5. Else
    6. Msg("solve failed")
    7. End If
    8. End Sub
    10. Private Function TrySetValue(ByVal y As Integer, ByVal x As Integer, ByVal val As Integer) As Boolean
    11. For xx = 0 To 8
    12. If _Fields(y, xx) = val Then Return False
    13. Next
    14. For yy = 0 To 8
    15. If _Fields(yy, x) = val Then Return False
    16. Next
    17. Dim xBox = (x \ 3) * 3
    18. Dim yBox = (y \ 3) * 3
    19. For yy = yBox To yBox + 2
    20. For xx = xBox To xBox + 2
    21. If _Fields(yy, xx) = val Then Return False
    22. Next
    23. Next
    24. _Fields(y, x) = val
    25. Return True
    26. End Function
    28. Private Function Solve(ByVal y As Integer, ByVal x As Integer) As Boolean
    29. If x > 8 Then
    30. y += 1 : x = 0
    31. If y > 8 Then Return True 'finally all cells are set
    32. End If
    33. If _Fields(y, x) > 0 Then Return Solve(y, x + 1) 'user-set cell: recurse at once, skip digit-trying
    34. For val = 1 To 9
    35. 'try set 9 digits: On success recurse. if recursion also succeeds finish algo
    36. If TrySetValue(y, x, val) AndAlso Solve(y, x + 1) Then Return True
    37. Next
    38. 'no digit found: reset field + return false
    39. _Fields(y, x) = 0
    40. Return False
    41. End Function
    Diese Variante beendet aber den ganzen Algo, sobald die erste Lösung gefunden

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    Ok, also wenn Feld gesetzt und prüfung ok, dann x+1. das geht dann so lange bis ein widerspruch herauskommt. Dann müsste ja alles wieder Stufenweise zurück gehen, dieses ist mir aber noch nicht ersichtlich :/

Facebook
Telefonspende