|ハイブリッドOS|File System|ARM|Android|Java|制御システム|オープンシステム

 

技術者コラム

 
フォーム
 
第51回目:MATLAB学習(Part1)
2015-09-27
筆者:村田
 
こんにちは。
 
これからMATLABについて勉強した内容を掲載したいと思います。不定期ですがお付き合いいただければと思います。
 
 
 
第50回目:Prologでさめがめを解く(Part6)
2015-09-20
筆者:村田

こんにちは。

前回はボード上のコマを削除する述語を作成しました。それではボード上から削除可能なコマを探す方法を考えてみましょう。以下のようにコマが配置されていた場合、

+-+-+-+
|g|b|r|
+-+-+-+
|g|g|r|
+-+-+-+
|r|b|b|
+-+-+-+

削除可能なコマとしてどのようなものがあるでしょうか。まずひとつ。

gを消す: [(0, 0), (0, 1), (1, 1)] パターン①

他にもあと2つありますね。

rを消す: [(2, 0), (2, 1)] パターン②
bを消す: [(1, 2), (2, 2)] パターン③

削除可能なコマをここではパターンと呼ぶことにします。ボードを与えるといくつかのパターンを得ることができます。まずはボード上の先頭のコマからパターンを返す述語を考えます。

pattern(Board, PosList, Pattern) :-
  [(X,Y)|_] = PosList, %% ボード上の先頭コマを取り出す
  neighbor(Board, X, Y, [], Pattern), %% 隣接コマを探す
  length(Pattern, Len),
  Len > 1.  %% 隣接コマと自身を含めて2個以上あること

上の定義だけでは、例えば以下のように先頭のコマ"g"が隣接コマを持っていない場合に失敗(false)してしまいます。

+-+-+-+
|g|b|b|
+-+-+-+
|r|r|g|
+-+-+-+
|r|g|g|
+-+-+-+

失敗する場合は再帰して別のコマからパターンを探すようにします。先程のpattern/3の定義を残しつつ、別のpattern/3を以下のように定義します。

pattern(Board, PosList, Pattern) :-
  [(X,Y)|Tail] = PosList,             %% もう一度先頭を取り出す
  neighbor(Board, X, Y, [], DelTail), %% 先頭の隣接コマを
  subtract(Tail, DelTail, Tail1),     %% まとめて捨ててから
  pattern(Board, Tail1, Pattern).     %% 別のパターンを探す

このようにpattern/3を複数定義することで、Prologのバックトラック機能を利用することができます。最初の定義に失敗した場合に自動的に別の定義を試してくれます。あとはpattern/3のままでは使いにくいのでpattern/2のラッパーを用意しておきましょう。

pattern(Board, Pattern) :-
  poslist(Board, PosList),
  pattern(Board, PosList, Pattern).

では冒頭のボードでテストしてみましょう。

?- board(B), pattern(B, Pattern).
B = [[g, b, r], [g, g, r], [r, b, b]],
Pattern = [ (0, 0), (1, 1), (0, 1)] ; %% ;で次のパターンを探す
B = [[g, b, r], [g, g, r], [r, b, b]],
Pattern = [ (2, 0), (2, 1)] ;         %% ;で次のパターンを探す
B = [[g, b, r], [g, g, r], [r, b, b]],
Pattern = [ (1, 2), (2, 2)] ;         %% ;で次のパターンを探す
false. %% もう無い

ところでpattern述語の別案として、例えば[ [(0,0),(1,1),(0,1)], [(2,0),(2,1)], [(1,2),(2,2)] ]のように複数のパターンをリストにまとめて一度に返す方法も考えられます。Prolog以外で実装するならばこの方が良いでしょう。しかし、今回は意図的にPrologのバックトラック機能でパターンを探すようにしました。

さて、これで道具が揃いました。
convert_board/2 (ボードの並び順を変換する)
remove/3        (ボードからコマを削除する)
pattern/2       (削除可能パターンをバックトラックで求める)

インタフェースは解きたいボードを渡すと解となるコマの削除順を返すようにしたいと思います。まずはボードの並び順を変換しておきましょう。

answer(Board, DeleteOrder) :-
  convert_board(Board, ConvertedBoard), %% ボードを並び替えてから
  answer_sub(ConvertedBoard, DeleteOrder). %% 解く

では残りの道具を組み合わせて解を定義しましょう。

