このページではJavaScriptを使用しています。

9-2.制約論理

9-2-1.概要

AZ-Prologのユニフィケーションの仕組を拡張し、変数が値を束縛されたときに起動されるゴール=遅延実行ゴールの設定(freeze/2)、および変数が束縛されたときにチェックされる値の組を設定(put_clp_area/2)しユニフィケーションの真偽に反映する仕組みを作り、この上にPrologによる制約解消系の構築(拡張ライブラリ組込述語)をおこなったものです。
制約解消系は未完成です。順次充実を図っていきますのでご協力ください。

処理系の制約論理拡張は 『制約論理プログラミング (知識情報処理シリーズ 別巻2)共立出版(株)』を参考にしました。

9-2-2.組込述語

組込述語は基本ライブラリ(AZPrologの基本組込述語)と拡張ライブラリ組込述語の2種類があります。
後者が基本組込述語を用いてProlog言語にて書かれ、コンパイルされた制約解消系です。
基本組込述語
(1)決定性述語: freeze/2

変数が値を持ったときに起動される遅延実行ゴールを設定します。
詳細は述語リファレンスをご参照ください。

ゴールは同一変数に順次追加することができますが、遅延実行時においては決定性すなわちゴール(列)の最後にカットオペレータがついたものになります。
デバッグモードで起動し、ある変数が値をもったときtraceを開始させるspyの変形のような制約以外の用途でも使うことができます。
例:

|  ?-debug.
|| ?-freeze(X,trace),go(X).     % go(X) の実行の経過で、X が値を持ったときにtrace が開始される
(2)決定性述語: frozen/2

変数に設定さている遅延実行ゴールをユニファイします。
詳細は述語リファレンスをご参照ください。

(3)決定性述語: put_clp_area/2

変数に領域を設定します。既に領域が設定されている場合はANDになります。
第二引数はソートされていることが前提となる述語でコンパイルDLIB組込述語「in/2」の下層述語となります。
例:

| ?-put_clp_area(X,[1,2,5..7]),get_clp_area(X,L).
X       = X,
L       = [1,2,5..7]
yes
| ?-put_clp_area(X,[a,b,d,1,2,5..7]),put_clp_area(X,[b,2..6]),get_clp_area(X,L).
X       = X,
L       = [b,2,5,6]
yes
(4)決定性述語: rm_clp_area/2

既に領域が設定されている変数から指定領域を取り除きます。
コンパイルDLIB組込述語「notin/2」の下層述語です。(同等ではありません。)
例:

| ?-put_clp_area(X,[1..9]),rm_clp_area(X,4..7),get_clp_area(X,L). 
X       = X,
L       = [1..3,8,9]
yes
(5)決定性述語: get_clp_area/2

領域設定された変数で値が決定していない場合,領域を取得します。
コンパイルDLIB組込述語「indomain」などの下層述語です。
例:

| ?-X in 0..9,get_clp_area(X,L).
X       = X,
L       = [0..9]
yes
(6)決定性述語: clp_intersection/3

「put_clp_area/2」の補助述語で、2集合の共通部分を取得します。
例:

| ?-clp_intersection([1,3..6,9..12],[2..11],L).
L       = [3..6,9..11]
yes
(7)決定性述語: clp_is_member/2

「put_clp_area/2」「in/2」の補助述語で第一引数が第二引数のリストに含まれる場合成功します。
例:

| ?- clp_is_member(a,[1..9,b,c(z)]).
no
| ?- clp_is_member(a,[1..9,a,c(z)]).
yes
| ?- clp_is_member(7,[1..9,a,c(z)]).
yes
(8)決定性述語: system_get_min_max_int/2

処理系であつかう整数の下限と上限を取得します。
例:

| ?- system_get_min_max_int(MinInt,MaxInt).
MinInt  = -9223372036854775808,
MaxInt  = 9223372036854775807
yes
拡張ライブラリ組込述語
拡張ライブラリの読込み(dlib_require/1)で組み込まれる述語です。
 ?- dlib_require(clp).   
