0

深さ優先の「ブルートフォース」を使用してパズルを解く数独パズル ソルバーを Python で作成しようとしています。しかし、何度も再コーディングした後、同じエラーが何度も出てきます。

問題をできるだけ明確に説明するために最善を尽くします。これは深さ優先検索に関連する最初の問題であるため、明らかな何かが欠けている可能性があります。

以下は簡略化されたコードです (詳細が不要な場所では疑似コードと混合されています)。

def solvePuzzle(puzzle):
    <while the puzzle is still not solved>:
        <make a copy of the puzzle>
        <go through each unsolved box>: 
            <try to find the value of the box>
            <if the current solution is impossible, return to the parent branch>
        <if the copy of the puzzle is exactly the same as the puzzle now, no changes have been made, so its time to start branching into different possibilities>:      
            <pick a random box to guess the number of>
            <go through each possible value and run solvePuzzle() on that puzzle>:
                <if a solution is returned, return it>
                <else, try the next possible value>
    <return the puzzle>

それは私ができる限り削減されています-それでも少し読みにくい/混乱している場合は申し訳ありません.

何らかの理由で、作成されたパズルのコピーごとにプログラムを solvePuzzle() に設定した後でも、すべてのコピーが不可能であることがわかります (不可能とは、推測でエラーが発生したことを意味します)。すべての番号がテストされているため、これは不可能です。

十分に明確でない場合に備えて、完全なコード(約 50 行のコードのみ) を次に示します。

なぜこれがうまくいかないのか誰かが提案できれば、とても感謝しています。

ありがとうございました！

編集： 約束どおり、これが「isSolved（）」メソッドです。

4

1 に答える 1

3

問題はここにあると強く思います：

# Go through each possibility in the branch until one solution is found
clone = deepcopy(puzzle)
values = clone[index / 9][index % 9]
for value in values:
    clone[index / 9][index % 9] = value
    branch = solvePuzzle(clone)
    # If a list is returned, it worked! Otherwise, try the next possibility
    if isinstance(branch, list):
        return branch

これはclone、候補値ごとにコピーを変更し、矛盾が見つかった場合に半解決済みのパズル状態に復元しません。これを試して：

# Go through each possibility in the branch until one solution is found
values = puzzle[index / 9][index % 9]
for value in values:
    clone = deepcopy(puzzle)
    clone[index / 9][index % 9] = value
    branch = solvePuzzle(clone)
    # If a list is returned, it worked! Otherwise, try the next possibility
    if isinstance(branch, list):
        return branch
于 2013-07-25T00:16:59.307 に答える