ブルートフォースバックトラッキングエラーを伴うPython Sudoku再帰

Question

私は宿題のために数独パズルソルバーをやっていますが、いくつかの問題に直面しています。コードは簡単なパズルのためにそれに達するが、解決策を過ぎて今サイクルするようになり、より難しいパズルの場合、明白な理由がなくても数個の9で固まってしまう。私はこれについて何か助けていただければ幸いです。 （check_cellはプレースメントが有効かどうかを判断します）

1. このコードではバックトラッキングが正しく実装されていますか？
2. どのようにソルバーがフリーズするのを止めることができますか？それは3行を解決し、その後、ほとんどの値を9に変更してフリーズします。

いくつかのコード：

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

あなたが抱えている悩みはあなたの再帰呼び出しのいくつかは、それが発見された場合、ので、あなたのソリューション、適切な結果を返すされていないいくつかのことを忘れてしまうことです

再帰的スタックをレベルアップします。ここではあなたが必要とする最初の修正はmoverで行われた再帰呼び出しにreturnを追加し、です：

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 

また、あなたは事前に解決した細胞を飛ばし、あなたのsolve_helper機能の特殊なケースで同様のものが必要。関数の終わりは次のようになります。

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

編集：

[OK]を、私は、コード内でより多くのいくつかの問題を発見しました。そのうちの2つはソルバーの論理問題であり、1つは解決中に奇妙に見える以外の実際の問題を引き起こさない表示問題です。

問題：

1. まず、あなたは最新のコードではなくmoverを呼び出すよりも、自分自身を呼び出すsolve_helperを持っています。これにより、移動する前に余分な関数呼び出しが必要になります（実際にはソルバーを壊さないかもしれないと思いますが）。
2. 第2に、solve_helperがセルを9に設定した後にバックトラックした場合（後でセルを解決できなかった場合）、バックトラックする前に0にリセットされません。
3. 最後に、表示の問題です。セルを0に設定しても、古い値は表示されません。これは＃2の問題とよく似ていました（バックトラック後に9秒が残っていますが）実際には化粧品です。

最初の問題は簡単に修正できます。代わりにmoverコールをsolve_helperコールに変更してください。それは実際にあなたが質問に入れた元のコードにあったものです。 solve_helperを直接呼び出すと、実際には間違った結果が得られることはありません（solve_helperは2回目に既に記入されたセルをスキップします）が、再帰の各レベルに不要な余分な関数呼び出しを追加します。

2番目の問題はもう少し複雑で、いくつかのボードにはまっています。あなたがする必要があるのは、それが現在入っているelseブロックからself.set_cell(row, col, 0)の行を移動することです。実際には、実際にはループの外に移動することができます。現在のセルの値のどれもが働かなかった後のバックトラッキング）。ここで私は、これはループのために（もreturn False文を上に移動）の最良の配置と思われるものである：

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 

最後に、表示の問題を修正すると、2つの変更が必要です。まず、set_cellの条件を取り除きます。常にディスプレイを更新したいとします。次に、update_textfieldのdeleteコールをifブロックの外側に移動して、常に起こるようにします（の下にinsertのままにします）。これにより、セルをゼロに設定すると前の値は消去されますが、実際の0文字は表示されません（何も表示されません）。

私はこれを行うべきだと思います。使用しているアルゴリズムはまだかなり遅いことに注意してください。 a board I found on the internet in a quick Google searchを解決すると、122482回の推測と5分以上の時間がかかりましたが、最終的には機能しました。他のボード（特に、最初のいくつかのオープンスペースに8または9を必要とするボード）はさらに長い時間がかかります。