answer_sub(Board, [(X1,Y1)|DeleteOrder]) :-
  %% 削除できるパターンを一つ入手する
  pattern(Board, Pattern),
  %% ボードからパターンを削除する
  remove(Board, Pattern, RemainBoard),
  %% 削除パターンの先頭を削除順(解)に加える
  %% (convert_boardを実行したあとはX,Yが入れ替わっている点に注意)
  [(Y,X)|_] = Pattern,
  %% 結果が見やすいように1を足しておく (1から始まるように)
  X1 is X + 1,
  Y1 is Y + 1,
  %% 残りのコマを消す順番を得る
  answer_sub(RemainBoard, DeleteOrder), !.

answer_sub([], []). %% Boardが空なら削除する必要なし

これだけであとはPrologが解を見つけてくれます。それではanswerを使ってみましょう。

?- board(B), answer(B, Order).
B = [[g, b, r], [g, g, r], [r, b, b]],
Order = [ (2, 2), (3, 1), (1, 1)].

得られた解の通りに消してみて結果を検証してみます。なお、消すコマの下に^を示しました。

+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+
|g|b|r|    | | |r|    | | | |    | | | |
+-+-+-+    +-+-+-+    +-+-+-+    +-+-+-+
|g|g|r| -> | |b|r| -> | |r| | -> | | | |
+-+^+-+    +-+-+-+    +-+-+-+    +-+-+-+
|r|b|b|    |r|b|b|    |r|r| |    | | | |
+-+-+-+    +-+-+^+    +^+-+-+    +-+-+-+

他のパターンも試してみます。今度は4x4マスでやってみましょう。

?- answer([[g,b,r,g],[r,g,r,b],[r,b,g,b],[g,r,r,b]], Order).
Order = [ (1, 2), (2, 1), (2, 2), (1, 1), (1, 2), (2, 3), (1, 1)].

以下のように確かに解けました。少し回りくどい解ですが。

+-+-+-+-+    +-+-+-+-+    +-+-+-+-+    +-+-+-+-+
|g|b|r|g|    | |b|r|g|    | | | |g|    | | |g| |
+-+-+-+-+    +-+-+-+-+    +-+-+-+-+    +-+-+-+-+
|r|g|r|b| -> | |g|r|b| -> | |b|r|b| -> | |r|b| | ->
+-+-+-+-+    +-+-+-+-+    +-+-+-+-+    +-+-+-+-+
|r|b|g|b|    |g|b|g|b|    |g|g|r|b|    |b|r|b| |
+^+-+-+-+    +-+-+-+-+    +-+^+-+-+    +-+-+-+-+
|g|r|r|b|    |g|r|r|b|    |g|b|g|b|    |b|g|b| |
+-+-+-+-+    +-+^+-+-+    +-+-+-+-+    +^+-+-+-+

+-+-+-+-+    +-+-+-+-+    +-+-+-+-+    +-+-+-+-+
| |g| | |    | |g| | |    | | | | |    | | | | |
+-+-+-+-+    +-+-+-+-+    +-+-+-+-+    +-+-+-+-+
|r|b| | | -> | |b| | | -> | | | | | -> | | | | |
+-+-+-+-+    +-+^+-+-+    +-+-+-+-+    +-+-+-+-+
|r|b| | |    | |b| | |    | | | | |    | | | | |
+^+-+-+-+    +-+-+-+-+    +-+-+-+-+    +-+-+-+-+
|g|b| | |    |g|b| | |    |g|g| | |    | | | | |
+-+-+-+-+    +-+-+-+-+    +^+-+-+-+    +-+-+-+-+

このプログラムのように、"打てる手"をバックトラックで複数得られるようにしておくことで、"Prologに手順を考えさせる"ことができます。さめがめに限らず、8クイーンや数独、もっと難しいゲームでもPrologで解法を考える場合には有効な手法となります。

[おわりに]
「Prologでさめがめを解く」は今回で終わりです。4月に書き始めたPart1から結構時間がかかりましたが、お付き合い頂きありがとうございました。私は今回、初めてPrologに触れたのですが、関数やオブジェクトではなく、述語を扱う点やバックトラックの理解には慣れが必要でした。Webでサンプルコードを探し、実際に打ち込んで動きを見るのが効果的だと思います。あとは公式マニュアルの述語をとにかく適当に色々触って、Prologの雰囲気を感じるのも良いと思います。Prologは独特ではありますが、実際に触ってみると色々と発見がある、とても面白い言語です。興味のある方は是非お試しあれ。