system/ext/clp/clp.plにprologソースで提供しておりますので、コンサルトでも使うことができ、ユーザーが手を加えることもできます。 ソースには下記以外にも定義述語がありますのでご参照ください。
(1)決定性述語: in /xfx

変数(リストに含まれる要素)に値を持つべき領域の制約を与えます。
詳細は述語リファレンスをご参照ください。

(2)決定性述語: notin /xfx

変数(リストに含まれる要素)に値が含まれない領域の制約を与えます。
詳細は述語リファレンスをご参照ください。

(3)決定性述語: alldifferent/1

引数リストに含まれる変数はすべて異なる値を持つという制約を与えます。
詳細は述語リファレンスをご参照ください。

(4)非決定性述語: indomain/1

制約変数の取りうる値を非決定的にユニファイします。
詳細は述語リファレンスをご参照ください。

(5)非決定性述語: labeling/1

与えられた制約に基づいて探索を行います。
詳細は述語リファレンスをご参照ください。

(6)決定性述語: #= /xfx

演算子の左右の数(式)の計算結果が等しいという制約を与えます。

(7)決定性述語: #\= /xfx

演算子の左右の数(式)の計算結果が等しくないという制約を与えます。

(8)決定性述語: #< /xfx

演算子の右の数(式)の計算結果が左の数(式)の計算結果より大きいという制約を与えます。

(9)決定性述語: #> /xfx

演算子の左の数(式)の計算結果が右の数(式)の計算結果より大きいという制約を与えます。

(11)決定性述語: #=< /xfx

演算子の右の数(式)の計算結果が左の数(式)の計算結果より大きいか等しいという制約を与えます。

(12)決定性述語: #>= /xfx

演算子の左の数(式)の計算結果が右の数(式)の計算結果より大きいか等しいという制約を与えます。

9-2-3.プログラミング例題

例題1.数独
ここでは、説明を簡単にするため、4X4マス(2X2の4ブロック)からなる数独の解法を説明します。
使われる制約組込述語は「in/2」「alldifferent/1」「labeling/1」の3述語です。
ヒントとして、4つのマスの値が示されているとします。
[ _,  1,    _,  _,
_,  _,    2,  _,
3,  _,    _,  _,
_,  _,    _,  4]
なお、「sample/clp/sudoku.pl」には通常の9x9はもちろん正の整数の平方根をもつN: NxNマスの解に一般化した例題がありますので、合わせてご確認ください。
:- dlib_require(clp).   % 拡張ライブラリをロードします
go:-     % 4x4の変数領域を作ります。マス目を左上から順に異なる変数で埋めます
         Vars = [X1, X2,  X3, X4,
                 X5, X6,  X7, X8,
                 X9, X10, X11,X12,
                 X13,X14, X15,X16],
                 
         % 各変数は1から4までの数値が入るという制約を与えます
         Vars in 1..4, 

         % 各行に含まれる変数はすべて異なる値を持つという制約を与えます
         alldifferent([X1, X2,  X3, X4]),
         alldifferent([X5, X6,  X7, X8]),
         alldifferent([X9, X10, X11,X12]),
         alldifferent([X13,X14, X15,X16]),

         % 各列に含まれる変数はすべて異なる値を持つという制約を与えます
         alldifferent([X1,X5,X9,X13]),
         alldifferent([X2,X6,X10,X14]),
         alldifferent([X3,X7,X11,X15]),
         alldifferent([X4,X8,X12,X16]),

         % 各ブロックに含まれる変数はすべて異なる値を持つという制約を与えます
         alldifferent([X1,X2,X5,X6]),
         alldifferent([X3,X4,X7,X8]),
         alldifferent([X9,X10,X13,X14]),
         alldifferent([X11,X12,X15,X16]),

         % ヒントとユニフィケーションして確定値を埋めます
         Vars =   [_,  1,   _,  _,
                   _,  _,   2,  _,
                   3,  _,   _,  _,
                   _,  _,   _,  4],

        % 以上の制約で探索を行います
        labeling(Vars),

        % 結果を表示します。
         write([X1,X2]),  tab(1),write([X3,X4]),nl,
         write([X5,X6]),  tab(1),write([X7,X8]),nl,nl,
         write([X9,X10]), tab(1),write([X11,X12]),nl,
         write([X13,X14]),tab(1),write([X15,X16]),nl.

