パズル問題解法のアルゴリズム講座
応用編
バックトラックに制約伝播を組み込む
雑誌系パズル(ペンシルパズル)はコンピュータ等を使わずに、自力で解くというのが前提です。
雑誌系パズルの特徴的な構造は、局所的な部分に対して確定的に解を特定出来る部分を探し、それを何よりも優先する。
これによって、また新たな局所部分で解を特定出来るという状況が連鎖的に発生して、やがて総てのマス目が埋め尽くされるというのが一般的です。(制約伝播)
このようなパズル問題をあえてコンピュータに解かせてみようと試みた場合、単純には次の２通りの方法が考えられます。
(1) バックトラックによるアルゴリズムにそのパズル特有の条件から巧妙な枝刈りを組み込む。(バックトラック法)
(2) 局所的な確定解を連鎖的に求めるという自力で解く場合と同じ方法のプログラムを作る。(制約伝播法)
しかし残念なことに、(1)の方法は探索時間がかかりすぎる、(2)は最後まで解けない場合があるという事態に突き当たったりします。
必ずしも有効という訳ではありませんが、上の２つの方法を組み合せるとかなり効果的な探索が出来るようになります。
(3) バックトラックによる探索に局所的確定探索を組み込んでやる。(制約伝播を持つバックトラック法)
| (1)バックトラック | (2)確定探索 | (3)確定探索付き再帰 |
 |  |  |
| 探索量が多すぎる | 解けない時がある | このテーマの探索木 |
上図の探索木を見ても明らかに探索の空間を縮小しながらバックトラックを行う確定探索付き再帰が優秀であることが感じられます。このプログラムの基本型は、
int 確定探索()
{
for (未確定部分について) {
if (確定解がある) {
確定する;
再帰探索();
確定を戻す;
return 探索ルート後退;
} else if (可能な解が１つもない) {
return 探索ルート後退(矛盾あり);
}
}
return 矛盾なし;
}
void 再帰探索()
{
if (確定探索() == 矛盾なし) {
未確定位置を１つ探す;
if (総ての解が求まっている) {
解の表示と記録;
} else {
for (未確定位置の総ての可能性) {
仮定する;
再帰探索();
仮定を戻す;
}
}
}
}
void main()
{
再帰探索();
}
|
これは完全再帰型の記述で、関数呼び出しが複雑に絡み合います。
再帰の深さはマス目の数と同じなので、マス目の少ないパズル問題なら、これで良いのですが、マス目が多い場合だと、スタックオーバーのトラブルが発生する可能性があります。
そんな時は、再帰が深くならないように、スタックを自己管理する形式の記述が安全性が高く、しかも高速です。
この方法は、公開プログラム研究開発ノートの「お絵書きロジックを解く」を参照して下さい。
いずれにしても、重要となってくるのは確定探索部分の中身を作り上げることですが、処理の軽い大雑把なものでも充分に役目を果たしてくれる場合もあり、実行結果と相談して時間がかかりすぎる場合は、より精度の高い確定探索を組み込んでやる必要が出てきます。