ナンプレを解くプログラムを方法ごとに3つ作成した。今回はその中で全探索による解法を紹介する。
全探索という名前の通り,すべての組み合わせを試し,ナンプレのルールに矛盾しないものを見つけ出す方法である。アルゴリズムは次のようになる。
—– アルゴリズム —–
- 数値が確定していないマスに,矛盾しない数値を入れる。2.へ
- 次の空いているマスについても同様に,矛盾しない数値を入れる。3.へ
- 矛盾しない数値が存在する場合は2.へ,存在しない場合は4.へ
- 一つ前のマスに戻り,別の矛盾しない数値を入れる。3.へ
このアルゴリズムをC言語で実装した
ソースファイル →nan_solve_全探索.c
サンプルの問題データ → sample.txt
——— 2018/05/13 追記 ———-
ソースファイルとサンプルの問題データをGitLabに移動した。
https://gitlab.alprovs.com/alprovs/numberPlace-fullSearch
このコードをコンパイルして実行した結果を一応載せておきます
$ ./a.out ./sample.txt / 2 / / / / / 7 / 9 / / 1 / 2 / / 8 / / / / 8 / / / / / 5 / / / / / 1 / / / 7 / 9 / 5 / / / 6 / / / / / 2 / / / / / 4 / / / / 5 / / 8 / 3 / / 9 / 1 / / / / / 6 / 8 2 1 4 5 9 6 7 3 9 3 6 1 7 2 4 5 8 7 4 5 3 8 6 2 9 1 2 5 4 6 3 8 9 1 7 1 8 7 2 9 4 5 3 6 3 6 9 7 1 5 8 2 4 6 9 3 5 4 1 7 8 2 5 7 2 8 6 3 1 4 9 4 1 8 9 2 7 3 6 5
以上。
この方法はプログラムで実装するには簡単なのですが,解けるまでの時間はかなり遅いです。
通常の9×9であれば遅くても数秒あれば解くことができますが,16×16となると数日かかります。
ということで,次回はもっと早く解くことのできるアルゴリズムを紹介しようと思います。