Tipps zum debuggen eines SudokuSolvers

  • VB.NET

Es gibt 10 Antworten in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

    Tipps zum debuggen eines SudokuSolvers

    Hallo,

    ich habe ein JavaScript, das ich (richtig?) in VB übersetzt habe... Habe es versucht so gut ich konnte...

    Auf der Form habe ich ein TableLayoutPanel zum Positionieren der 81 (Multiline) TextBoxen benutzt.

    Der Solver gibt natürlich nicht! eine korrekte Lösung in die TextBoxen aus...

    Könntet ihr mir Hinweise geben was ich vielleicht falsch übersetzt habe?

    Habe versucht zu debuggen...

    Könntet ihr mir Hinweise geben wie man so etwas sinnvoll debuggt (irgendwie ist es nicht einfach die Orientierung zu behalten...)?

    Hier das JavaScript:

    Quellcode

    1. ​function sudokuSolver(matrix) {
    2. if (solveSudoku(matrix) === true) {
    3. return matrix;
    4. }
    5. return 'NO SOLUTION';
    6. }
    7. const UNASSIGNED = 0;
    8. function solveSudoku(matrix) {
    9. let row = 0;
    10. let col = 0;
    11. let checkBlankSpaces = false;
    12. /* verify if sudoku is already solved and if not solved,
    13. get next "blank" space position */
    14. for (row = 0; row < matrix.length; row++) {
    15. for (col = 0; col < matrix[row].length; col++) {
    16. if (matrix[row][col] === UNASSIGNED) {
    17. checkBlankSpaces = true;
    18. break;
    19. }
    20. }
    21. if (checkBlankSpaces === true) {
    22. break;
    23. }
    24. }
    25. // no more "blank" spaces means the puzzle is solved
    26. if (checkBlankSpaces === false) {
    27. return true;
    28. }
    29. // try to fill "blank" space with correct num
    30. for (let num = 1; num <= 9; num++) {
    31. /* isSafe checks that num isn't already present
    32. in the row, column, or 3x3 box (see below) */
    33. if (isSafe(matrix, row, col, num)) {
    34. matrix[row][col] = num;
    35. if (solveSudoku(matrix)) {
    36. return true;
    37. }
    38. /* if num is placed in incorrect position,
    39. mark as "blank" again then backtrack with
    40. a different num */
    41. matrix[row][col] = UNASSIGNED;
    42. }
    43. }
    44. return false;
    45. }
    46. function isSafe(matrix, row, col, num) {
    47. return (
    48. !usedInRow(matrix, row, num) &&
    49. !usedInCol(matrix, col, num) &&
    50. !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
    51. );
    52. }
    53. function usedInRow(matrix, row, num) {
    54. for (let col = 0; col < matrix.length; col++) {
    55. if (matrix[row][col] === num) {
    56. return true;
    57. }
    58. }
    59. return false;
    60. }
    61. function usedInCol(matrix, col, num) {
    62. for (let row = 0; row < matrix.length; row++) {
    63. if (matrix[row][col] === num) {
    64. return true;
    65. }
    66. }
    67. return false;
    68. }
    69. function usedInBox(matrix, boxStartRow, boxStartCol, num) {
    70. for (let row = 0; row < 3; row++) {
    71. for (let col = 0; col < 3; col++) {
    72. if (matrix[row + boxStartRow][col + boxStartCol] === num) {
    73. return true;
    74. }
    75. }
    76. }
    77. return false;
    78. }
    79. const matrix = [
    80. [5, 3, 0, 0, 7, 0, 0, 0, 0],
    81. [6, 0, 0, 1, 9, 5, 0, 0, 0],
    82. [0, 9, 8, 0, 0, 0, 0, 6, 0],
    83. [8, 0, 0, 0, 6, 0, 0, 0, 3],
    84. [4, 0, 0, 8, 0, 3, 0, 0, 1],
    85. [7, 0, 0, 0, 2, 0, 0, 0, 6],
    86. [0, 6, 0, 0, 0, 0, 2, 8, 0],
    87. [0, 0, 0, 4, 1, 9, 0, 0, 5],
    88. [0, 0, 0, 0, 8, 0, 0, 7, 9]
    89. ];
    90. console.log(sudokuSolver(matrix));


    Hier mein Versuch in VB:

    VB.NET-Quellcode

    1. ​Public Class Form1
    2. Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
    3. End Sub
    4. Const UNASSIGNED = 0
    5. Private Sub loeseButton_Click(sender As Object, e As EventArgs) Handles loeseButton.Click
    6. Dim i As Integer, j As Integer, n As Integer
    7. Dim matrix(80, 80) As Integer
    8. 'Matrix füllen
    9. n = 1
    10. For i = 0 to 8
    11. For j = 0 To 8
    12. If Me.TableLayoutPanel1.Controls("TextBox" & n).Text <> "" Then
    13. matrix(i, j) = CInt(Me.TableLayoutPanel1.Controls("TextBox" & n).Text)
    14. End If
    15. n += 1
    16. Next
    17. Next
    18. SudokuSolver(matrix)
    19. End Sub
    20. Function SudokuSolver(matrix(,) As Integer) As Integer
    21. Dim n As Integer
    22. If SolveSudoku(matrix) = True Then
    23. n = 1
    24. For i = 0 To 8
    25. For j = 0 To 8
    26. Me.TableLayoutPanel1.Controls("TextBox" & n).Text = CStr(matrix(i, j))
    27. n += 1
    28. Next
    29. Next
    30. MessageBox.Show("Sudoku gelöst.")
    31. End If
    32. Return Nothing
    33. End Function
    34. Function SolveSudoku(matrix(,) As Integer) As Boolean
    35. Dim row As Integer, col As Integer, num As Integer
    36. Dim checkBlankSpaces As Boolean = False
    37. ' verify if sudoku is already solved and if not solved,
    38. ' get next "blank" space position
    39. For row = 0 To 8
    40. For col = 0 To 8
    41. If matrix(row, col) = UNASSIGNED Then
    42. checkBlankSpaces = True
    43. Exit For
    44. End If
    45. Next col
    46. If checkBlankSpaces = True Then
    47. Exit For
    48. End If
    49. Next row
    50. ' no more "blank" spaces means the puzzle is solved
    51. If checkBlankSpaces = False Then
    52. Return True
    53. End If
    54. ' try to fill "blank" space with correct num
    55. For num = 1 To 9
    56. 'isSafe checks that num isn't already present
    57. 'in the row, column, or 3x3 box (see below)
    58. If IsSafe(matrix, row, col, num) Then
    59. matrix(row, col) = num
    60. If SolveSudoku(matrix) = True Then
    61. Return True
    62. End If
    63. 'if num is placed in incorrect position,
    64. 'mark as "blank" again then backtrack with
    65. 'a different num
    66. matrix(row, col) = UNASSIGNED
    67. End If
    68. Next num
    69. Return False
    70. End Function
    71. Function IsSafe(matrix(,) As Integer, row As Integer, col As Integer, num As Integer) As Boolean
    72. Return (Not UsedInRow(matrix, row, num) Or Not UsedInCol(matrix, col, num) Or Not UsedInBox(matrix, row - (row Mod 3), col - (col Mod 3), num))
    73. End Function
    74. Function UsedInRow(matrix(,) As Integer, row As Integer, num As Integer) As Boolean
    75. For col As Integer = 0 To 8
    76. If matrix(row, col) = num Then
    77. Return True
    78. End If
    79. Next col
    80. Return False
    81. End Function
    82. Function UsedInCol(matrix(,) As Integer, col As Integer, num As Integer) As Boolean
    83. For row As Integer = 0 To 8
    84. If matrix(row, col) = num Then
    85. Return True
    86. End If
    87. Next row
    88. Return False
    89. End Function
    90. Function UsedInBox(matrix(,) As Integer, boxStartRow As Integer, boxStartCol As Integer, num As Integer) As Boolean
    91. For row As Integer = 0 To 2
    92. For col As Integer = 0 To 2
    93. If matrix(row + boxStartRow, col + boxStartCol) = num Then
    94. Return True
    95. End If
    96. Next col
    97. Next row
    98. Return False
    99. End Function
    100. Private Sub löschenButton_Click(sender As Object, e As EventArgs) Handles löschenButton.Click
    101. Dim ctrl As Control
    102. For Each ctrl In Me.TableLayoutPanel1.Controls
    103. If TypeOf ctrl Is TextBox Then
    104. ctrl.Text = ""
    105. End If
    106. Next
    107. End Sub
    108. End Class


    Das angefügte Bild der Form soll nur zur Orientierung dienen...

    Ich bitte um eure geschätzte Hilfe...

    Viele Grüße,

    Kwon
    Bilder
    • bildgrid.jpg

      31,28 kB, 313×425, 39 mal angesehen
    @kwon Das ist jetzt nicht Dein Ernst.
    Du hast da einen Code übertragen, verstehst das Original nicht und wir sollen Deinen übertragenen Code re-designen?
    Zum Testen von Code gehört eine Spezifikation, was bei welcher Aktion zu passieren hat.
    Du musst schon so was schreiben wie:
    Mit der und der Ausgangssituation erwarte ich dies und jenes, es passiert aber was ganz anderes.
    Es kann ja sein, dass Dein Code nicht Sudoku löst, sondern die Wörter eines Textes zählt.
    Und:
    Sollen wir nach Deinem Code eine GUI designen, so dass der Code compiliert?
    Wenn, dann hänge Dein bereinigtes Projekt ohne obj, bin und vs-Verzeichnis gezippt an.
    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!
    Warum tust du nicht einfach, was er vorschlägt?

    RodFromGermany schrieb:

    hänge Dein bereinigtes Projekt ohne obj, bin und vs-Verzeichnis gezippt an.
    Dann kann man daran arbeiten (wenn jmd. Lust hat).
    So, im Browser ist das bei so viel Code nicht möglich.

    Zum Anhängen:

    Und nochmal zur Erinnerung: das angehängte, gezippte Projekt soll(te möglichst) sofort nach dem Entpacken starten können, und es soll keine Ordner obj, bin, vs enthalten.

    kwon schrieb:

    ich wollte niemand verärgern...
    Du hast niemanden verärgert. :D
    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!

    angehängtes Projekt

    Hallo,
    vielen Dank für die Unterstützung!!

    Ich verstehe nicht, warum in Zeile 59 in die matrix(0,1) der Wert 1 geschrieben wird, obwohl matrix(0,0) bereits 1 enthält.
    Die Funktion IsSafe() sollte mit den Funktionen UsedinRow(), UsedinCol() und UsedinBox() dies eigentlich verhindern.

    Ich habe mein Projekt angehängt (und die erwähnten Ordner entfernt). Habe getestet, ob man die sln-Datei öffnen kann.
    Ich habe auch ein Beispiel mit vorgegebenen Zahlen in die TextBoxen eingefügt, damit man es leichter debuggen kann.

    Ich würde mich sehr darüber freuen, wenn sich jemand das Projekt mal anschauen könnte.

    Ich wünsche einen schönen Abend...

    Viele Grüße,
    kwon
    Dateien
    • projekt.zip

      (17,16 kB, 43 mal heruntergeladen, zuletzt: )

    VB.NET-Quellcode

    1. Function IsSafe(matrix(,) As Integer, row As Integer, col As Integer, num As Integer) As Boolean
    2. Return Not UsedInRow(matrix, row, num)
    3. AndAlso Not UsedInCol(matrix, col, num)
    4. AndAlso Not UsedInBox(matrix, row - (row Mod 3), col - (col Mod 3), num)
    5. End Function
    Eigentlich alles ok, nur da war Or reingeschrieben, wo AndAlso hingehört

    Achso - die matrix ist viel zu fett - ersetze

    VB.NET-Quellcode

    1. Dim matrix(80, 80) As Integer
    2. durch
    3. Dim matrix(8, 8) As Integer


    Dann würde ich noch dringend empfehlen, den Deppen-Namespace-GeneralImport zu entfernen.
    Visual Studio - Empfohlene Einstellungen

    Edit: Link korrigiert

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

    Hallo ErfinderDesRades,

    Vielen Dank, dass du dir das Projekt mal angesehen hast...
    Wenn nur die Sache mit dem AndAlso war, dann hatte ich das JavaScript gar nicht mal so schlecht übersetzt...

    ErfinderDesRades schrieb:

    Dann würde ich noch dringend empfehlen, den Deppen-Namespace-GeneralImport zu entfernen.


    Deinen Vorschlag zur Änderung bezogen auf die Benennung von den controls (wahrscheinlich meinst du die TextBoxen?) verstehe ich nicht - stehe da komplett auf dem Schlauch...
    Habe mir den Link angesehen, aber leider weiß ich nicht was mit "Deppen-Namespace-GeneralImport" gemeint ist (ich bin halt kein Profi).
    Vielleicht könntest du mir kurz sagen was an der Benennung falsch ist - das würde mich sehr freuen...

    Ansonsten läuft der SudokuSolver und ich werde den berichtigten Code (für jemanden, der interessiert ist) einstellen sobald das mit der Benennung geklärt ist.

    Vielen Dank nochmals für die Unterstützung...

    Viele Grüße,
    kwon

    kwon schrieb:

    dann hatte ich das JavaScript gar nicht mal so schlecht übersetzt.
    Jo :thumbup:
    Und ausserdem eine funktionierende und sogar gut programmierte Vorlage gewählt.
    Oft genug geraten Anfänger an irgendwas im INet, was höchst zweifelhaft programmiert ist, und/oder auch garnet funktioniert.



    Zur Benennung von irgendwas hab ich garnix gesagt - ich sagte "Deppen-Namespace" - damit meinte ich den Namespace Microsoft.VisualBasic.

    Ein Namespace hat nichts mit Benamung zu tun. Ich habe dein Projekt unter Option Strict On vorgefunden - also die Hälfte des gegebenen Tuts ist bereits abgearbeitet - da dachte ich, du wüsstest, was ein Namespace, und speziell der "Deppen-Namespace" sei.
    Gross nochmal erklären werde ich das Problem (es sind zwei Probleme, eines ist zumindest für dieses Projekt schon gelöst) hier nicht - es ist im gegebenen Tut erklärt, befilmt, ausschweifend erklärt und nochmal erklärt und mit zusätzlichen Links versehen.
    Hier jetzt noch eine Erklärung wird nix besser machen.
    Aber wenn du spezielle Fragen zum Tut hast, frag.

    kwon schrieb:

    Vielleicht könntest du mir kurz sagen was an der Benennung falsch ist - das würde mich sehr freuen...

    ErfinderDesRades schrieb:

    Zur Benennung von irgendwas hab ich garnix gesagt
    Da ist die Verlinkung von EDR in die Irre gegangen (obwohl's dort auch bei Punkt 7 im Eingangspost angedeutet wurde...)
    Er meinte sicher diese --> Visual Studio - Empfohlene Einstellungen
    nichtsdestotrotz kann man die Verständlichkeit des Projekts stark erhöhen.
    ZB ist der Lösungs-Algo kein BruteForce, sondern ist ein rekursiver Backtracking-Algorithmus.
    Bei Backtracking werden exorbitant viele Lösungs-Versuche gar nicht erst unternommen, wenn eine Teil-Lösung sich schon als irregulär erweist.
    Dieses Prinzip, und dass es durch Rekursion umgesetzt ist - das dürfte gerne in die Kommentation.

    Und dann viele Formulierungen gehen eleganter - zB ist ganz unnötig, einen Boolean mit True zu vergleichen - kommt doch immer nur derselbe Boolean bei raus.

    Jo, Benamung auch - kann man immer verbessern.