電子情報工学特別実験のページへ戻る
これとは若干異なる一つの方向性としては，
制約をあらかじめ固定した方向で使う
方法があります．
つまり，
各制約を
例えば，X + Y = 1000 という制約の場合， X = 1000 - Y, Y = 1000 - X と変形しておけば， Y(X)の値が決まった時にX(Y)の値を求めるための手続きとなります．
各オブジェクトがとり得る値の場合の数がさほど大きくない場合は，
「オブジェクトの値を決定(生成)する」制約をあらかじめ用いて，静的に，
「オブジェクトの値の候補の情報をすべて保持」
する方法が採れます．
これは各オブジェクトを値域付き変数として表し，
その要素を列挙することに相当します．
この場合「現在の解の候補を絞り込む」制約は， 「適さない解の排除」となり，「制約の充足性の検査」のみで行なえます． もちろん，解法の最中にも制約を「オブジェクトの値を決定(生成)する」方向でつかいます．
各オブジェクトの値は
[a,b,c,d] [a,e,c,f] [a,g,c,h]が解の候補であったとします． このとき，各候補において，1番めの項目と3番めの項目は共通です． よって，部分解として
[a,*,c,*]が得られます． ただし，* は未定を表すものとします．
基本的に一つの制約を介した隣接オブジェクト間の相互作用しか基本的に扱えません． また，その性質上どこかに解が一意に決まるところがないと， 制約を通じた解の伝播が起こらず，解を求めることができません． つまり，
また，制約伝播の源をつくるには， パズルに依存した発見的な知識を導入するとよいでしょう．
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)に次の候補がある)
}