以上。
 
ソースコードを掲載します。
 
第49回目:Prologでさめがめを解く(Part5)
2015-08-30
筆者:村田

こんにちは。

カニ坂RockFesという地元福生の音楽イベントに遊びに行ってきました。多摩川河川敷で開催され、今年で32回目だそうです。雨が心配でしたが、なんとか曇空をキープしてくれました。夏の終わりにしては涼しすぎる週末でしたが熱い演奏を楽しみました。メインステージのバンド演奏だけでなく、小さなテントでフォーク演奏もやっていて、これもまたフェスっぽくて良かったです。

さて、さめがめの続きなのですが、前回のプログラムにはバグがありました。どういうことか、前回作ったneighbor/5をテストしてみましょう。

?- board(B), neighbor(B, 0, 0, [], N).
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (0, 0), (1, 1), (0, 1)]

と、ここまでは良かったのですが、実は上記結果はバックトラックします。一つ目の結果が出力された後、";"を入力すると次の結果が表示されます。

?- board(B), neighbor(B, 0, 0, [], N).
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (0, 0), (1, 1), (0, 1)] ;        %% <- ここで";"を入力
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (1, 1), (0, 1)]                  %% <- バックトラック

2つ目の結果は誤った答えです。neighbor/5は指定したコマの隣接コマを返してくれる述語ですが、複数の答えはあり得ず、答えは一つでなければなりません。なぜこうなってしまうのか。バックトラックについてはPart1でも少し触れていますが、もう一度復習しましょう。例えば以下のような述語familyがあった場合、

family(sazae).
family(masuo).
family(tarao).

家族は何か?の問いの答えをバックトラックで求めることができます。

?- family(X).
X = sazae ;  %% <- ";"を入力
X = masuo ;  %% <- ";"を入力
X = tarao.

Prologがsazaeという答えを見つけてくれた後、他にもfamily(X)を満たすXが無いか探しにいってくれるのがバックトラックです。

では、neighbor/6の定義のどこに原因があるのが見てみます。例えばneighbor/6呼び出し時の第1引数が"l"の場合に、

neighbor(l, Board, X, Y, Crumb, Neighbor) %% ①

という定義①にパターンマッチするだけでなく

neighbor(_, _, _, _, Neighbor, Neighbor). %% ②

という番兵用に用意していた定義②にもマッチしてしまいます。②は①がマッチしなかった場合に、エラーとならないように定義したものです。しかし、バックトラックが動いてしまったことで、①にマッチしたにもかかわらず、②にも余計にマッチしてしまうという問題が発生したのです。"_"は何にでもマッチしてしまうので、こういう思わぬバックトラックを引き起こしやすいので要注意です。

それでは対処を考えます。②の定義は番兵としての役割があるので削除するわけにはいきません。バックトラックを抑制することで対処したいと思います。バックトラックは「カット」という"!"記号を用いることで抑制することができます。例として、先のfamily定義を以下のように直してみましょう。

family(sazae).
family(masuo) :- !.  %% <- カットしてみる
family(tarao).

すると以下のように

?- family(X).
X = sazae ;
X = masuo.

sazaeにマッチした後はバックトラックしてmasuoにもマッチしますが、masuoにマッチした後はバックトラックが抑制され以降のマッチは発生しなくなります。

カットを理解したところで、neighborのどこにカットを入れるのが良いでしょうか。以下のようにneighbor/6の最後にカットを入れてみましょう。これで適切なNeighborが見つかった後にバックトラックしてしまうことを防げます。

%% 左側に同じコマがあるかチェック
neighbor(l, Board, X, Y, Crumb, Neighbor) :-
  X1 is X - 1,
  not(member((X1,Y), Crumb)),
  piece(Board, X, Y, P),
  piece(Board, X1, Y, P),
  neighbor(Board, X1, Y, [(X1,Y)|Crumb], Neighbor), !.

これは素直な対処でわかりやすいですが、neighbor(r, ...)、neighbor(u, ...)、neighbor(d, ...)にも同様にカットを入れる必要があります。それよりも以下のようにneighbor/5にカットを入れれば1箇所の修正で済みます。

