Python-Sudoku-Rekursion mit Brute-Force-Backtracking-Fehler

Question

Ich mache einen Sudoku-Rätsellöser für die Hausaufgaben, aber ich stoße auf einige Schwierigkeiten. Der Code durchläuft jetzt die Lösung, obwohl er es für einfache Rätsel erreicht, und für härtere Rätsel bleibt er ohne ersichtlichen Grund mit mehreren Neunern stecken. Ich würde mich über jede Hilfe hier freuen. (check_cell bestimmt, ob das Placement gültig ist oder nicht.)

1. Ist das Zurückverfolgen in diesem Code korrekt implementiert, und wenn nicht, wie wäre das behoben?
2. Wie kann ich verhindern, dass der Solver einfriert? Es löst 3 Zeilen und friert dann ein, wobei die meisten Werte auf 9 geändert werden.

Einige Code:

def solve_helper(self, row, col): 
# Try placing a number in each column of current row 
    board = self.the_board 
    if board[row][col] != 0: 
     ????? 
    elif board[row][col] == 0: 
     for i in range(1,10): 
      print("Setting value at i with ") + str (i) + (" located at ") + str(row) + str(col) 
      self.set_cell(row, col, i) 
      self.guesses = self.guesses + 1 
      if self.check_cell(row, col): 
       if self.solve_helper(row, col): return True 
      else: 
       self.set_cell(row, col, 0) 
    else: 
     return self.mover(row,col) 
    return False 

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0) 
    else: 
     print "SOLUTION FOUND" 
     return True 

Answer 1

Das Problem Sie ist mit sind, dass einige Ihrer rekursive Anrufe werden Ihre Lösung nicht richtig, die Ergebnisse zurückkehrt, so, wenn es gefunden wird, wird über ein paar vergessen erhöht den rekursiven Stack. Hier ist das erste Update, das Sie benötigen, das Hinzufügen return die rekursiven Anrufe in mover:

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) # added return 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0)  # here too 
    else: 
     print "SOLUTION FOUND" 
     return True 

Sie müssen auch etwas ähnliches in dem speziellen Fall Ihrer solve_helper Funktion, wo man über bereits gelösten Zellen überspringt. Das Ende der Funktion sollte sein:

else: 
    return self.mover(row, col) # added return 
return False 

Edit:

Ok, ich habe noch ein paar Probleme im Code gefunden. Zwei von ihnen sind logische Probleme mit dem Solver, und einer ist ein Anzeigeproblem, das keine wirklichen Probleme verursacht, außer seltsam beim Lösen zu sein.

Die Themen:

1. Zuerst sind Sie neuesten Code solve_helper Aufruf selbst hat, anstatt mover Aufruf. Das erfordert einen zusätzlichen Funktionsaufruf vor dem Verschieben (obwohl ich denke, dass es den Solver nicht wirklich unterbricht).
2. Zweitens, wenn solve_helper setzt eine Zelle auf 9, aber dann in Backtracked zu (nach einigen späteren Zellen konnte nicht gelöst werden), wird die 9 nicht auf Null zurückgesetzt, bevor Backtracking weiter.
3. Und zuletzt, das Display Problem. Wenn Sie Zellen auf 0 setzen, wird der alte Wert nicht angezeigt. Dies sah sehr ähnlich aus wie das Problem in # 2 (mit 9s nach dem Zurückverfolgen zurückgelassen), aber in Wirklichkeit ist es nur kosmetisch.

Das erste Problem ist einfach zu beheben. Ändern Sie einfach den Anruf zu einem mover Anruf stattdessen. Genau das hatten Sie in dem ursprünglichen Code, den Sie in die Frage eingefügt haben. Der Aufruf von solve_helper führt direkt nicht zu einem falschen Ergebnis (da solve_helper die bereits ausgefüllte Zelle das zweite Mal überspringt), aber es fügt jeder Ebene Ihrer Rekursion einen unnötigen zusätzlichen Funktionsaufruf hinzu.

Das zweite Problem ist ein wenig komplizierter, und hier stecken Sie auf einigen Boards fest. Was Sie tun müssen, ist die Linie, die self.set_cell(row, col, 0) aus dem else Block ist es derzeit in Bewegung ist. In der Tat können Sie es tatsächlich außerhalb der Schleife vollständig verschieben, wenn Sie wollen (da es nur wirklich notwendig ist, wenn Sie sind Backtracking, nachdem keiner der Werte für die aktuelle Zelle funktioniert hat).Hier ist, was ich denke, das ist die beste Anordnung der for-Schleife (auch die return False Anweisung oben bewegt):

for i in range(1,10): 
    print("Setting value ") + str (i) + (" at ") + str(row) + ", " + str(col) 
    self.set_cell(row, col, i) 
    self.guesses = self.guesses + 1 
    if self.check_cell(row, col): 
     if self.mover(row, col): 
      return True 
print "Backtracking" 
self.set_cell(row, col, 0) 
return False 

Schließlich Fixierung das Anzeigeproblems erfordert zwei Änderungen. Zuerst werden Sie die Bedingung in set_cell loswerden. Sie möchten die Anzeige immer aktualisieren. Als nächstes, in update_textfield, verschieben Sie die delete Anruf außerhalb der if Block, so dass es immer passiert (lassen Sie die insert unter der if). Dies macht es so, dass das Setzen einer Zelle auf Null den vorherigen Wert löscht, aber nicht, dass sie ein tatsächliches 0-Zeichen anzeigt (es wird nichts angezeigt).

Ich denke, das sollte es tun. Beachten Sie, dass der von Ihnen verwendete Algorithmus immer noch ziemlich langsam ist. Lösen a board I found on the internet in a quick Google search dauerte 122482 Vermutungen und mehr als 5 Minuten, aber es hat endlich funktioniert. Andere Boards (vor allem solche, die in den ersten paar Freiräumen 8er oder 9er benötigen) können noch länger dauern.