私は、1 つのことを除いてほぼ完成した再帰バックトラッキングを備えた数独ソルバーに取り組んでいます。パズル内のどこかに複製を配置すると (たとえば、上隅に 1,1)、解決可能なパズルでなくても、永遠に解決策を見つけようとする可能性があります。
どんな助けでも大歓迎です！
ロブ
質問する
470 次
5 に答える
2
バックトラックする方法は、パズルが矛盾にぶつかったときです。したがって、すべてのステップで「検証」メソッドを実行する必要があります。パズルが違法である場合、最後に行った手は違法です。
自分の動きが違法であることがわかったら、再帰的にバックトラックして続行できます。
また、これはかなり素朴なアプローチであることに注意してください。数独の専門家の中にはより良いアルゴリズムを持っている人もいるかもしれませんが、この力ずくでうまくいくはずです。
于 2013-03-19T15:26:26.633 に答える
2
無効な状況を検出したいので、ソルバーを呼び出す前に確認する必要があります。ソルバー自体は無効なソリューションを作成しません...
于 2013-03-19T15:28:40.373 に答える
2
重複については、セルごとに可能な番号のリストを保持することをお勧めします。セルを解決しようとするときは、このリストを一致する行、列、ボックスと比較して、重複の作成を防ぐことができます。これにより、後戻りせずに簡単なパズルを解くことができます。行き詰まったら、バックトラックを使用して続行します...
于 2013-03-19T15:35:32.987 に答える
1
これは必ずしも答えではありませんが、役立つはずです。以前にマクロ プログラムでこの種のことを行ったことがありますが、これは入手可能な中で最も評価の高いものでした。
数独ソルバーはかなりの挑戦になる可能性があります。動きが正しいかどうかを判断する唯一の方法は、それが絶対的なものか、後で証明されるかです。終わりは現在の状況と動きに基づいているため、これはかなりの挑戦につながる可能性があります. これは、これを順列として処理できることを意味します。各マスを調べて、可能な数字を見つけます。そこから、1 つまたは 2 つの定義済みの正方形を取得できます。これに基づいて、エンドポイントに到達する方法はたくさんあります。
「終点」は、パズルが解かれたとき (エラーなし - すべての四角が塗りつぶされたとき)、またはエラーが発生したときに定義されます。
これに基づいて、各移動をノードとして扱い、可能な移動を囲むツリー システムを構築できます。
例えば：
8 7 1 2 _ _ 6 9 3
2 9 6 3 8 7 1 _ _
これはほんの一例ですが、それに基づいて、各行をそれぞれスイープし、次に各列を使用して、可能な数値を生成できます。
(5, 1) -> [4, 5]
(6, 1) -> [4, 5]
(8, 2) -> [4, 5]
(9, 2) -> [4, 5]
これと私たちに与えられた解決策に基づいて、4 つの可能な解決策があることがわかります。
8 7 1 2 4 5 6 9 3
2 9 6 3 8 7 1 4 5
-また-
8 7 1 2 5 4 6 9 3
2 9 6 3 8 7 1 4 5
-また-
8 7 1 2 4 5 6 9 3
2 9 6 3 8 7 1 5 4
-また-
8 7 1 2 5 4 6 9 3
2 9 6 3 8 7 1 5 4
パズル全体を解決し、どれが「正しい」かを判断するには、それだけでは十分な情報ではありませんが、これを標準化して同様のシステムを作成し、すぐに解決策を見つけるために使用できます。
したがって、これら 4 つの可能性すべてをツリーに追加し、それぞれが元のブランチから分岐することができます。
8 7 1 2 _ _ 6 9 3
2 9 6 3 8 7 1 _ _
そしてそれらを再帰的に処理します。
お役に立てれば！
于 2013-03-19T16:01:54.710 に答える
1
Validate クラスを実装するValidate.validate();には、solve メソッド内に記述できませんでしたか? それが役に立てば幸い。
于 2013-03-19T16:50:18.220 に答える