%% 上下左右に同じコマがあるか再帰チェック
neighbor(Board, X, Y, Crumb, Neighbor) :-
  neighbor(l, Board, X, Y, Crumb, Crumb1),
  neighbor(r, Board, X, Y, Crumb1, Crumb2),
  neighbor(u, Board, X, Y, Crumb2, Crumb3),
  neighbor(d, Board, X, Y, Crumb3, Neighbor), !.

なお、どこにカットを入れるべきかを判断するのは慣れないと難しいかもしれません。いくつかカットを入れてみて動きを観察したり、バックトラックがどういう経緯で発生したのかをじっくり考えることが大切です。では修正版neighbor/5をテストしてみましょう。

?- board(B), neighbor(B, 0, 0, [], N).
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (0, 0), (1, 1), (0, 1)].

今度はバックトラックせずに唯一の解を見つけてくれました。

ここまでで隣接コマをリストで取得することができるようになりました。ところで、隣接コマは[(0, 0), (1, 1), (0, 1)]のようにXY座標で表現されているのに対し、ボード上のコマは[[g, b, r], [g, g, r], [r, b, b]]のようにコマの色で表現されています。ボード上のコマもXY座標で表現できるようにしましょう。(次回の記事で使う予定です)

インタフェースは盤面(Board)をもらって座標リスト(PosList)を返すようにします。

poslist(Board, PosList) :- ...

この述語はBoardが2次元配列ですので、2重ループ構造になります。まずは内側の列(X)に対するループから書くと考えやすいでしょう。コマを座標に置き換えるわけですが、順番に置き換えるので、X座標もY座標もループのインデックスそのものです。したがって引数からもらうようにしましょう。それと、以下の第1項のパターンマッチを[_|T]とし、H要素を捨てている理由は、コマ自身が何か(r/g/b)は座標に関係ないためです。

poslist([_|T], X, Y, [(X,Y)|PosList]) :-
  X1 is X + 1,
  poslist(T, X1, Y, PosList). %% Xインデックスを増やしながら回す
poslist([], _, _, []). %% 末尾[]にマッチする番兵

次に外側の行(Y)に対するループを考えます。

poslist([H|T], Y, PosList) :-
  poslist(H, 0, Y, PosList1), %% 各行は上で定義したposlist/4を使用
  Y1 is Y + 1,
  poslist(T, Y1, PosList2),
  append(PosList1, PosList2, PosList).
poslist([], _, []).

ポイントは最後にappendを使う点です。簡単な例でその必要性を考えてみます。List1=[1,2,3], List2=[] としたとき、appendを使わず[List1|List2]とするとどうなるでしょうか。

List = [List1|List2].
List = [[1,2,3]].

このようにListは2次元リストになってしまいます。appendを使うと

append(List1, List2, List).
List = [1,2,3].

このように1次元リストになります。今回は盤面上のコマの位置を1次元リストで欲しいのでappendを使います。おっと、poslistの呼び出し口となるposlist/2の定義が途中でした。

poslist(Board, PosList) :-
  poslist(Board, 0, PosList). %% Y=0からループ開始

それではテストしてみます。

