Python Sudoku Recursion z Brute Force Backtracking Error

Question

Robię sudoku puzzle dla zadania domowego, ale napotykam na pewne trudności. Teraz kod przechodzi obok rozwiązania, chociaż osiąga go dla łatwych układanek, a dla trudniejszych zagadek utknie z kilkoma dziewięcioma bez wyraźnego powodu. Byłbym wdzięczny za pomoc w tej sprawie. (check_cell określa, czy miejsce docelowe jest poprawne, czy nie).

1. Czy w tym kodzie prawidłowo zastosowano mechanizm cofania, a jeśli nie, w jaki sposób zostałby on rozwiązany?
2. Jak zatrzymać solwera przed zamarznięciem? Rozwiązuje on około 3 wierszy, a następnie zawiesza się, zmieniając większość wartości na 9s.

Niektóre kodu:

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

Kłopot masz to, że niektóre z twoich rekurencyjnych wywołań nie wracają wyniki prawidłowo, więc rozwiązanie, gdy okaże się, dostaje zapomnieli o kilka wyrównuje stos rekursywny. Oto pierwsza poprawka, że ​​trzeba, dodając return do wywołań rekurencyjnych wykonanych w 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 

Trzeba też coś podobnego w szczególnym przypadku swojej funkcji solve_helper gdzie można przeskoczyć wstępnie rozwiązany komórek. Koniec funkcji powinno być:

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

Edit:

Ok, znalazłem jeszcze kilka kwestii w kodzie. Dwa z nich są problemami logicznymi z solver, a jednym jest problem z wyświetlaniem, który nie powoduje żadnych rzeczywistych problemów poza wyglądaniem dziwnym podczas rozwiązywania.

Zagadnienia:

1. pierwsze, jesteś ostatni kodu solve_helper nazywająca siebie, zamiast wywoływania mover. To powoduje, że przed wykonaniem ruchu wykonuje dodatkowe wywołanie funkcji (chociaż myślę, że to nie może tak naprawdę rozwiązać solver).
2. Po drugie, jeśli solve_helper ustawi komórkę na 9, ale następnie zostanie cofnięta do (po kilku późniejszych komórkach nie da się rozwiązać), 9 nie zostanie zresetowane do zera przed dalszym cofaniem.
3. I na koniec kwestia wyświetlania. Ustawienie komórek na 0 nie zatrzymuje wyświetlania ich starej wartości. To wyglądało bardzo podobnie do problemu z # 2, (z 9 sekundami pozostało po backtrackingu), ale w rzeczywistości jest to tylko kosmetyk.

Pierwszy problem jest łatwy do naprawienia. Wystarczy zmienić wywołanie solve_helper na połączenie mover. Tak właśnie było w oryginalnym kodzie, który umieściłeś w pytaniu. Wywołanie solve_helper bezpośrednio nie daje właściwie błędnego wyniku (ponieważ solve_helper po raz drugi pominie już wypełnioną komórkę), ale doda niepotrzebne dodatkowe wywołanie funkcji do każdego poziomu rekursji.

Drugi problem jest nieco bardziej skomplikowany, i to jest to, gdzie utknąłeś na niektórych tablicach. Trzeba tylko przesunąć linię, która ma self.set_cell(row, col, 0) z bloku else, w którym aktualnie się znajduje. Rzeczywiście, możesz go całkowicie przenieść poza pętlę, jeśli chcesz (ponieważ jest to naprawdę konieczne, jeśli jesteś backtracking po tym, jak żadna z wartości dla bieżącej komórki nie zadziałała).Oto, co myślę jest to najlepszy układ pętli for (również poruszającej się return False oświadczenie w górę):

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 

Wreszcie ustalające problem wyświetlania wymaga dwóch zmian. Najpierw pozbądź się warunku w set_cell. Chcesz zawsze aktualizować wyświetlacz. Następnie, w update_textfield, przenieś wywołanie delete poza blok if tak, aby zawsze miało miejsce (pozostaw insert pod if). Powoduje to, że ustawienie komórki na zero spowoduje skasowanie poprzedniej wartości, ale nie sprawi, że wyświetli ona rzeczywisty 0 znak (nie pokaże niczego).

Myślę, że powinno się to zrobić. Zauważ, że algorytm, którego używasz, jest wciąż dość powolny. Rozwiązywanie a board I found on the internet in a quick Google search zajęło 122482 wartości przypuszczeń i ponad 5 minut, ale w końcu udało się. Inne płyty (szczególnie te, które wymagają 8s lub 9s w pierwszych kilku otwartych przestrzeniach) mogą trwać jeszcze dłużej.