5

私は宿題のために数独パズルソルバーをやっていますが、いくつかの困難に直面しています。コードは現在、ソリューションを循環しますが、簡単なパズルでは到達し、難しいパズルでは、明らかな理由もなく、いくつかの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
4

1 に答える 1

4

あなたが抱えている問題は、再帰呼び出しの一部が結果を適切に返さないことです。そのため、ソリューションが見つかった場合、再帰スタックの数レベル上で忘れられてしまいます。これがあなたが必要とする最初の修正であり、でreturn行われた再帰呼び出しに追加され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

solve_helperまた、事前に解決されたセルをスキップする関数の特殊なケースでも同様のものが必要です。関数の終わりは次のようになります。

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

編集：

わかりました。コードにさらにいくつかの問題が見つかりました。そのうちの2つはソルバーの論理的な問題であり、1つは、ソルバー中に奇妙に見える以外に実際の問題を引き起こさない表示の問題です。

問題：

  1. まず、最新のコードではsolve_helper、を呼び出すのではなく、それ自体を呼び出していmoverます。これにより、移動する前に追加の関数呼び出しが必要になります（ただし、実際にはソルバーが壊れない可能性があります）。
  2. 次に、solve_helperセルを9に設定した後、バックトラックで（後のセルを解決できなかった後）、さらにバックトラックする前に9がゼロにリセットされません。
  3. そして最後に、表示の問題です。セルを0に設定しても、古い値の表示は停止しません。これは＃2の問題とよく似ていますが（バックトラック後に9が残されています）、実際には表面的なものにすぎません。

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

2番目の問題はもう少し複雑で、これはいくつかのボードで立ち往生しているところです。あなたがする必要があるのは、それが現在self.set_cell(row, col, 0)あるブロックの外にある行を移動するelseことです。実際、必要に応じて、実際にはループの外に完全に移動することができます（後でバックトラックする場合にのみ本当に必要なので）現在のセルの値はどれも機能しませんでした）。これがforループの最良の配置であると私が思うものです（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移動して、常に発生するようにします（を下に残します）。これにより、セルをゼロに設定すると前の値が消去されますが、実際の0文字は表示されません（何も表示されません）。deleteifinsertif

私はこれがそれをするべきだと思います。使用しているアルゴリズムはまだかなり遅いことに注意してください。インターネットで見つけたボードをグーグルですばやく検索して解決するには、 122482回の推測と5分以上かかりましたが、ようやくうまくいきました。他のボード（特に最初のいくつかのオープンスペースで8秒または9秒を必要とするボード）はさらに時間がかかる場合があります。

于 2012-11-13T01:46:00.023 に答える