反復深化の例題として、15 パズルの変形版である 6 パズル を解きました。今度は単純に解くのではなく、パズルが完成するまでにいちばん手数がかかる配置 (最長手数となる局面) を求めてみましょう。
6 パズルは全部で 5040 通りの局面があります。それらすべての局面の最短手順を求めて、その中から最長の手順となる局面を求めることもできますが、それでは時間がとてもかかりそうです。そこで、完成形から始めていちばん手数が長くなる局面を生成することにします。
まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ延ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。
6 パズルを表すデータ構造は、以前に作成したプログラムを流用します。座標を表す図と隣接関係のリストを再掲します。
１───２ ０───１
／ ＼ ／ ＼ ／ ＼ ／ ＼
３───４───５ ２───３───４
＼ ／ ＼ ／ ＼ ／ ＼ ／
６───０ ５───６
(1)完成形 (2)座標
図：６パズル
リスト：隣接関係の定義 next(0, 1). next(0, 2). next(0, 3). next(1, 3). next(1, 4). next(2, 3). next(2, 5). next(3, 4). next(3, 5). next(3, 6). next(4, 6). next(5, 6). neighbor(X, Y) :- next(X, Y). neighbor(X, Y) :- next(Y, X).
局面は state(Board, Space) で表します。Board が盤面で Space が空き場所の位置です。これを state_table(N, State) に記憶します。N が手数を表します。N + 1 手の局面は、state_table から N 手の局面を求め、駒を動かして新しい局面を生成します。そして、state_table に同一局面がないことを確認してから、N + 1 手の局面として state_table に登録します。
ここで、同一局面のチェックに単純な線形探索を使うと、時間がとてもかかってしまいます。この処理に 二分探索木 を使ってみましょう。まず最初に、二分探索木を使わないでプログラムを作ります。
今回は単純な幅優先探索なので、プログラムはそれほど難しくありません。幅優先探索を行う breadth_search から説明します。
リスト：幅優先探索
breadth_search(N) :-
not(state_table(N, _)), !, N1 is N - 1, print_answer(N1).
breadth_search(N) :-
findall(State, state_table(N, State), L),
N1 is N + 1,
make_new_state(N1, L),
breadth_search(N1).
breadth_search は N 手の局面から N + 1 手の局面を生成します。最初の規則で、N 手の局面があるか state_table をチェックします。state_table(N, _) が成功すれば、N 手の局面が存在します。なければ N - 1 手が最長手数です。print_answer で N - 1 手の局面を出力します。
N 手の局面が存在する場合、次の規則で N + 1 手の局面を生成します。集合述語 findall で state_table から N 手の局面を集めてリスト L に格納します。それから、述語 make_new_state に局面のリスト L を渡し、駒を動かして N + 1 手の局面を生成します。
次は make_new_state を説明します。
リスト：新しい局面を作る
make_new_state(N, []).
make_new_state(N, [ state(Board, Space) | Rest ]) :-
findall(X, neighbor(Space, X), L),
move_check(N, Board, L),
make_new_state(N, Rest).
空き場所 Space の隣の場所は、findall で集めてリスト L に格納します。それを述語 move_check に渡して新しい局面を生成します。このときに同一局面のチェックも行います。
次は move_check を説明します。
リスト：駒の移動と同一局面のチェック
move_check(N, Board, []).
move_check(N, Board, [X | Rest]) :-
nth0(X, Board, Piece),
move_piece(Piece, Board, NewBoard),
(state_table(_, state(NewBoard, _)) ->
true ; assert(state_table(N, state(NewBoard, X)))),
move_check(N, Board, Rest).
move_check は、場所 X にある駒を空き場所へ移動します。Board から X にある駒 Piece を求め、move_piece で駒を動かして新しい盤面 NewBoard を生成します。そして、この盤面が state_table にないかチェックします。
state_table は「事実」として定義されているので、state_table(_, state(NewBoard, _)) とマッチングに成功すれば同一局面が存在します。この場合は NewBoard を state_table に登録しません。マッチングに失敗したら同一局面がないので、assert で state_table に NewBoard を登録します。
ちなみに、同一局面のチェックを自分でプログラムすると、次のようになるでしょう。
/* 同一局面のチェック (失敗駆動ループ) */
check_same_state(New) :-
state_table(_, state(Old, _)), New == Old.
失敗駆動ループを使った単純な線形探索なので、これだと時間がかかってしまいます。 同一局面のチェックに Prolog のマッチング機能を使うことで、単純な線形探索よりも高速になります。
述語 move_piece は 6 パズルで作成したプログラムと同じです。リストを再掲します。
リスト：駒の移動（再掲） move_piece(_, [], []). move_piece(Piece, [0 | Rest], [Piece | Rest1]) :- move_piece(Piece, Rest, Rest1), !. move_piece(Piece, [Piece | Rest], [0 | Rest1]) :- move_piece(Piece, Rest, Rest1), !. move_piece(Piece, [X | Rest], [X | Rest1]) :- move_piece(Piece, Rest, Rest1).
解を表示する print_answer は簡単なので説明は省略します。リストを読んでくださいね。
リスト：解の表示
print_answer(N) :-
write(N), nl,
state_table(N, state(Board, _)), write(Board), nl, fail.
それでは実行してみましょう。初期状態を assert で登録してから breadth_search を呼び出します。
リスト：テスト
test :-
assert(state_table(0, state([1,2,3,4,5,6,0], 6))),
breadth_search(0).
?- test. 15 [2, 1, 5, 4, 3, 0, 6] [0, 2, 5, 4, 1, 6, 3] [4, 6, 5, 0, 2, 3, 1] [1, 6, 2, 4, 3, 5, 0] [4, 6, 5, 1, 3, 2, 0] [5, 2, 0, 4, 3, 6, 1] [0, 1, 2, 4, 3, 5, 6] [0, 3, 2, 4, 6, 5, 1] [4, 3, 2, 1, 6, 5, 0] [4, 6, 2, 0, 3, 5, 1] [3, 6, 1, 4, 0, 2, 5] [0, 3, 1, 4, 6, 2, 5] [1, 3, 5, 4, 6, 2, 0] [0, 6, 3, 4, 5, 1, 2] [0, 5, 6, 4, 2, 3, 1] [0, 5, 4, 6, 3, 2, 1] [0, 6, 4, 5, 3, 1, 2] [4, 0, 5, 6, 3, 2, 1] [4, 3, 5, 0, 6, 2, 1] [6, 0, 3, 4, 5, 2, 1] [0, 4, 5, 6, 1, 2, 3] [0, 4, 6, 5, 3, 2, 1] [4, 6, 0, 5, 3, 2, 1] [0, 6, 5, 4, 3, 2, 1]
最長手数は 15 手で、局面は全部で 24 通りあります。実行時間はオンボロマシン (Pentium 166 MHz) で約 107 秒でした。ちなみに、同一局面のチェックに線形探索 (check_same_state) を使うと約 370 秒かかります。SWI-Prolog のマッチングは高速ですね。
ところで、このプログラムは失敗駆動ループを使って実現することもできます。その方が簡単にプログラムできるかもしれません。興味ある方は、失敗駆動ループに書き直してみてください。ただし、失敗駆動ループでは二分探索木を使うことができないので、今回は findall と末尾再帰でプログラムしました。
次は、二分探索木を使ってプログラムを作ります。二分探索木を使う場合、データの大きさを比較する述語が必要になります。6 パズルの盤面はリストで表しているので、リストの要素を順番に比較することで大小関係を定義してもいいのですが、今回は盤面を整数値に変換することにします。プログラムは次のようになります。
リスト：盤面を数値に変換
board_to_number([], Result, Result).
board_to_number([N | Rest], M, Result) :-
M1 is M * 10 + N, board_to_number(Rest, M1, Result).
述語 board_to_number は盤面を 7 桁の整数値に変換します。単純な方法ですが、これで盤面を固有の整数値に変換することができます。このほかに、N! 通りのパターンを 0 から N! - 1 まで整数値に変換する方法があります。6 パズルの局面は全部で 5040 通りありますが、この方法を使うと局面を 0 から 5039 までの整数値に変換することができます。興味のある方は Puzzle DE Programming の 幅優先探索の高速化(1) をご覧ください。
次は、二分探索木にデータを挿入する insert_tree を作ります。
リスト：データの挿入 insert_tree(Data, Tree) :- var(Tree), Tree = node(Data, _, _). insert_tree(Data, node(Data, _, _)) :- !, fail. insert_tree(Data, node(Value, Left, _)) :- Data < Value, insert_tree(Data, Left). insert_tree(Data, node(Value, _, Right)) :- Data > Value, insert_tree(Data, Right).
基本的には 二分探索木 で説明したプログラムと同じですが、同じデータを見つけた場合は失敗することにします。2 番目の規則で、同じデータを見つけた場合は fail で失敗するとともに、残りの規則を実行しないためカットを使っていることに注意してください。これで新しいデータは二分木に挿入されますが、同じデータを見つけた場合は失敗します。
これで二分探索木を使う準備ができました。それでは、プログラムを修正しましょう。
リスト：幅優先探索
breadth_search(N, _) :-
not(state_table(N, _)), !, N1 is N - 1, print_answer(N1).
breadth_search(N, Tree) :-
findall(State, state_table(N, State), L),
N1 is N + 1,
make_new_state(N1, L, Tree),
breadth_search(N1, Tree).
リスト：新しい局面を作る
make_new_state(N, [], Tree).
make_new_state(N, [ state(Board, Space) | Rest ], Tree) :-
findall(X, neighbor(Space, X), L),
move_check(N, Board, Tree, L),
make_new_state(N, Rest, Tree).
breadth_search と make_new_state は、引数に二分探索木を表す変数 Tree を追加するだけです。次は、move_check を修正します。
リスト：駒の移動と同一局面のチェック
move_check(N, Board, Tree, []).
move_check(N, Board, Tree, [X | Rest]) :-
nth0(X, Board, Piece),
move_piece(Piece, Board, NewBoard),
board_to_number(NewBoard, 0, M),
(insert_tree(M, Tree) -> assert(state_table(N, state(NewBoard, X))) ; true),
move_check(N, Board, Tree, Rest).
move_check も引数に Tree を追加します。盤面 NewBoard を board_to_number で整数値 M に変換し、それを insert_tree で Tree に挿入します。成功すれば新しい局面なので、assert で NewBoard を state_table に登録します。insert_tree が失敗した場合、同一局面があるので state_table には登録しません。プログラムの修正はこれだけです。
それでは実行してみましょう。
リスト：テスト
test :-
Init = [1,2,3,4,5,6,0],
board_to_number(Init, 0, N),
insert_tree(N, Tree),
assert(state_table(0, state(Init, 6))),
breadth_search(0, Tree).
breadth_search を実行する前に、初期状態を二分探索木と state_table に登録します。実行時間はオンボロマシン (Pentium 166 MHz) で約 13 秒と、8 倍以上の高速化に成功しました。二分探索木の効果は十分に出ていますね。
Prolog 処理系に依存しますが、もっと簡単で高速な方法を紹介しましょう。SWI-Prolog の場合、盤面を表す整数値を節 state_number に記憶させると、二分探索木を使わなくても高速に実行できます。次のプログラムを見てください。
リスト：駒の移動と同一局面のチェック
move_check(N, Board, []).
move_check(N, Board, [X | Rest]) :-
nth0(X, Board, Piece),
move_piece(Piece, Board, NewBoard),
board_to_number(NewBoard, 0, M),
(state_number(M) ->
true ; (assert(state_number(M)),
assert(state_table(N, state(NewBoard, X))))),
move_check(N, Board, Rest).
盤面を表す整数値は、二分探索木ではなく節 state_number に記憶します。state_number(M) が成功すれば、同一局面があるので盤面 NewBoard は登録しません。失敗した場合は新しい局面なので、整数値を state_number に、盤面 NewBoard を state_table に登録します。ようするに、同一局面のチェックを SWI-Prolog のパターンマッチングに頼るわけです。
最初に説明したように、state_table とマッチングさせると実行時間は長くなります。ところが、このプログラムのように整数値を記憶させると、実行時間は約 10 秒とたいへん高速になりました。これは SWI-Prolog での結果であり、ほかの Prolog 処理系で同様な結果が得られるとは限りません。ご注意ください。
また、データ構造によっても実行時間は変わります。たとえば、state_number に手数を記憶することにしましょう。state_number(Num, Move) のように整数値 Num を第 1 引数にした場合、実行時間は今までと同じですが、手数 Move を第 1 引数にすると実行時間は約 80 秒と遅くなってしまいます。
Prolog 処理系の内部では、パターンマッチングを高速に行うために、いろいろな工夫がなされています。SWI-Prolog では、名前のほかに第 1 引数の情報を利用することで、高速なパターンマッチングを実現していると思われます。興味のある方は、ほかの Prolog 処理系でも試してみてください。
二分探索木を使わないのであれば、失敗駆動ループを利用することができます。参考までに失敗駆動ループ版のプログラムを示しましょう。ちなみに、実行時間は約 8 秒と少しだけ速くなりました。
リスト：６パズルの最長手数（失敗駆動ループ版）
/* 隣接 */
next(0, 1). next(0, 2). next(0, 3).
next(1, 3). next(1, 4).
next(2, 3). next(2, 5).
next(3, 4). next(3, 5). next(3, 6).
next(4, 6).
next(5, 6).
neighbor(X, Y) :- next(X, Y).
neighbor(X, Y) :- next(Y, X).
/* 数値に変換 */
board_to_number([], Result, Result).
board_to_number([N | Rest], M, Result) :-
M1 is M * 10 + N, board_to_number(Rest, M1, Result).
/* 駒の移動 */
move_piece(_, [], []).
move_piece(Piece, [0 | Rest], [Piece | Rest1]) :-
move_piece(Piece, Rest, Rest1), !.
move_piece(Piece, [Piece | Rest], [0 | Rest1]) :-
move_piece(Piece, Rest, Rest1), !.
move_piece(Piece, [X | Rest], [X | Rest1]) :-
move_piece(Piece, Rest, Rest1).
/* 駒の移動と同一局面のチェック */
move_check(N, Board, X) :-
nth0(X, Board, Piece),
move_piece(Piece, Board, NewBoard),
board_to_number(NewBoard, 0, M),
not(state_number(M)),
assert(state_number(M)),
assert(state_table(N, state(NewBoard, X))),
!,
fail.
/* 新しい局面を作る */
make_new_state(N, N1) :-
state_table(N, state(Board, Space)),
neighbor(Space, X),
move_check(N1, Board, X).
/* 表示 */
print_answer(N) :-
write(N), nl,
state_table(N, state(Board, _)),
write(Board), nl, fail.
/* 幅優先探索 */
breadth_search(N) :-
not(state_table(N, _)), !, N1 is N - 1, print_answer(N1).
breadth_search(N) :-
N1 is N + 1,
not(make_new_state(N, N1)),
breadth_search(N1).
/* 実行 */
test :-
assert(state_table(0, state([1,2,3,4,5,6,0], 6))),
board_to_number([1,2,3,4,5,6,0], 0, N),
assert(state_number(N)),
breadth_search(0).
Prolog の場合、データ構造を表すのにリストがよく使われます。ところが、問題によってはリストよりもビットで表した方が、プログラムを作るのに都合がいい場合もあります。SWI-Prolog には、整数の論理演算とビット操作を行う演算子が用意されています。
| 式 | 機能 |
|---|---|
| IntExpr \/ IntExpr | ビットごとの論理和を計算する |
| IntExpr /\ IntExpr | ビットごとの論理積を計算する |
| IntExpr xor IntExpr | ビットごとの排他的論理和を計算する |
| \ IntExpr | ビットごとの論理的否定を計算する |
| IntExpr1 >> IntExpr2 | IntExpr1 を IntExpr2 ビット右へシフトする |
| IntExpr1 << IntExpr2 | IntExpr1 を IntExpr2 ビット左へシフトする |
簡単な使用例を示しましょう。
?- X is 1 \/ 0. X = 1 ?- X is 1 /\ 0. X = 0 ?- X is 1 xor 1. X = 0 ?- X is 1 xor 0. X = 1 ? X is \ 0. X = -1 ?- X is 1 << 1. X = 2 ?- X is 1 << 2. X = 4
それでは、例題として Puzzel DE Programming で取り上げた ライツアウト というパズルを Prolog で解いてみましょう。ライツアウトの説明は、Puzzle DE Programming と重複するところがありますが、ご容赦くださいませ。
ライツアウトは光っているボタンをすべて消すことが目的のパズルです。ルールはとても簡単です。あるボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。つまり、光っているボタンは消灯し、消えていたボタンは点灯します。次の図を見てください。
□□□□□ □□□□□ ０ １ ２ ３ ４
□□□□□ □□■□□ ５ ６ ７ ８ ９
□□□□□ ─→ □■■■□ 10 11 12 13 14
□□□□□ □□■□□ 15 16 17 18 19
□□□□□ □□□□□ 20 21 22 23 24
（Ａ）中央のボタンを押した場合 （Ｂ）座標
図：ライツアウトの点灯パターン
ボタンは 5 行 5 列に配置されています。図に示したように、中央のボタン 12 を押すと、そのボタンと上下左右のボタンの状態が反転します。
ライツアウトは、ライトオン・オフの 2 種類の状態しかないので、盤面はリストよりもビットを使って表した方が簡単です。ライトオン・オフの状態を 1 と 0 で表し、各ビットとボタンの座標を対応させると、盤面は 0 から 33554431 の整数値で表すことができます。
ボタンを押してライトの状態を反転する処理も簡単です。たとえば、中央のボタン 12 を押した場合、7, 11, 12, 13, 17 のライトを反転させます。この場合、5 つのボタンのビットをオンにした値 0x23880 (16進数) と、盤面を表す整数値の排他的論理和 (xor) を求めれば、5 つのライトの状態を反転することができます。次の例を見てください。
0 xor 0x23880 => 0x23880 % 消灯の状態でボタン 12 を押す (点灯する) 0x23880 xor 0x23880 => 0 % もう一度同じボタンを押す (消灯する)
このように、ライツアウトは同じボタンを二度押すと元の状態に戻ります。したがって、同じボタンは二度押さなくてよいことがわかります。また、実際にボタンを押してみるとわかりますが、ボタンを押す順番は関係がないことがわかります。たとえば、ボタン 0 と 1 を押す場合、0 -> 1 と押すのも 1 -> 0 と押すのも同じ結果になります。
この 2 つの法則から、ボタンを押す組み合わせは全部で 2 ^ 25 通りになります。ライツアウトを解くいちばん単純な方法は、ボタンを押す組み合わせを生成して、実際にライトが全部消えるかチェックすることです。ところが、この方法ではちょっと時間がかかるのです。高速 CPU を搭載した最新マシンを使えば、Prolog でも短時間で解けると思いますが、M.Hiroi のオンボロマシン(Pentium 166 MHz) では、けっこう時間がかかるでしょう。実は、もっと高速に解く方法があるのです。
ライツアウトは次の図に示すように、ボタンを上から 1 行ずつ消灯していくという、わかりやすい方法で解くことができます。
ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ
１□■□■□ １□□□□□ １□□□□□ １□□□□□
２□□□□□ ２■■□■■ ２□□□□□ ２□□□□□
３□□□□□ ３□■□■□ ３□■□■□ ３□□□□□
４□□□□□ ４□□□□□ ４■■□■■ ４□□□□□
５□□□□□ ５□□□□□ ５□□□□□ ５□■□■□
（１） （２） （３） （４）
図：1 行ずつボタンを消灯していく方法
(1) では、1 行目のボタンが 2 つ点灯しています。このボタンを消すには、真下にある 2 行目の B と D のボタンを押せばいいですね。すると (2) の状態になります。次に、2 行目のボタンを消します。3 行目の A, B, D, E のボタンを押して (3) の状態になります。
あとはこれを繰り返し、4 行目までのボタンを消したときに、5 行目のボタンも全部消えていれば成功となります。(4) のように、5 行目のボタンが消えない場合は失敗です。この場合は、1 行目のボタンを押して、点灯パターンを変更します。
2 - 5 行目のボタンの押し方は、1 行目の点灯パターンにより決定されるので、けっきょく 1 行目のボタンの押し方により、解けるか否かが決まります。この場合、ボタンの押し方は、2 ^ 5 = 32 通りしかありせん。つまり、たった 32 通り調べるだけで、ライツアウトの解を求めることができます。
このほかに、高橋謙一郎さんの コンピュータ＆パズル では、細江万太郎さんが考案されたライツアウトを連立方程式で解く方法が紹介されています。この方法には M.Hiroi も驚きました。
それではプログラムを作りましょう。最初に、ボタンを押したときにライトの状態を反転させるための値を pattern に定義します。
リスト：ボタンを押したときのパターン pattern(0, 0x0000023). pattern(1, 0x0000047). pattern(2, 0x000008e). pattern(3, 0x000011c). pattern(4, 0x0000218). pattern(5, 0x0000461). pattern(6, 0x00008e2). pattern(7, 0x00011c4). pattern(8, 0x0002388). pattern(9, 0x0004310). pattern(10, 0x0008c20). pattern(11, 0x0011c40). pattern(12, 0x0023880). pattern(13, 0x0047100). pattern(14, 0x0086200). pattern(15, 0x0118400). pattern(16, 0x0238800). pattern(17, 0x0471000). pattern(18, 0x08e2000). pattern(19, 0x10c4000). pattern(20, 0x0308000). pattern(21, 0x0710000). pattern(22, 0x0e20000). pattern(23, 0x1c40000). pattern(24, 0x1880000).
pattern(N, Value) の引数 N がボタンの番号で、Values がライトの状態を反転させるための値です。
次は、ライツアウトを解くプログラム solve を作ります。
リスト：ライツアウトの解法
solve(Board) :-
between(0, 31, N),
push_button(N, 0, Board, NewBoard),
clear_light(5, NewBoard, Result, N, PushPattern),
Result == 0,
print_answer(PushPattern).
1 行目のボタンの押し方は 32 通りあります。solve は失敗駆動ループにより 32 通りの押し方をすべてをチェックします。ボタンの押し方は 0 から 31 までの数値で表します。これらの値は 5 ビットで表すことができるので、ビットとボタンの位置を対応させて、ビットがオンであればそのボタンを押すことにします。この処理を述語 push_button で行います。結果は NewBoard にセットされます。
1 行ずつライトを消していく処理は述語 clear_light で行います。ボタンを押したあとの盤面は Result に、ボタンを押した位置は PushPattern にセットされます。PushPattern は、対応するビットをオンにすることで押したボタンの位置を表します。Result が 0 になればすべてのライトが消灯したので、print_answer で解を表示します。失敗駆動ループを構成するため、print_answer は必ず失敗することに注意してください。
次は、1 行目のボタンを押す push_button を作ります。
リスト：1 行目の５つのボタンを押す
push_button(_, 5, Board, Board) :- !.
push_button(N, M, Board, Result) :-
((1 << M) /\ N) > 0, % ビットオンならばボタンを押す
pattern(M, Pattern),
NewBoard is Board xor Pattern,
M1 is M + 1, !, push_button(N, M1, NewBoard, Result).
push_button(N, M, Board, Result) :-
M1 is M + 1, push_button(N, M1, Board, Result).
引数 N が押すボタンを表す値で、M がボタンの位置を表します。最初の規則が再帰の停止条件です。ボタンは 0 から 4 までの 5 つなので、M が 5 になればボタンを押す処理を終了します。
次の規則で、整数値 N の M 番目のビットがオンならば、M 番目のボタンを押します。ビットのチェックは、論理積 /\ を使えば簡単です。ビットシフト << を使って 1 を左へ M ビットシフトし、N との論理積を求めます。ビットがオフであれば論理積の結果は 0 になるので、0 より大きければビットはオンであることがわかります。
ボタンを押す処理も簡単です。pattern からライトを反転させる値を取り出し、xor でライトを反転させて新しい盤面 NewBoard を作るだけです。ビットがオフであれば、最後の規則が実行されて次のボタンをチェックします。それから、push_button は再試行する必要はないので、カットを使っていることに注意してください。
次は clear_light を作ります。
リスト：上の行のライトを消す
clear_light(25, Board, Board, Push, Push) :- !.
clear_light(N, Board, Result, Push, PushResult) :-
M is N - 5,
(Board /\ (1 << M)) > 0,
pattern(N, Pattern),
NewBoard is Board xor Pattern,
NewPush is Push \/ (1 << N),
N1 is N + 1, !, clear_light(N1, NewBoard, Result, NewPush, PushResult).
clear_light(N, Board, Result, Push, PushResult) :-
N1 is N + 1, clear_light(N1, Board, Result, Push, PushResult).
clear_light の引数 N がボタンの位置、Board が盤面の状態、Push が押したボタンの位置を表します。最初の規則が再帰の停止条件です。
次の規則で、上のライトが点灯しているかチェックします。上のライトは M で表していて、その位置は N - 5 で求めることができます。Board の M 番目のビットがオンであればライトが点灯しているので、N 番目のボタンを押して新しい盤面 NewBoard を作ります。押したボタンの位置は Push に記憶します。ボタン N を押した場合は、Push の N 番目のビットをオンにします。ビットシフト << で 1 を左へ N ビットシフトし、Push との論理和を求めれば、N 番目のビットだけをオンにすることができます。
ライトが点灯していない場合は、最後の規則が実行されて次のボタンを処理します。それから、clear_light も再試行する必要がないので、カットを使っていることに注意してください。
最後に、解を出力する print_answer を作ります。
リスト：解の出力
print_answer(PushPattern) :-
nl,
between(0, 24, N),
((PushPattern /\ (1 << N)) > 0 -> write('1') ; write('0')),
M is N mod 5,
(M == 4 -> nl),
fail.
print_answer は失敗駆動ループでプログラムします。PushPattern の各ビットをチェックして、オンであれば 1 を、オフであれば 0 を出力します。5 行 5 列に出力するため、N mod 5 の値が 4 であれば nl で改行を出力します。
これでプログラムは完成です。それでは実行してみましょう。ライトが全部点灯している状態 (0x1ffffff) を解いてみます。
?- solve(0x1ffffff). 11000 11011 00111 01110 01101 10110 01110 11100 11011 00011 01101 01110 00111 11011 11000 00011 11011 11100 01110 10110 No
4 通りの解が出力されました。ボタンを押した回数は、どの解も 15 回になりました。 実は、これがライツアウトの最長手数なのです。ライツアウトの場合、ライトの点灯パターンは 2 ^ 25 = 33554432 通りありますが、実際に解が存在するパターンは、その 1 / 4 の 8388608 通りしかありません。その中で最短回数が 15 回で解けるパターンは 7350 通りあり、そのうちのひとつが、ライトが全部点灯しているパターンなのです。
ライツアウトの最長手数に興味のある方は、Puzzle DE Programming：ライツアウト の 最長手数を求める を読んでみてください。