制約論理プログラミング
有限領域(Finite Domains)は、有限集合について制約を扱う領域である。多くの制約充足問題はこの領域で表現することができる。変数の値として有限領域の要素をとるもので、特定の範囲内の整数などがその代表である。個々の変数について、例えば1から5までの整数であれば X::[1..5] (あるいは X::[1,2,3,4,5] )のように領域が指定される。数値以外であれば X::[george,mary,john] のような形になる。 有限領域での制約としては算術式による制約や記号的制約などが使われ、言語により指定方法は異なる。以下は古典的な覆面算 SEND+MORE=MONEY を解くプログラムの例である。
有限領域では、制約の一貫性チェックにより各変数の取りえる領域が変化した場合、その変化を制約伝播により他の関連する変数の領域に反映し、解の範囲を順次狭めていくことで最終的な解を求めることが多い。全体の一貫性が取れなくなった場合はバックトラックを行い途中からやり直す。
論理プログラミングでは任意の有限木(tree)を表す項(term)を基本データとしているため、制約論理プログラミングでも木は基本的な計算領域として扱うことができる。ユニフィケーションによる等号制約(=)が基本的な制約である。項は以下の再帰的な定義で表される。
任意の定数 c は項である。
任意の変数 X は項である。
任意の関数記号 f と複数の項からなる複合項 f(t1, .. ,tn) は項である。
例えば、f(X,g(a,b,h(Y))) は項である。データの並びを表すリスト(例: [1,2,3] )も先頭要素と残りの要素の2つの引数からなる項の特別な表現方法と見なすことができる。
制約論理プログラミング言語のProlog IIIは無限木の等号制約と不等号制約を扱うことができる。