?- board(B), poslist(B, L).
B = [[g, b, r], [g, g, r], [r, b, b]],
L = [ (0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (..., ...)].

Prologが長いリストを省略表示していますが、最初の6つくらいを見ると3x3ボード上のコマをXY座標で表していることが分かると思います。

最後はボードからコマを削除する述語を作ります。コマはリストで与えることにします。まずはインタフェースを考えます。

remove(Board, DeleteList, RemovedBoard) :-

こちらも行と列の2重ループ構造になります。列(X)のループを考えましょう。まずは削除リストに含まれない場合の定義を見てください。

remove([H|T], DeleteList, X, Y, [H|RemovedLine]) :-
  not(member((X,Y), DeleteList)), %% 削除リストに含まれない
  X1 is X + 1,
  remove(T, DeleteList, X1, Y, RemovedLine).

not(member(...))によって削除リストに含まれない場合は、第1項のHを戻り値である第5項に含めてます。すなわち削除しないということです。次に削除リストに含まれる場合の定義を見てください。

remove([_|T], DeleteList, X, Y, RemoveLine) :-
  member((X,Y), DeleteList), %% 削除リストに含まれる
  X1 is X + 1,
  remove(T, DeleteList, X1, Y, RemovedLine).

こちらは第1項のHを第5項に含めず、削除しています。行末の番兵も定義しておきましょう。

remove([], _, _, _, []).

どんどんいきます。行(Y)のループを書いてみます。

remove([Line|TailBoard], DeleteList, Y, [RemovedLine|RemovedBoard]) :-
  %% 行の中の削除対象コマを削除する
  remove(Line, DeleteList, 0, Y, RemovedLine),
  Y1 is Y + 1,
  remove(TailBoard, DeleteList, Y1, RemovedBoard). %% 次の行へ
remove([], _, _, []). %% ボード終端にマッチする番兵

こちらは変数名を[H|T]よりも分かりやすい名前にしました。忘れずに行ループの入り口となるremove/3も定義しておきましょう。

remove(Board, DeleteList, RemovedBoard) :-
  remove(Board, DeleteList, 0, RemovedBoard).

ではテストしてみます。いつもの3x3ボードに対し、"g"の位置を手動で指定して削除してみましょう。

?- board(B), remove(B, [(0,0), (0,1), (1,1)], R).
B = [[g, b, r], [g, g, r], [r, b, b]],
R = [[b, r], [r], [r, b, b]]

"g"を削除できたようですね。さて一見うまくいっているようですが、これでは不十分です。さめがめのルールを思い出しましょう。縦一列の全てのコマが消えたら、その列の右側のコマが左にスライドするのでした。これをremove/3で表現したいのです。今のコードのままで、例えば1行目が全て消えたとしましょう。

?- board(B), remove(B, [(0,0), (1,0), (2,0)], R).
B = [[g, b, r], [g, g, r], [r, b, b]],
R = [[], [g, g, r], [r, b, b]]

結果(R)の1個目が空リストとして残ってしまうためにスライドしていません。というわけで空リストを削除しましょう。リストから要素を削除するdelete/3という述語があります。

?- delete([1, a, 3], a, R).
R = [1, 3].

これを使ってremove/3の最後で[]を除去してみましょう。

remove(Board, DeleteList, RemovedBoard) :-
  remove(Board, DeleteList, 0, RemovedBoard1),
  delete(RemoveBoard1, [], RemoveBoard).

もう一度同じように1行目を全て消してみます。

?- board(B), remove(B, [(0,0), (1,0), (2,0)], R).
B = [[g, b, r], [g, g, r], [r, b, b]],
R = [[g, g, r], [r, b, b]]

削除後にきちんとリストが縮まり、さめがめのスライドのようになりました。

今回はここまでにします。それにしても猛暑から一転、涼しいというか肌寒いくらいですね。皆さん風邪など引かぬよう。

以上。
 
カニ坂RockFes
2015-08-30
 
第48回目:Prologでさめがめを解く(Part4)
2015-08-17
筆者:村田

こんにちは。

夏休みを取られた方、リフレッシュできましたか?今週もとにかく暑かったですね。私は図書館に通って涼んでいました。図書館は静かで本がたくさんあって癒されます。

さて、前回はさめがめのボードを並び替えました。今回は隣接コマを探し出す機能を作りたいと思います。手始めに、任意の位置のコマを取得してみましょう。インタフェースを考えます。

piece(Board, X, Y, P) :- ...

BoardとX,Y位置を与え、コマPを返してもらう述語です。Boardは2次元リストです。ライブラリを調べてみると、リストの値を取得する便利な述語が見つかりました。nth0の使用方法を確かめてみましょう。

?- nth0(1, [1,2,3], X).
X = 2.

それではnth0を使ってpieceの本体を実装します。2次元リストなのでまずは行(Y)を指定し、次に列(X)を指定してPを取得します。

piece(Board, X, Y, P) :-
  nth0(Y, Board, Xs),
  nth0(X, Xs, P).

テストしてみます。述語boardは前回の3x3マスの定義を用います。

?- board(B), piece(B, 0, 0, P).
B = [[g, b, r], [g, g, r], [r, b, b]],
P = g.

位置は0から数えますので1x1の"g"が取得できていますね。本題の隣接コマを探すロジックに取り掛かりましょう。インタフェースを考えます。ボードとX,Y座標を与え、同種の隣接コマの座標をリスト(Neighbor)で返すようにしたいと思います。

neighbor(Board, X, Y, Neighbor) :- ...

まず自分自身の上下左右に同種のコマがあるかを調べ、同種のコマがあれば、さらにそのコマを中心として上下左右を調べます。つまり、再帰を用いたアルゴリズムになります。

先に述語の作り方について補足します。左側のコマが同種かどうかを調べるのでneighborLeftのような述語を作り、続けてneighborRight、neighborUp、neighborDownと別名で4種類の述語を作っても良いのですか、以下のように同じ述語にして、パターンマッチを使って場合分けする方がスッキリします。

neighbor(l, Board, X, Y, Neighbor) :-  ... %% 左(l)
neighbor(r, Board, X, Y, Neighbor) :-  ... %% 右(r)
neighbor(u, Board, X, Y, Neighbor) :-  ... %% 上(u)
neighbor(d, Board, X, Y, Neighbor) :-  ... %% 下(d)

第1項のアトム(l,r,u,d)のどれにマッチするかで適切な述語が選ばれます。もう一つ補足します。Prologでは同じ述語名でも引数の数(アリティ:arity)が異なると別の述語として扱われます。アリティは述語名の後ろに記述して表します。最初のneighborは引数が4つなのでneighbor/4です。上下左右チェック用のneighborは引数が5つなのでneighbor/5です。neighbor/4とneighbor/5は全く別物です。ついでにpieceはpiece/4と表され、nth0はnth0/3となります。覚えておきましょう。

それではneighbor/5の本体を実装していきます。"l"にマッチした場合、すなわち左側チェックのロジックから考えてみましょう。まずは与えられたX,Yから自身のコマ(P1)を取得します。

neighbor(l, Board, X, Y, Neighbor) :-
  piece(Board, X, Y, P1),
  ...

次に左隣のコマ(P2)を取得し、比較します。

neighbor(l, Board, X, Y, Neighbor) :-
  piece(Board, X, Y, P1),
  X1 is X - 1,
  piece(Board, X1, Y, P2),
  P1 == P2,
  ...

P1とP2が同種かどうかは上記のように等価演算子(==)を使っても良いですが、以下のようにP1とP2が同じ値Pであることを宣言的に表した方が良いです。

neighbor(l, Board, X, Y, Neighbor) :-
  X1 is X - 1,
  piece(Board, X, Y, P),
  piece(Board, X1, Y, P),
  ...

上記を満たす(中央と左のコマが等しい)ならば、再帰して検索を続けたいと思います。この時、neighbor/5のneighbor(l, ...)を呼び出してしまうと、左側にしかチェックが進まなくなってしまいます。上下左右全てを繰り返しチェックするためにはneighbor/4を呼び出します。

neighbor(l, Board, X, Y, Neighbor) :-  %% neighbor/5
  X1 is X - 1,
  piece(Board, X, Y, P),
  piece(Board, X1, Y, P),
  neighbor(Board, X, Y, Neighbor).     %% neighbor/4

さて、このまま進めると問題が発生します。左側をチェックした後neighbor/4を呼び出していますが、これでは無限ループになります。左を見て右を見て、また左を見て・・・とずっと同種のコマが隣に見つかるからです。したがって一度チェックしたコマを覚えておいて、そのコマに対しては再帰チェックをしないようにガードしなければなりません。

覚えておくと言っても副作用のあるグローバル変数は使えません。昔Haskellで実践したように状態は引数で渡すしかないのです。チェック済みのコマの位置(X,Y)を引数Crumb(パンくず)に入れておくようにします。ではneighbor/6を定義しなおしてみます。(引数を増やしたため、アリティが変わっています)

%% 左側に同じコマがあるかチェック
neighbor(l, Board, X, Y, Crumb, Neighbor) :-
  X1 is X - 1,
  not(member((X1,Y), Crumb)),
  piece(Board, X, Y, P),
  piece(Board, X1, Y, P),
  neighbor(Board, X1, Y, [(X1,Y)|Crumb], Neighbor).

member/2は第1項が第2項のリストに含まれているかを調べる述語です。

?- member(1, [1,2,3]).
true

not/1はtrue,falseを反転する述語です。

?- not(member(0, [1,2,3])).
true.

というわけで、新しいneighbor/6は、チェック対象のコマが既にCrumbリストに含まれている場合に述語が失敗するようになりました。neighbor/6の左側の場合分けは作れたので、同じように右側をチェックする述語を作ります。

%% 右側に同じコマがあるかチェック
neighbor(r, Board, X, Y, Crumb, Neighbor) :-
  X1 is X + 1,
  not(member((X1,Y), Crumb)),
  piece(Board, X, Y, P),
  piece(Board, X1, Y, P),
  neighbor(Board, X1, Y, [(X1,Y)|Crumb], Neighbor).

2行目のマイナスがプラスになっただけですね。上下の場合は省略します。えーっと、一つ定義が漏れていました。上下左右に移動するとボードからはみ出てしまうケースです。例えば現在のXが0なのに、左側のチェックを実行するとX1が-1になります。するとpiece/4内のnth0/3が失敗(false)します。

?- nth0(-1, [1,2,3], P).
false.

連鎖してneighbor/6も失敗してしまいます。neighbor/6を修正して、はみ出る場合にも適切な結果を返せるようにしましょう。Prologは述語が失敗すると、同一述語内(アリティが同じ)で別のパターンにマッチする定義がないか自動的にチェックします。というわけで、どんな引数でも一致する"_"(アンダースコア)を用いて番兵パターンを定義してあげましょう。

neighbor(_, _, _, _, Neighbor, Neighbor).

上記パターンに一致した場合、パンくず(Crumb)をそのまま隣接コマの検索結果として返し、再帰を停止させています。それでは最後に複数のneighbor/6をまとめてneighbor/5を定義しましょう。

neighbor(Board, X, Y, Crumb, Neighbor) :-
  neighbor(l, Board, X, Y, Crumb, Crumb1),
  neighbor(r, Board, X, Y, Crumb1, Crumb2),
  neighbor(u, Board, X, Y, Crumb2, Crumb3),
  neighbor(d, Board, X, Y, Crumb3, Neighbor).

順番に意味はありませんが左右上下の順にチェックしています。neighbor/6の第6項(Neighbor)にはその方向の同種コマのリストが返ってきますので、これを次のneighbor/6のCrumbに渡して無限ループを防ぎます。

それでは本日の成果をテストしてみましょう。

+-+-+-+
|g|b|r|
+-+-+-+
|g|g|r|
+-+-+-+
|r|b|b|
+-+-+-+

という前回定義したboardの(0,0)の隣接コマを再帰的に検索してみましょう。

?- board(B), neighbor(B, 0, 0, [], N).
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (0, 0), (1, 1), (0, 1)].

