Python Sudoku Ricorsione con Brute Force Backtracking Error

Question

Sto facendo un risolutore di puzzle di Sudoku per i compiti, ma sto incontrando qualche difficoltà. Il codice in questo momento supera la soluzione, anche se lo raggiunge per i puzzle facili, e per i puzzle più difficili, rimane bloccato con diversi 9 senza alcun motivo apparente. Apprezzerei qualsiasi aiuto su questo. (check_cell determina se il posizionamento è valido o meno)

1. Backtracking è implementato correttamente in questo codice e, in caso contrario, come sarebbe corretto?
2. Come arrestare il solver dal congelamento? Risolve intorno a 3 file e poi si blocca, cambiando la maggior parte dei valori in 9 secondi.

Alcuni codice:

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

Il problema che stai avendo è che alcune delle vostre chiamate ricorsive non stanno tornando i risultati correttamente, quindi la soluzione, quando si trova, ottiene dimenticato un paio di livella la pila ricorsiva. Ecco la prima correzione di cui avete bisogno, aggiungendo return alle chiamate ricorsive effettuate nel 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 

È inoltre necessario qualcosa di simile nel caso particolare della funzione solve_helper dove si salta più di cellule pre-risolto. La fine della funzione dovrebbe essere:

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

Edit:

Ok, ho trovato un paio di problemi nel codice. Due di questi sono problemi logici con il risolutore, e uno è un problema di visualizzazione che non causa problemi reali oltre a sembrare strano durante la risoluzione.

Le questioni:

1. primo luogo, sei ultimo codice è solve_helper si fa chiamare, piuttosto che chiamare mover. Questo rende necessaria una chiamata di funzione extra prima di spostarsi (anche se penso che potrebbe non rompere il risolutore).
2. In secondo luogo, se solve_helper imposta una cella su 9, ma poi torna indietro (dopo alcune celle successive non possono essere risolte), il 9 non viene reimpostato su zero prima di tornare indietro.
3. E infine, il problema di visualizzazione. L'impostazione di celle su 0 non interrompe la visualizzazione del loro vecchio valore. Questo assomigliava molto al problema in # 2, (con 9s lasciato indietro dopo il backtracking) ma in realtà è solo cosmetico.

Il primo problema è facile da risolvere. Basta cambiare la chiamata solve_helper a una chiamata mover. Questo è in realtà ciò che avevi nel codice originale che hai inserito nella domanda. Chiamare direttamente il numero solve_helper non ottiene il risultato errato (dal momento che il solve_helper salterà la cella già compilata per la seconda volta), ma aggiunge una chiamata di funzione extra non necessaria a ciascun livello della ricorsione.

Il secondo problema è un po 'più complicato, ed è qui che ti trovi bloccato su alcune schede. Quello che devi fare è spostare la linea che fa self.set_cell(row, col, 0) dal blocco else in cui si trova attualmente. In effetti, puoi spostarlo completamente al di fuori del ciclo, se lo desideri (dal momento che è davvero necessario solo se sei backtracking dopo che nessuno dei valori per la cella corrente ha funzionato).Ecco quello che penso che questa sia la migliore disposizione del ciclo for (anche spostando il return False dichiarazione su):

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 

infine, che fissa il problema di visualizzazione richiede due modifiche. Innanzitutto, eliminare il condizionale in set_cell. Vuoi aggiornare il display sempre. Quindi, in update_textfield, spostare la chiamata delete all'esterno del blocco if in modo che avvenga sempre (lasciare insert sotto if). Questo fa sì che l'impostazione di una cella a zero cancellerà il valore precedente, ma non lo farà visualizzare un carattere 0 effettivo (non mostrerà nulla).

Penso che questo dovrebbe farlo. Nota che l'algoritmo che stai usando è ancora piuttosto lento. La risoluzione di a board I found on the internet in a quick Google search ha richiesto 122482 tentativi e più di 5 minuti, ma alla fine ha funzionato. Altre schede (in particolare quelle che richiedono 8 o 9 nei primi spazi aperti) potrebbero richiedere ancora più tempo.