パズル向け制約処理システム
目次
- パズル向け制約処理システム
- パズル解法の指針
- パズルのための局所制約伝搬
- 大域的な解の発見
- パズル解法アルゴリズムの一般的な枠組
電子情報工学特別実験のページへ戻る
この実験を数年間通じて行なうことにより何らかの知見が得られるかも知れませんが,
どのようなパズルにも適用できる制約処理システムの作り方はまだわかっておりません.
そこで,ここでは,そのような一般的なシステムではなく,
ある特定のパズルのみを解くシステムを考えます.
以下の手法を用いることが考えられます.
局所制約伝播では隣接するオブジェクト間の相互作用を利用しますので,
処理としては軽いのですが,大域的な解の決定には向きません.
そのため,未解決の部分が残る可能性があります.
このような大域的な部分をあつかうには,
生成・検査型のバックトラックアルゴリズムを用いて探索を行なうか,
もしくは,
大域的な局面で解を求めることができる発見的知識(ヒューリスティック)を用いるのが簡単でしょう.
本来の局所制約伝播方式では「制約を満足する解の生成」をどの変数に対してもできるようにするのですが,
これを行なうのは簡易型の制約解消システムをまるごと一つつくらないといけません.
簡易型の制約解消システムを作っていただく,というのでももちろん構いませんが,
かなりの労力を要します.
これとは若干異なる一つの方向性としては,
制約をあらかじめ固定した方向で使う
方法があります.
つまり,
各制約を
- 「オブジェクトの値を決定する」場面(生成)で使う場合
- 「現在の解の候補を絞り込む」場面(検査)で使う場合
に分け,手続き的に解けるようにあらかじめ変形しておきます.
例えば,X + Y = 1000 という制約の場合,
X = 1000 - Y, Y = 1000 - X と変形しておけば,
Y(X)の値が決まった時にX(Y)の値を求めるための手続きとなります.
各オブジェクトがとり得る値の場合の数がさほど大きくない場合は,
「オブジェクトの値を決定(生成)する」制約をあらかじめ用いて,静的に,
「オブジェクトの値の候補の情報をすべて保持」
する方法が採れます.
これは各オブジェクトを値域付き変数として表し,
その要素を列挙することに相当します.
この場合「現在の解の候補を絞り込む」制約は,
「適さない解の排除」となり,「制約の充足性の検査」のみで行なえます.
もちろん,解法の最中にも制約を「オブジェクトの値を決定(生成)する」方向でつかいます.
各オブジェクトの値は
- アトミックな値,すなわち,構造を持たない値.
例えば,数字など.
- 構造を持つ値.例えば,数字の組など.
が考えられます.
構造を持つ値の場合は,値についての部分解を考えることができることがあります.
例えば,解が4つの記号の組で表すことができて,
[a,b,c,d]
[a,e,c,f]
[a,g,c,h]
が解の候補であったとします.
このとき,各候補において,1番めの項目と3番めの項目は共通です.
よって,部分解として
[a,*,c,*]
が得られます.
ただし,* は未定を表すものとします.
局所制約伝播では
基本的に一つの制約を介した隣接オブジェクト間の相互作用
しか基本的に扱えません.
また,その性質上どこかに解が一意に決まるところがないと,
制約を通じた解の伝播が起こらず,解を求めることができません.
つまり,
- 複数の制約に跨って決まる解を扱う
- 制約伝播の源をつくる
ことは他の方法によらなければなりません.
制約の変形を行なうような制約解消システムでは,
複数の制約に跨って決まる解を見つけることができますが,実装が複雑になります.
そこで,
バックトラックによる生成・検査型アルゴリズム
を局所制約伝播と併用するといいでしょう.
また,制約伝播の源をつくるには,
パズルに依存した発見的な知識を導入するとよいでしょう.
以上述べてきた方法を大まかなアルゴリズムにすると以下のようになります.
ただし
- No はオブジェクトの数
- Ncan(i) はオブジェクト(i)の値の候補の数
- Nc は制約の数
です.
main()
{
for (i=0; i < No; i++) {
オブジェクト(i) の値の候補を列挙する
(各制約を「オブジェクトの値を決定する」手続きに変形したものによる)
}
初期状態で利用可能な発見的知識の適用
local_constraint_solver();
if (未解決) search(0);
}
local_constraint_solver()
{
do {
for (i=0; i < No; i++) {
for (j=0; j < Ncan(i); j++) {
for (k=0; k < Nc; k++) {
if (オブジェクト(i)の値のj番めの候補が制約(k)「検査方向」を充足しない) {
オブジェクト(i)の値のj番めの候補を削除
}
}
}
for (k=0; k < Nc; k++) {
制約(k)「生成方向」によりオブジェクト(i)に関する値のうち
確定可能な部分を決める
}
オブジェクト(i)のすべての候補に共通の情報を求め,
それを現在のオブジェクト(i)の値(部分解)とする
}
} while (いずれかのオブジェクトの値が変化した)
}
search(i)
{
do {
現在の状態の保存
オブジェクト(i)の候補の一つを仮定する
local_constraint_solver()
if (矛盾しない) {
if (i < No) { /* まだ未定部がある */
search(i+1)
} else {
/* 解が見つかった */
}
} else { /* 矛盾した */
保存しておいた以前の状態に戻す
}
} while (解がみつからない || オブジェクト(i)に次の候補がある)
}
このアルゴリズムの枠組を用いる場合は,以下の点を検討します.
- パズルの中に現れる未確定要素(パズルの解となる部分)を形式的に表現する.
同時に,解の候補を保持する方法も決める.
- パズルのルールを1で表現した未確定要素の間の制約として形式的に記述する.
- 2で表現した制約を,
「オブジェクトの値を決定する」手続きと
「オブジェクトの値の候補を絞り込む」手続きに変形する.
(一つの制約からこれら二つが得られることもあるし,
どちらか一方のこともある.)
- 3で得られた手続きを先のアルゴリズムの枠組に埋め込みプログラムする.
2で記述する制約はパズルのルールから得られるものがほとんどですが,
「このルールとこのルールを満足するためには,こうでなければならない」
というように複数のルールから得られる制約の中に有用なものがある場合もあります.
このような知識は大域的な局面で解を求めることができる発見的知識(ヒューリスティック)となります.
これらは,実際にパズルを解いているときに見つかった「解くためのコツ」から得られることが多いので,
まず,実際に対象となるパズルを手で解いてみることをお勧めします.
ヒューリスティックを得ることにより探索の範囲を大幅に枝刈りできることが多々あります.