筆者：村田
こんにちは。
暑いですね〜。都心もとうとう今年初の猛暑日となったそうで。暑さが一層厳しくなりますが皆さんも体に気をつけて夏を過ごしましょう。でもまあ夏ですね。昨日、立川では花火まつりがあり、今日は地元福生でも夏祭りがありました。駅前は神輿や山車などが出ていて賑やかでした。暑くてあまり長居はできませんでしたが、お祭りの雰囲気、お囃子を聞いていると夏だな〜と感じますね。
さて、5月の更新から間が空いてしまいました。久しぶりのPrologです。今回はさめがめのボードをPrologで表現してみます。コマはアルファベット1文字にします。単純な3x3マスのボードは以下のように表せます。
+-+-+-+
|g|b|r|
+-+-+-+
|g|g|r|
+-+-+-+
|r|b|b|
+-+-+-+
r ... red
g ... green
b ... blue
この3x3のさめがめ問題は以下のようにg->b->rの順に消すとクリアできます。
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|g|b|r| | | |r| | | | | | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|g|g|r| -> | |b|r| -> | |r| | -> | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
|r|b|b| |r|b|b| |r|r| | | | | |
+-+-+-+ +-+-+-+ +-+-+-+ +-+-+-+
２次元のマスはリストを使って表現します。上記のボードは以下のように定義できます。
board([[g,b,r],
[g,g,r],
[r,b,b]]).
swiplで読み込んでボードを表示させてみます。
$ swipl -f samegame.pl
?- board(B).
B = [[g, b, r], [g, g, r], [r, b, b]].
これは問題をわかりやすく定義するための並び順です。このまま問題を解くことができるかもしれませんが、今回はプログラムで解きやすいように並び順を変換します。さめがめはコマを消すとその上のコマがストンと落ちてきます。このストンという動作は、リストの並び順を工夫すると簡単に実装できます。例題の一番左の列は下からr,g,gです。この並び順でリストにすると[r,g,g]となります。rを削除すれば[g,g]となりコマがストンと落ちた結果と一致します。というわけで、以下の手順でボードを並び替えるのが今回の目標です。
① ボードの行を逆順にします。
[[g, b, r], [g, g, r], [r, b, b]] -> [[r, b, b], [g, g, r], [g, b, r]]
② 各行の１つ目を集めて１行にします。２つ目以降も同様に繰り返します。これは行と列の入れ替えに相当します。
[[r, b, b], [g, g, r], [g, b, r]] -> [[r, g, g], [b, g, b], [b, r, r]]
では並び替える方法を考えていきます。まず①ですが、マニュアルを探すと逆順にする述語reverseがみつかります。使い方を見てみます。
?- reverse([1,2,3], R).
R = [3, 2, 1].
ではボードの行を逆順にします。
?- board(B), reverse(B, Reversed).
B = [[g, b, r], [g, g, r], [r, b, b]],
Reversed = [[r, b, b], [g, g, r], [g, b, r]].
①の結果が得られました。次に②を考えます。なかなか難しいですが色々なやり方があるので面白い題材です。これから紹介する方法以外にも考えてみると面白いでしょう。 まずは各行の先頭を集めて一つにまとめる述語を考えます。BoardをもらってHeadRowを返す述語なので、書き出しは・・・
headline(Board, HeadRow) :-
となります。最初にBoardから先頭行(Row)の先頭(H)をとります。
headline(Board, HeadRow) :-
[Row|Remain] = Board,
[H|T] = Row,
次にBoardの残りの部分(Remain)からも同じように先頭を集めるのですが、ここは「繰り返し」ですね。他の言語ならfor文を用いるところですがPrologでは再帰を使います。ゆっくり考えましょう。Boardを[Row|Remain]に分けると以下のようになります。
Board = [[r, b, b], [g, g, r], [g, b, r]],
Row = [r, b, b],
Remain = [[g, g, r], [g, b, r]].
よく見るとRemainは少し小さくなったBoardであることがわかります。BoardもRemainも２次元リストであり、RemainはBoardと同型で、Boardの一部分です。このように同型の部分を見つけることは再帰を思いつく上でポイントになります。RemainはBoardと同型なのでheadlineに渡すことができます。headlineの仕様はBoardの先頭を集めた行を返してくれるのですから、返してくれた値(RemainHeadRow)を組み合わせましょう。
headline(Board, HeadRow) :-
[Row|Remain] = Board,
[H|T] = Row,
headline(Remain, RemainHeadRow),
HeadRow = [H|RemainHeadRow].
再帰を書くときには停止性に気をつけます。Remainはどんどん小さくなり、最後は空リスト[]になります。その場合はHeadRowも空リストです。このパターンを付け加えます。
headline(Board, HeadRow) :-
[Row|Remain] = Board,
[H|T] = Row,
headline(Remain, RemainHeadRow),
HeadRow = [H|RemainHeadRow].
headline([], []).
ちょっと試してみます。
?- headline([[1, 2, 3], [a, b, c], [A, B, C]], HeadRow).
HeadRow = [1, a, A].
先頭行を集めることができました。さて、他の行についても同じことをやりたいのですが、どうすれば良いでしょう。これも「繰り返し」ですので再帰を考えます。ただしheadlineはすでに内部に一つの再帰ループを抱えており、ここにさらにもう一つ再帰を書いて2重ループを作るのは大変です。そこでheadlineは1重ループのままにして、先頭行を集めたら、残りの部分をBoardの部分同型として、headlineの第３項(TailBoard)で返すようにします。実装してみましょう。Rowを分割した際の残り(T)とheadlineの残り(RemainTailBoard)を集めてTailBoardを返します。
headline(Board, HeadRow, TailBoard) :-
[Row|Remain] = Board,
[H|T] = Row,
headline(Remain, RemainHeadRow, RemainTailBoard),
HeadRow = [H|RemainHeadRow],
TailBoard = [T|RemainTailBoard].
headline([], [], []).
試してみます。
?- headline([[1, 2, 3], [a, b, c], [A, B, C]], HeadRow, TailBoard).
HeadRow = [1, a, A],
TailBoard = [[2, 3], [b, c], [B, C]].
先頭行の残りを返すことができました。なお以下のようにリファクタリングして変数を減らすことができます。
headline([Row|Remain], [H|RemainHeadRow], [T|RemainTailBoard]) :-
[H|T] = Row,
headline(Remain, RemainHeadRow, RemainTailBoard).
headline([], [], []).
ではheadlineを繰り返し呼び出して行列をひっくり返す述語(transepose)を考えます。
transpose(Board, Transposed) :-
headline(Board, HeadRow, TailBoard), % 行列の１列目を集めた先頭行と残りを得る
transpose(TailBoard, TailTransposed), % 残りをひっくり返す
Transposed = [HeadRow|TailTransposed]. % 先頭行とひっくり返した残りを結合する
なお再帰停止用の節には注意が必要です。TailBoardはどんどん短くなりますが、最後は空リスト[]ではなく、空リストのリスト[[], [], ...]になります。したがって以下のように書くとパターンマッチしません。
transpose([], []).
正しいパターンマッチは以下です。
transepose([[]|_], []).
これもリファクタリングして変数を減らし、以下のように書けます。
transpose(Board, [HeadRow|TailTransposed]) :-
headline(Board, HeadRow, TailBoard),
transpose(TailBoard, TailTransposed).
transpose([[]|_], []).
では試してみます。
?- transpose([[1, 2, 3], [a, b, c], [A, B, C]], R).
R = [[1, a, A], [2, b, B], [3, c, C]] ; <- あれ？バックトラックした・・・
false.
得られた結果(R)は問題ないのですが、バックトラックが動いて別の解を探しに行っているようです。;を入力して次の解を探しても見つからずfalseになっています。今回は説明を端折りますがカット(!)という機能でバックトラックを抑制できます。
transpose(Board, [HeadRow|TailTransposed]) :-
headline(Board, HeadRow, TailBoard),
transpose(TailBoard, TailTransposed), !. %% ここまで来たらバックトラックを抑制(!はカット記号)
transpose([[]|_], []).
これで以下のように一つのみ解を得られます。
?- transpose([[1, 2, 3], [a, b, c], [A, B, C]], R).
R = [[1, a, A], [2, b, B], [3, c, C]].
最後に①と②を組み合わせてボードを並び替える述語を組み立てましょう。
convert_board(Board, Converted) :-
reverse(Board, Reversed),
transpose(Reversed, Converted).
試してみます。
?- board(Board), convert_board(Board, Converted).
Board = [[g,b,r],[g,g,r],[r,b,b]],
Converted = [[r,g,g],[b,g,b],[b,r,r]].
今回の目標であるボードの並び替えができました。今回はここまでにします。それと、ようやく、さめがめのコードを書き始めたということで、本ページの下のリンクから今回のソースコードを参照できます。ところで今月のSoftware Design誌に「なぜ関数型プログラミングは難しいのか？」というテーマでLisp/Scala/Haskell/Elixir/Python/Clojureを使った特集が載っています。まだ全部読んでいませんが、個人的にはElixirっていう言語が初めてなので興味深いです。Prologは関数型言語に分類されることは少ないのですが、副作用を抑え、再帰を多用する考え方は関数型と通じるものがあり、このような関数型の特集記事などは参考になる点が多いです。
以上。
