• [Debian]LinuxでECLiPSe CLPをビルドする

    LinuxでECLiPSe CLPをビルドする手順を書きます。

    何でビルドするかというと、先日ECLiPSeのメイン開発者の Joachim Schimpf さんに「ECLiPSeのContributorになりたい」というメールを送ったら、「ビルド・インストール関連の作業でできることがたくさんあり、例えばDebian packageなど出来ればよい（今は./RUNMEという独自シェルスクリプトでインストールする）」と言われたので、その作業の一環としてやってます。ビルドのやり方を記事にまとめるのも立派なContribute作業だと思いますので以下に手順記載します。

    ちなみにただインストールするだけならばずっと簡単な手順があり、そのうち紹介します。

    ディストリビューション:Debian バージョン10.9
    ECLiPSe CLPのバージョン:7.0_54
    目標：ダウンロードしたソースから、root以外の全ユーザーがtkeclipseコマンドでtkeclipse起動・eclipseコマンドでeclipse起動できる状態までもっていく
    この作業でできないこと：
    COIN-ORのインストール
    CPLEXのインストール
    XPRESS-MPのインストール
    JAVAインターフェースのインストール
    GraphVizのインストール
    FlexLMのインストール
    MySQLインターフェースのインストール

    ディレクトリ構成やアーキテクチャ(以下の例では64bit)など、適宜自分の環境に読み替えてください。また、ソースをビルド・インストールする際はソースディレクトリのINSTALLファイルなど目を通しておいてください。

    以下はDebianをインストールした直後からの手順です。基本rootで作業してます。

    ECLiPSeダウンロードページ
    /usr/local/srcに移動し、wgetでECLiPSeのソースを取得し、解凍する
    0621_001

    build essential をインストールする
    0621_003

    mkdir /vol/Eclipse/thirdparty を作成し、ECLiPSeのサーバからtcltk.tgzを取得・解凍する（最新の8.6のライブラリだとコンパイルエラーとなるのでここで手に入る8.5を使用します）
    0621_004

    0621_005

    ディレクトリの名称をtcl8.5に変更します
    0621_006

    m4をインストールします(次のGMPのビルドで必要となる）
    0621_008

    GMPのソースを取得、解凍します。lzファイルの解凍のためにlzipインストールします。
    0621_009

    0621_010

    gmpのフォルダに入り./configureを実行
    0621_011

    makeを実行
    0621_012

    make checkを実行
    0621_013

    make instalを実行
    0621_014

    はじめにダウンロードしたEclipseのソースのフォルダに移動します。
    ECLIPSEARCH=x86_64_linux
    ECLIPSETHIRDPARTY=/vol/Eclipse/thirdparty
    を設定したのち、./configureを実行（詳しくは同じフォルダのINSTALLというファイル見てください）
    0621_015

    make -f Makefile.$ECLIPSEARCH を実行
    0621_016

    ./RUNMEを実行
    0621_017

    Enter押下
    0621_018

    Enter押下
    0621_019

    インストール先は/usr/local/binにしました。
    0621_020

    Enter
    0621_021

    tcl/tk用のパス設定を行います。多分このままで良いのですが、一応配置した/vol/Eclipse/thirdpartyに変更しました。
    0621_022

    0621_023

    0621_024

    不要となった圧縮ファイルを削除します。
    0621_025

    exitで一般ユーザーに戻り「tkeclipse」コマンドでtkeclipseが、「eclipse」コマンドでeclipseが起動するようになりました。
    0621_026

    0621_027

  • ECLiPSe の Nonogram Solver の解説

    ECLiPSe CLPのexampleページにあるnonogram solverを解析していて、大体理解したので説明します。（内部で regular expression constraintを使用しています。）
    nonogramは日本でいうところのお絵かきロジック、ピクロスです。

    ルールの説明は割愛します。

    プログラムの説明も細かいところ端折ってエッセンスの説明だけします。
    このプログラムの一番重要な部分は、それぞれの行列のヒントのリスト(例えば[3,3,2]など)から盤面を表すリストの制約を生成するline述語で、この内容がわかれば8割方理解したことになります。

    line述語にはヒントのリストと盤面1行分(or1列分)のリストを渡します。
    line述語内でfromtoを駆使してヒントからTableに怪しげなリストを生成しています。

    以下の例では、tkeclipseのコンソール？で
    length(Xs,15),line([3,2,3],Xs).
    と入力してステップ実行した結果です。これは、ピクロスの問題でいうところの、ヒントとして「3,2,3」が与えられた15マスの1つの行の制約をつける処理に相当します。

    このfromtoの説明も今回は割愛します。このプログラムではあまり良い使い方してないので他の例で学んだほうが良いです。fromtoなどのLogical Loopはかなり重要なのでいつか改めて解説記事書くと思います。

    このTableなのですが、fromtoの操作が終了した時点では図のような内容になっています（右の四角内）
    nono

    並べ替えて書くと以下の内容です（ここら辺ぐちゃぐちゃに登録してるのがこのプログラムの良くない≒テキトーなところなので見習わなくて良いです）
    [0,1,1]
    [1,1,2]
    [1,2,3]
    [1,3,4]
    [0,4,5]
    [0,5,5]
    [1,5,6]
    [1,6,7]
    [0,7,8]
    [0,8,8]
    [1,8,9]
    [1,9,10]
    [1,10,11]
    [0,11,11]

    このリストなのですが、オートマトンの状態遷移表を意味していて、盤面のリストを左から読み込んでいった際の状態の変遷を記述してます。
    3つある数字の意味は
    [読み込んだ数字(0 or 1), 現在の状態, 次の状態]
    を表していて、
    「現在の状態　で　0または1　を読み込んだら　次はどの状態になるか」
    をすべて書き出しています。

    状態を11個持つ以下のようなオートマトンが出来たことになります。便宜的に状態にqをつけました。
    automaton

    状態はq1から開始し、矢印に書いてある数字を読み込んだ際に次の状態に遷移します。
    矢印がない数字が入力された際はヒントの条件を破ってしまっているのでオートマトン不受理（エラー、制約違反）となります。
    q11の状態が最終状態（受理≒読み込み終わったときにこの状態であればOK）となります。

    状態遷移表が完成したのち、それをregularという術語に渡して実際の制約を作成しています。

    regularの説明です。
    Qsは状態のリストです。この例では15個数字を読み込むので、それぞれの読み込み時に対応したものとなります。作成したオートマトンから、上記の例だと最初の状態がq1、最後Qnがq11となります。
    与えられた盤面の1行(列)のリストに「現在の状態」「次の状態」の2つの変数を追加して
    [マス目の数字, 現在の状態, 次の状態]
    が1要素となるリスト（この例だと要素は15個）を作成しています。
    状態の部分にはQsの要素を順番に指定して以下のように隣の要素同士を関連付けています。
    nono_juzu

    そして、それぞれの要素に関し
    (Goal infers ac)@Module

    で実際の制約をつけるのですが、これが実際どのようにコールされているかというと、
    member([マス目の数字, 現在の状態, 次の状態], List) infers ac
    という呼ばれ方です。Listの中身はオートマトンの状態遷移表です。
    この操作で、[マス目の数字, 現在の状態, 次の状態]の3つの組が、オートマトンの状態遷移表の要素のいずれかの組み合わせに一致する（それ以外の組はありえない）という制約を設定しています。

    member(A,L)はご存知の通り「AはL内の要素の一つ」を表すprologの組み込み述語で、ECLiPSeの制約ではありません。
    ここで使用されている 「infers」というのがこのブログでも何度か触れたpropiaという仕組みで、任意のprologの述語（組み込み述語でも自作述語でも良い）をECLiPSeの制約に変換してしまうというすごい強力な仕組みです。memberは本来バックトラックを発生させてしまうため制約としては使用できないのですが、propiaを使用することにより「AはL内の要素」という意味の制約として機能するようになります。
    infers ac の acの部分は制約伝搬の際にどの程度絞り込むか（候補の枝狩り）の動作に関連します。
    acはarc consistency の略でアーク整合のことで、これは制約プログラミングの用語です。自分はぼんやりとしか把握してないのですがそのうちちゃんと理解したら記事書こうと思います。
    infersのマニュアルページ

    ちなみにECLiPSeは主にアーク整合アルゴリズムAC-3とAC-5を使用しているらしいです。

    制約を作るときにオートマトンを使用するというのは面白いアイデアで今後何らかの参考になるかもしれません。

    Nonogram Solverは今回解説したオートマトン使用したものの他にECLiPSeメイン開発者のJoachim Schimpfさんが作成したgecodeバージョンがあり、こちらのほうが記述が簡潔なのでそのうち解析してみたいです。

  • Prologの差分リスト(difference list)に関して

    差分リスト(difference list)の解説をします。

    まず初めにPrologの通常のリストの構造の解説から。

    Prologでは例えば[a,b,c,d]で表されるリストは、内部的には以下の形の木構造で表されています。

    20210512_normal_list

    左の要素に値が入っていて、右の要素には続く要素が入るリストが入っています。黄色のところ見るとわかるように、最後の要素が[]の空リストになっています。

    ここで、このリストそのものの後ろに何か新しい要素やリストを追加する方法を考えてみます。
    結論から言うと、Prologでは自由変数に値を設定すると固定化されバックトラック以外の方法では変更できないため、図の黄色の空リストが入っている変数の値を変更することが出来ず、「できない」 のです。

    appendという術語を用いて、append([a,b],[c,d],NewList).　のように記述するとNewListには[a,b,c,d]というリストが入りますが、前の方のリスト[a,b]はそのまま使用できず全要素コピーされています。

    述語appendの定義：
    append([], L, L).
    append([H|T], L, [H|R]) :-
    append(T, L, R).

    長いリストの後ろにリストを追加するときなどは、元のリストは全要素コピーされ、結構な無駄（リスト終わりまでたどり着く時間とコピーで使用されるメモリ資源）となります。

    ここで登場するのが差分リストです。
    差分リストは、上記で述べた通常のリストの黄色い部分を「空リストではなく、値を決定しない自由変数のままにした」リストのことを言います。

    20210512_difference_list

    当たり前ですが、黄色の変数に空リストを設定すると、通常のPrologのリストと全く同じになります（→差分リストを通常のリストに変換するのは簡単）
    青い部分を差分リストの頭部(Head)、黄色の部分を差分リストの尾部(Tail)と言います。

    差分リストの表現方法はいくつかあるようですが、自分は[Head,Tail]という表記を使用しています。
    最終要素の自由変数をTailとして表に引っ張り出してきます。

    無理やり図で表すとこんな感じです（便宜的に矢印つけました）
    20210512_difference_list2

    ちょっとわかりずらいので、ドット演算子をはしょって以下のように図示してみます。
    20210512_difference_list3

    この表現にすると、リストの後ろに新たなリストを追加するという操作が、「尾部の自由変数に追加したいリストを代入してやる」操作で行えることがわかります。これはappendによる1つ目のリストの全要素コピーが行われないため、高速です。

    注意点としては、「新しく追加するリストの最終要素も自由変数である必要がある」「その自由変数が結合後のリストの新たな尾部となる」ということです。以下で説明します。

    差分リストの結合は以下のような述語を用いて行います。
    append_difference_list([List1Head, List1Tail], [List2Head, List2Tail], [List1Head, List2Tail]):-
    List1Tail=List2Head.

    仮に
    List1:[a,b,c,d,自由変数1]
    List2:[e,f,g,h,自由変数2]
    とします（ちょっと表現変ですがニュアンスで）

    ①一番目と二番目の引数として以下のようにマッチングされます。
    20210512_difference_list_append1

    ②List1Tail=List2Head.　の記述により List1の尾部(自由変数1)にList2が設定され、List1が以下のようなリストになります。

    20210512_difference_list_append2

    ③3番目の引数として結合した差分リストを返します。

    実際は
    List1Tail=List2Head.の記述は述語を以下のような記述にすることにより省略できます。説明のためわざとこのような記述にしました。
    append_difference_list([List1Head, List2Head], [List2Head, List2Tail], [List1Head, List2Tail]).

    差分リストの具体的な使われ方なのですが、例えばSWI-Prologのfindall/4があります。
    これは通常のfindall/3で返ってくるリストを差分リストとして返すもので、リストの尾部が4番目の引数として返ってきます。

    私は以前スライドパズルのラッシュアワー(RUSH HOUR)のソルバーを作成したときにこのfindall/4を使用しました。
    ソースコード
    ドキュメントおよび実行結果

    詳細の解説は行いませんが、このソースコードでは幅優先探索というアルゴリズムを用いていて、ある局面から発生しうるすべての局面を生成するのにfindall/4を使用しています。結果を差分リストで取得することにより、幅優先探索キューの尾部にfindall/4で返された差分リストをそのまま追加することにより処理を効率化しています。

    差分リストが使用されている他の例は構文解析などで使用される DCG(Definite clause grammar)などがあります。SWI-PrologでDCGで何らかの述語（トークン？）を記述したのちlistingなどで定義を見ると、すべて差分リストの引数が追加された同名のprolog述語に変換されているのがわかります。

  • Project Euler 46

    久しぶりに解きました。
    あんまり良いプログラムではないけど…

    Problem 46(日本語)
    Problem 46(本家サイト)

    %problem 46
:-lib(ic).
solve:-
	PrimeMax is 100000,
	assert(max(PrimeMax)),
	make_list(PrimeMax,Lst),
	eratosthenes_sieve(Lst,PrimeLst), % エラトステネスのふるいによる素数列挙

	Prime1#::PrimeLst,
	Prime2#::PrimeLst,
	A#=Prime1*Prime2,
	A#=_*2+1, % Aは奇数
	indomain(A,min),
	(
		Prime#::PrimeLst,
		B#>0,
		(A-Prime)/2 #= B*B,
		
		labeling([B])->
		(
%			printf(output,"%d = %d + 2*%d^2\n",[A,Prime,B]),
%			flush(output)
			true
		);
		(
			labeling([Prime1,Prime2]),
			printf(output,"answer %d = %d * %d\n",[A,Prime1,Prime2]),
			flush(output),
			abort
		)
	),
	fail.

mk_lst([],_,[]):-!.
mk_lst([First|Rest],Th,[Rest]):-
	First>Th,
	mk_lst(Rest,Th,Rest).
mk_lst([First|Rest],Th,[First|Rest]):-
	mk_lst(Rest,Th,Rest).

% 2 ～ Idx までのリストを作成
make_list(Idx,List):-
make_list_sub(Idx,List,[]).

make_list_sub(1,Ret,Ret):-!.
make_list_sub(Idx,Ret,List):-
Idx1 is Idx - 1,
make_list_sub(Idx1,Ret,[Idx | List]).

% 素数列挙 エラトステネスのふるい
eratosthenes_sieve([],[]):-!.
eratosthenes_sieve([First | Rest],[First | Rest]):-
max(Max),
First * First > Max ,
!.
eratosthenes_sieve([First | Rest], [First | Ret]):-
erase_baisu(First,Rest,Rest1),
eratosthenes_sieve(Rest1,Ret).

erase_baisu(_,[],[]):-!.
erase_baisu(Base,[First | Rest],[First | Ret]):-
First mod Base =\= 0,
!,
erase_baisu(Base,Rest,Ret).
erase_baisu(Base,[_ | Rest],Ret):-
erase_baisu(Base,Rest,Ret).


    実行結果(回答伏せます)
    solve.
    answer XXXX = XXXX * XXXX
    Aborting execution ...

  • CHRをGPUで実行させる論文を読みました。

    Parallel Execution of Constraint Handling Rules on a Graphical Processing Unit
    という論文を読みました。
    リンク
    リンク切れている場合は論文名で検索してください。

    Constraint Handling Rulesの開発者のThom Fr¨uhwirth さん達が書いた論文で、CHRをGPU上で実行させる方法がCUDAのコード込みで書いてあります。

    Constraint Handling Rulesに関して自分がわかっているレベル(≒あまりわかっていない)で簡単に説明すると、CHRは基本的には記述された一連の制約を論理的に同等かつよりシンプルなものにしたり、何かに変換（自作の制約で書いた記述 → 組み込み述語のみ使用した記述に変換など）したりします。

    例えばECLiPSeではPropiaとは別にCHRを使用しても自作の制約が定義出来ます。

    まず以下の3種類のいずれかの構文でルールを記述しておきます。(これが自作制約となります)
    CHRには以下の3つしかルールがありません。
    ・simplification
    　　Head1,Head2 <=> Guard | Body
    ・propagation
    　　Head1,Head2 => Guard | Body
    ・simpagation
    　　Head1¥Head2 <=> Guard | Body
    （HeadもGuardもBodyも普通のPrologのCallable Termで書きます。
    GuardとBodyの部分は複数の述語を書いて良い。Headの部分は最大2つの述語のみ（ECLiPSeの場合。3つ以上が不可なのは以下に述べる述語のピックアップの際の効率の問題らしいです）→すみません訂正します。CHRの昔のライブラリでは2つのみでしたが、新しいECHライブラリでは3つ以上可能でした）

    動作の仕組みなのですが、上記で定義した制約を含む述語群を連言（=AND。カンマ区切りの普通のPrologの表現）で記述すると、CHRの機構はそれらの述語群の中から2つピックアップし、
    ・上記のHead1,Head2にパターンマッチ
    ・GuardがTrueとなる
    を満たすものを見つけると、以下のルールに従ってピックアップした2つの述語を「書き替えて」しまいます（これをfire[発火]と呼ぶ）そしてその際にBodyの実行可能な述語は実行してしまいます。
    また、Guardの部分は常時チェックされる番犬のような動作をしていて、例えばguardにnonvar(A)みたいな記述をしていた際、別の処理でAに何か値を設定した場合、その瞬間にGuardのチェックが通り対応するBodyが発火されます（ECLiPSeのsuspend機構を使って実装されている）
    simplificationの場合はBodyに書き換え
    propagationの場合はHead1,Head2そのままでBodyの述語を追加
    simpagationはHead2のみBodyに書き換え(Head1は残す)

    上記の変換を適用できるルールがなくなるまで繰り返す（2つ述語ピックアップ→Head1,Head2にマッチングするかチェック→GuardがTrueかチェック→ルールに従いHead1,Head2を書き換え）
    どうも書き換え中のルール群をconstraint storeと呼んでいるようです。

    ちなみに上記一連の処理中にはバックトラックは発生しません。
    CHRの動作を「コミッテドチョイス」と言うらしいのですが、CHRの機構がどの述語をピックアップするか勝手に決めるのでプログラマはコントロールできない（選択を委託する）という意味かもしれません。
    また、Headの部分は２つじゃなくて1つでも良いです。

    CHRは基本的には上記の書き換えを行うのみなので、用途は特に制約の表現のみにとどまらず、サンプルを見ると
    　最大公約数の計算
    　ガウスの消去法
    　高速フーリエ変換
    　マージソート
    など、色々な応用があります。

    めちゃめちゃ端折ってますが上記がCHRの基本動作です。

    記述した制約群をどのような組み合わせでピックアップ・変換したとしても必ず最終的に生成される述語群が同じになるようなとき、Confluence（合流）性を持つと言うそうです。

    Confluence性はどのようにすれば担保されるかなのですが、以下の論文に書いてありますが自分はまだ理解できていない（論理学の用語がたくさん使用されてて難しいため）どうも冗長なルールを追加することにより合流性が担保されるようです。

    Theory and practice of constraint handling rules
    リンク切れしている場合は論文名で検索してください。

    Confluence性を満たす場合CHRが並列処理に非常に向いているとのことで、理屈では確かにそうだなと自分も納得しました。

    前置きが長くなりましたが、上記を踏まえたうえでGPUでCHRを使った上記の論文を読んだわけです（GPUは数千コア積んでいるものもあり単純な計算を同時に行うのに非常に有力）
    論文の内容はCUDAコードが実際に記載されていて実装イメージがしやすいものでした。
    しかし、ルールの述語自体をCUDAコンパイル用のコードで書いているため、あまり汎用性がないのではないという気がしました。
    使う側は当然任意の述語を使いたいのですが、論文のやり方ではそのたびに新たなプログラムをCUDA用に書いてコンパイルしなくてはならないのでは？と感じました。
    あまりGPUのことわかってないですが、if文を多用するプログラムは遅くなるなど、性能を100%出すためにいろいろ条件があるようです。
    現状ではCHRをGPUの速度を100%出し切って実行するのは難しいのかな、と感じました。
    ただ理論的にCHRのいろいろな性質が証明されているので、ハードウェア側でCHRに向いた実装が実現されたら、かなり望みがあるような気がします。

    余談ですが「CHRには3つしかルールがない」と書きましたが、
    ・simpagation
    　　Head1¥Head2 <=> Guard | Body
    の、
    ・simplification はこれの Head1 がないバージョン（Head2がBodyに書き換えられる)
    ・propagation はこれの Head2 がないバージョン(Head1そのままでBodyが追加される)
    となるので実質はsimpagationだけで良いみたいな文章をどこかで読みました。

  • labelingに関して

    制約論理プログラミングで必ず出てくるlabelingに関して説明しようと思います。
    だだーっとマニュアル見ないでいい加減に書くので多分嘘も書いてますが大体で読んでください。なるべくプログラム自体も書かない記述にします（めんどくさいので）

    概要的にはECLiPSe CLP のtutorialに書いてあることを抜粋して書くので英語読める人はそちらを読んでもらう方が絶対に良いです。とても分かりやすいです。
    ECLiPSeのtutorial

    制約論理プログラミングでは基本的なプログラムの構造は以下のような形になってます。
    １．制約の記述
    ２．解のサーチ
    ３．解の表示

    labelingというのはこれの2．解のサーチに相当します。

    labeling述語には制約変数のリストを渡します。
    例えば、（便宜的に整数のみ扱います。というか整数しか自分は扱い方が良くわかりません。）
    変数Aが１から３
    変数Bが１から３
    変数Cが１から３
    といった制約をつけた後、labeling([A,B,C])というような呼び出しをすると、A=1,B=1,C=1という解が設定されます。
    Prologをやっている人はピンとくると思いますが、labelingの呼び出しでバックトラックが発生し、failすると次のA=2,B=1,C=1という別解が設定されます。バックトラックするごとに制約を満たす解が順番に設定されます。

    ちょっと余談で、ECLiPSe CLPの資料を読んでるとことあるごとに口酸っぱく書いてあるのですが
    「１．の制約の記述の部分は、バックトラックを発生させてはいけない」とのことです。制約の部分でバックトラックを発生させる作りにすると正確な解が得られないとのことです。
    バックトラックの有無がPrologの一般的な述語と制約論理プログラミングの制約の大きな違いだと思います。
    ですので、ECLiPSe CLPにもSWI-PrologのCLPFDにもたくさん制約用の述語が定義されてますが、そのどれもがバックトラックをしない述語になってるはずです。

    これもまた余談ですがECLiPSeには自分が任意に定義したPrologの述語を制約に変換することが出来るPropiaという仕組みがあり、とても便利です。これを使うとバックトラックを生成させてしまう術語がバックトラックを生成しない制約に変わります。

    話は戻って、labelingなのですが、既定では与えられた変数群の解を生成する際、
    ・リストの先頭の変数から順番に値を確定
    ・値はドメイン（取りうる範囲）の小さいほうから大きいほうへ
    決定しています。

    ただ、これが一番良いやり方かどうかはわかりません。
    SWI-PrologのclpfdでもECLiPSe CLPでも「どの変数の値を優先的に決定するか」「値をどのように設定するか」の2つの観点でいろいろなオプションが用意されてます。
    例えば以下の観点のオプションなどあります。
    ・一番ドメインの範囲（取りうる値の範囲）が小さい変数から決定する
    ・値を中央から外側に向かうように設定する
    ・値をランダムに設定する

    SWI-PrologのCLPFDではここまでの話でlabelingに関しての説明は完了なのですが、ECLiPSe CLPはこのlabelingの部分を完全にプログラム制御できます。tutorialのTree Search Methodの項を見てください。

    まずlabelingを使用せずに、1つの制約変数を指定して、
    indomain(変数)という書き方ができます。
    これは変数の取りうる値を小さいほうから順に設定してfailするたびバックトラックをさせるという、labelingの1変数バージョンのような述語です。そしてindomainの2番目の引数にオプションを渡すと、いろいろな順番で値を決めることが出来ます（大きい順、ランダム、真ん中から、etc…）

    また、deleteという紛らわしい名前の述語があるのですが、これにfirst_failなどのオプションを指定して制約変数のリストを渡すと、指定したオプションに応じたやり方で1つ変数を取り出し、それ以外の変数をRestに返してくれます。
    first_failの場合はリスト内の一番ドメインが少ない変数を選択し、残りをRestで返します。
    （「次に値を決める変数の選択」を行ってくれる述語）

    ECLiPSeではこのdeleteとindomainを駆使して、細やかに変数のラベリングをコントロールできます。ECLiPSeのtutorialには、これらを使用してN-Queenの問題をいろいろなラベリング方法で解き、発生したバックトラックの回数を計測するという興味深い記事が出てますので是非読んでみてください。

    あとsearch/6という似たようなことする術語もあるのですがまだよくわかってません。
    あとECLiPSeでは整数以外の値が扱えるのですが、そのときにindomainの実数バージョンのようなlocateという術語があるのですが、これもまだ詳細に使いこなせてません。

    これ読んでる方もぜひ一緒に勉強しましょう（そして教えて下さい）

  • DOMINO PUZZLEソルバーの解説

    ここ最近、勉強で ECLiPSe CLPのExampleページのドミノタイル問題ソルバーのソースを解析していました。大体理解したので解説したいと思います。

    問題の解説：
    0-0、0-1、0-2…..6-6 の全部で28枚のドミノタイルがある。
    tiles

    このタイルが横８×縦７の長方形の中にランダムに敷き詰められている。
    縦、横、左右逆、上下逆のどの置き方でも良い。

    どのように置いたかは不明で、並べた結果全体の数字が以下のようになっていた場合、タイルがどのように配置されていたかを解け。
    3 1 2 6 6 1 2 2
    3 4 1 5 3 0 3 6
    5 6 6 1 2 4 5 0
    5 6 4 1 3 3 0 0
    6 1 0 6 3 2 4 0
    4 1 5 2 4 3 5 5
    4 1 0 2 4 5 2 0

    プログラムの解説：

    プログラムの概要を説明します。
    ①述語one_by_two_tiling/4でLeftとUpというマス同士の接続状態を表す配列を作成、制約を設定します。

    Leftの配列は以下の色のついた部分の接続状態を表す2次元配列です。
    1つのドミノタイルとしてつながっていれば１、つながっていなければ０になります。
    lefts

    Upは以下の色のついた部分の接続状態を表す2次元配列です。
    Ups

    制約のつけ方なのですが、あるマスに注目し上下左右の接続状態を考えたとき、必ず上下左右のいずれか1つの方向のみ接続されていることになるので、そのような制約を設定します（上下左右の変数の和が１）

    ②２つのdo文で、隣接した2マスに注目しながら、「2つの数字-対応する接続変数」の組み合わせをどんどんリストに集めます。このとき、タイルは数字が小-大の順番になるようにして保存します。
    その部分にタイルが配置されていた場合は、該当する接続状態の変数が1になるというわけです。

    scan
    ヨコ方向の隣接マスに注目した後は、タテ方向で同様の操作を行います。どちらも同じ配列にまとめます。
    このようにまとめると当然 (1,4)-変数 というような組み合わせが複数見つかりますが、いくつか見つかった中のどれか1つの組み合わせだけが実際に配置されているタイルの情報だということになります。

    ③まとめた配列をkeysortでソートします。タイルごとにまとまります。

    ④group_same_key_values/2で、ソート後の
    […(1,4)-接続状態変数1,(1,4)-接続状態変数2,(1,4)-接続状態変数3,(1,5)-接続状態変数4,(1,5)-接続状態変数5…]
    のような状態のリストを
    […(1,4)-[接続状態変数1,接続状態変数2,接続状態変数3],(1,5)-[接続状態変数4,接続状態変数5]…]
    のような形式にまとめます。

    ⑤
    [接続状態変数1,接続状態変数2,接続状態変数3]　の和が１
    [接続状態変数4,接続状態変数5]　の和が１
    というような制約を設定します(foreach)

    ⑥term_variableで全変数を1つのリストにまとめた後labelingですべての接続状態変数の解を探します。

    ⑦
    prety_print出力結果：
    pretty_print

  • 四角に切れ（パズル）を解くプログラム

    昔いくつか書いたPrologのパズルソルバーのコードがリンク切れになってたので再掲します。

    今回は四角に切れ（パズル）のソルバーです。

    プログラム
    解説と実行結果

    これも数年後、英語のStackOverFlow で以下の ECLiPSe CLP で書かれたプログラムを発見しました。
    ECLiPSe の開発メンバーのjschimpfさんのコードですね。
    ECLiPSeで書かれた四角に切れソルバー

  • RUSH HOUR(パズル)を解くプログラム

    昔いくつか書いたPrologのパズルソルバーのコードがリンク切れになってたので再掲します。

    今回はラッシュアワーというパズルを解くプログラムです。

    プログラム
    解説と実行結果

  • ペントミノを解くプログラム

    昔いくつか書いたPrologのパズルソルバーのコードがリンク切れになってたので再掲します。

    今回はペントミノのソルバーです。

    プログラム
    解説と実行結果