数独パズルを解決するためのブルート フォース アルゴリズムの実装は、 1 ～ 9 の数字のいずれかを配置することが不正な動きになるセルが発見された場合に失敗します。
実装は C で書かれており、ボードは 9x9 配列で表されます。ソルバーは、9 から正当な数に到達するまでカウントダウンし、到達できない場合は、代わりにゼロを出力します。
ゼロは、入力されるセルも表します。ゼロの文字列 (空のボード) が入力である場合の出力 (切り捨てられた) は次のとおりです。
9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0
最後の 3 つのゼロがあるのは、以前に入力された値が変更されていないためです。ソルバーがこのように失敗しないようにするにはどうすればよいですか?
現在スポットにゼロを入力している場合は、代わりに、数字を入力した前のスポットに戻り、そのスポットの別の値の数字が見つかるまでカウントダウンを続けます。
たとえば、あなたの例では：
9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0
3 の下に 0 を入れる代わりに、戻って 4 の下に 6 を入れてみます。
すべての「動き」を正しい動きのように扱わないでください。たとえば、最後の 7 を配置しても問題ないように見えますが、次のセルに有効な移動が残らないようにします。したがって、「移動不可能」な状況になったら、戻って次のオプションを試してください。反復すると、ソリューションが得られます。
もちろん、より良い方法は、残りのオプションのセットが少ない場所に対してブルートフォースを開始することです。すべてのセルを実行し、残っているオプションの数が最も少ないセルでブルート フォースを開始します。すべてゼロで始めると、最終的には
9 8 7 6 5 4 3 2 1
6 5 4 0 0 0 0 0 0
3 2 1 0 0 0 0 0 0
これは合法であり、一度も後戻りすることはありません。
これを行うには、推測をスタックにプッシュします。ゼロを出力したくなるたびに、代わりに最後の答えをボードからポップして、そこからカウントを続けます。
したがって、(2,3) で 3 を推測し、次に (3,3) を見てゼロになった場合は、(2,3) に戻って 2 を試し、次に 1 を試してから、(2 の前にポップします。 、3)推測など