数独の構成が有効かどうかを確認する簡単なアルゴリズムを知っている人はいますか?私が思いついた最も簡単なアルゴリズムは、(サイズnのボードの場合)擬似コードです。
for each row
for each number k in 1..n
if k is not in the row (using another for-loop)
return not-a-solution
..do the same for each column
しかし、もっと良い(よりエレガントな意味で)解決策があるはずだと私は確信しています。効率はまったく重要ではありません。
ベストアンサー1
数独のすべての制約を確認する必要があります:
- 各行の合計を確認します
- 各列の合計を確認します
- 各ボックスの合計を確認します
- 各行の重複した数字をチェックする
- 各列の重複した数字をチェックする
- 各ボックスの数字が重複していないか確認する
つまり、合計 6 回のチェックです。ブルート フォース アプローチを使用しています。
ボードのサイズ(3x3または9x9など)がわかっている場合は、何らかの数学的最適化を使用できます。
編集: 合計制約の説明: 最初に合計をチェックする (そして合計が 45 でない場合は停止する) 方が、重複をチェックするよりもはるかに高速 (かつ簡単) です。これにより、間違ったソリューションを簡単に破棄できます。