| ?- go.
[2,1] [4,3]
[4,3] [2,1]

[3,4] [1,2]
[1,2] [3,4]

yes

※「数独(スウドク)」はニコリの登録商標(第3327502号など)で、日本では「ナンバープレース」と呼ばれることも多い。日本以外の国ではSudokuという呼称が一般的。

例題2.魔方陣

3X3魔方陣の解法を説明します。
使われる制約組込述語は「in/2」「alldifferent/1」「labeling/1」「#= /2」の4述語です。

なお、「sample/clp/magic.pl」にはNxNマスの魔方陣が解けるようになっています。
比較のため、通常のPrologコードの生成検査法によるプログラムも同梱しています。
生成検査法では、4X4魔方陣においては16の階乗=20兆とおりの組み合わせを試すことになり、最初の解を得るのでさえ相当の時間を要しますが、制約論理プログラミングでは、数分のうちに全解を求めることができます。
ただし、N=6以上では第一解でさえ相当の時間を要します。

:- dlib_require(clp).     % 拡張ライブラリをロードします
go:-
    Vars = [X1,X2,X3,     % 変数領域を設定します
            X4,X5,X6,
            X7,X8,X9],
    Vars in 1..9,         % 各変数は1から9までの数値が入るという制約を与えます
    alldifferent(Vars),   % 各変数はすべて異なる値をとるという制約を与えます
    15 #= X1+X2+X3,       % 第1行のマスの合計値が15になるという制約を与えます
    15 #= X4+X5+X6,       % 第2行のマスの合計値が15になるという制約を与えます
    15 #= X7+X8+X9,       % 第3行のマスの合計値が15になるという制約を与えます
    15 #= X1+X4+X7,       % 第1列のマスの合計値が15になるという制約を与えます
    15 #= X2+X5+X8,       % 第2列のマスの合計値が15になるという制約を与えます
    15 #= X3+X6+X9,       % 第3列のマスの合計値が15になるという制約を与えます
    15 #= X1+X5+X9,       % 左上右下対角線のマスの合計値が15になるという制約を与えます
    15 #= X3+X5+X7,       % 右上左下対角線のマスの合計値が15になるという制約を与えます
    labeling(Vars),       % 以上の制約で探索を行います
    write([X1,X2,X3]),nl, % 結果を表示します。
    write([X4,X5,X6]),nl,
    write([X7,X8,X9]),nl. 

| ?-go.
[2,7,6]
[9,5,1]
[4,3,8]
yes
例題3.覆面算
覆面算SEND+MORE=MONEYの解法を説明します。 使われる制約組込述語は「in/2」「 alldifferent/1」「labeling/1」「#= /2」「#\= /2」の5述語です。
「sample/clp/sendmore.pl」にソースがあり、比較のため通常のPrologコードで生成検査法によるプログラムも同梱しています。
:- dlib_require(clp).              % 拡張ライブラリをロードします
go:-
    Vars = [S,E,N,D,M,O,R,Y],      % 変数領域を設定します
    Vars in 0..9,                  % 各変数は0から9までの数値が入るという制約を与えます
    alldifferent(Vars),            % 各変数はすべて異なる値をとるという制約を与えます
    S #\= 0,                       % S は0ではないという制約を与えます
    M #\= 0,                       % M は0ではないという制約を与えます
            S*1000+E*100+N*10+D    % SEND+MORE=MONEY であるという制約を与えます
           +M*1000+O*100+R*10+E
 #= M*10000+O*1000+N*100+E*10+Y,
    labeling(Vars),                % 以上の制約で探索を行います
    write(Vars),nl.                % 結果を表示します。

| ?-go.
[9,5,6,7,1,0,8,2]
yes