(0,0)と(1,1)と(0,1)、すなわち"g"の部分を再帰的に見つけてくれました。隣接と言いながら自分自身(0,0)も含んでいますが、今後コマを消すアルゴリズムのことを考えると好都合です。ところで上記の例では、本当に隣接コマを再帰検索してくれているかイマイチ確信が持てません。次の例で2段目2列目(1,1)を指定して隣接コマを再帰的に見つけてこれるかテストしてみましょう。右上の離れの@(3,0)は結果に含まれないはずですね。

+-+-+-+-+
|@|-|-|@|
+-+-+-+-+
|@|@|-|-|
+-+-+-+-+
|-|@|@|@|
+-+-+-+-+
|-|-|-|@|
+-+-+-+-+

?- neighbor([[@,-,-,@],[@,@,-,-],[-,@,@,@],[-,-,-,@]], 1, 1, [], N).
N = [ (0, 0), (3, 3), (3, 2), (2, 2), (1, 2), (1, 1), (0, 1)].

よし、(3,0)を含まずに7個の結果を返してくれました。今回はここまでにします。

話は変わり、上司Yさんに教えてもらった立川マシマシという、いわゆる二郎系のラーメン屋さんに行ってきました。ミニラーメンでも十分な食べ応えで、麺やスープも美味しかったので満足です。こってり系(というか二郎系?)が好きな方は行ってみてください^^

以上。
 
 

連載記事のソースコード

連載記事のソースコード
 
・Haskellで問題を解く(Part1〜Part4) ソースコード
・Clojureで8クイーン問題にチャレンジ(Part1〜Part5) ソースコード
・OCamlでへびゲームを作る(Part1〜Part5) ソースコード
・Swiftでオセロを作る(Part1〜Part5) ソースコード
・Processingでシューティング(Part1〜Part4) ソースコード 
Haskellでテトリス(Part1〜Part9) ソースコード
・プチコン3号(BASIC)でさめがめ(Part1〜Part3) ソースコード
・Prologでさめがめを解く(Part1〜Part6) ソースコード