今回は簡単なパズルを 5 問出題します。Prolog で解法プログラムを作成してください。
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。
例 : 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。問題１は小町算の中でも特に有名なパズルです。
S E N D
+ M O R E
-------------
M O N E Y
図 : 覆面算
計算式の数字を文字や記号に置き換えて、それを元の数字に戻すパズルを「覆面算」といいます。異なる文字は異なる数字を表し、同じ文字は同じ数字を表します。使用する数字は 0 から 9 までで、最上位の桁に 0 を入れることはできません。
問題２はデュードニーが 1924 年に発表したもので、覆面算の古典といわれる有名なパズルです。
┌─┬─┬─┬─┬─┬─┬─┐
│●│●│●│ │○│○│○│ スタート
└─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┐
│○│○│○│ │●│●│●│ ゴール
└─┴─┴─┴─┴─┴─┴─┘
図 : 蛙跳びゲーム
蛙跳びゲームは黒石と白石を使って遊ぶ、いわゆる「飛び石ゲーム」と呼ばれる種類のパズルです。上図のように、蛙跳びゲームは黒石と白石を入れ替えることができれば成功です。スタートからゴールまでの最短手順を求めてください。
石を動かす規則は次のとおりです。
石の跳び越しは次の図を参考にしてください。
┌───┐ ┌───┐
↓ │ │ ↓
┬─┬─┬─┬─┬ ┬─┬─┬─┬─┬
│ │●│○│ │ │ │●│○│ │
┴─┴─┴─┴─┴ ┴─┴─┴─┴─┴
白石の移動 黒石の移動
図 : 石の跳び越し
3 人の宣教師と 3 人の先住民が川を渡ることになりました。川には 2 人乗りのボートが 1 そうしかありません。どのような時でも先住民の数が宣教師の数よりも多いと、先住民は反旗を翻し宣教師に襲い掛かります。6 人が安全に川を渡る最短手順を求めてください。
問題４は「川渡りの問題」とか「渡船問題」と呼ばれる古典的なパズルの一種です。その中でも「宣教師と先住民」は特に有名な問題です。
斗桶に油が 1 斗（= 10 升）あります。これを 5 升ずつ 2 つの油に分けたいのですが、手元には 7 升ますと 3 升ますが 1 つずつしかありません。この 2 つのますを使って油を二等分してください。
油分け算は江戸時代の和算書『塵劫記（じんこうき）』にある問題です。
それではプログラムを作りましょう。式は次のようにリストで表すことにします。
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 => [1, +, 2, +, 3, -, 4, +, 5, +, 6, +, 78, +, 9]
あとは、式を生成して値を計算するだけです。式を生成するとき、リストを逆順で管理すると簡単です。次の図を見てください。
[1] => [2, +, 1] => [3, +, 2, + 1]
=> [3, -, 2, + 1]
=> [23, +, 1]
=> [2, -, 1] => [3, +, 2, -, 1]
=> [3, -, 2, -, 1]
=> [23, -, 1]
=> [12] => [3, +, 12]
=> [3, -, 12]
=> [123]
式を生成するとき、リストに数字と演算子を順番に追加していきます。数字と +, - を追加する処理は簡単です。プログラムのポイントは数字を連結する処理、たとえば 1 と 2 を連結して一つの数値 12 にする処理です。この処理はリストの先頭の数字 1 を 12 (= 1 * 10 + 2) に置き換えることで実現できます。リストが [2, +, 1] であれば、数字 2 を 23 (= 2 * 10 + 3) に置き換えます。
式を生成するプログラムは次のようになります。
リスト : 式の生成
set_op(N, Exp, [N, + | Exp]).
set_op(N, Exp, [N, - | Exp]).
set_op(N, [N1 | Rest], [N2 | Rest]) :- N2 is N1 * 10 + N.
make_exp(10, Exp) :-
reverse(Exp, Exp1), calc_exp(Exp1, N), N =:= 100, print_expr(Exp1), fail.
make_exp(N, Exp):-
N < 10, set_op(N, Exp, Exp1), N1 is N + 1, make_exp(N1, Exp1).
make_exp の引数 N が追加する数字、Exp が生成する式 (リスト) です。set_op は Exp に数字 N と演算子をセットし、新しい式 Exp1 を生成します。N が 10 の場合は、式が完成したので値を計算します。reverse で式を元に戻し、calc_exp で式 Exp1 を計算します。値 N が 100 になれば述語 print_expr で式を出力します。
set_op(N, Exp, Exp1) は Exp に数字と演算子をセットして新しい式 Exp1 を生成します。演算子 + と - を追加する処理は簡単ですね。数字を連結する場合は、式の先頭から数字 N1 を取り出し、N1 * 10 + N を計算して N2 にセットします。あとは、[N2 | Rest] とすれば N1 を N2 に置き換えることができます。
次は式を計算する calc_exp を作ります。今回の問題は演算子に + と - しかないので、リストで表現した式を計算することは簡単です。次のプログラムを見てください。
リスト : 式の計算 (+ と - だけ)
calc_one_exp(A, +, B, N):- N is A + B.
calc_one_exp(A, -, B, N):- N is A - B.
calc_exp([Num], Num).
calc_exp([A, Op, B | Rest], Num) :-
calc_one_exp(A, Op, B, Num1), calc_exp([Num1 | Rest], Num).
リストの先頭から数字 A, 演算子 Op, 数字 B を取り出して順番に計算していくだけです。最後に、リストの要素は数値一つになるので、calc_exp([Num], Num) で計算を終了します。
あとのプログラムは簡単なので、説明は割愛させていただきます。詳細はプログラムリスト１をお読みくださいませ。
それでは実行結果を示します。
?- solver. 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100 123 + 4 - 5 + 67 - 89 = 100 123 + 45 - 67 + 8 - 9 = 100 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100 123 - 45 - 67 + 89 = 100 false.
全部で 11 通りの解が出力されます。
%
% komachi.pl : パズル「小町算」の解法
%
% Copyright (C) 2005-2023 Makoto Hiroi
%
%
% 式の出力
%
print_expr([N]) :- format('~d = 100~n', N).
print_expr([N, Op | Xs]) :-
format('~d ~a ', [N, Op]), print_expr(Xs).
%
% 式の計算 (+, -) だけ
%
calc_one_exp(A, +, B, N):- N is A + B.
calc_one_exp(A, -, B, N):- N is A - B.
calc_exp([Num], Num).
calc_exp([A, Op, B | Rest], Num) :-
calc_one_exp(A, Op, B, Num1), calc_exp([Num1 | Rest], Num).
%
% 式の生成
%
set_op(N, Exp, [N, + | Exp]).
set_op(N, Exp, [N, - | Exp]).
set_op(N, [N1 | Rest], [N2 | Rest]) :- N2 is N1 * 10 + N.
make_exp(10, Exp) :-
reverse(Exp, Exp1), calc_exp(Exp1, N), N =:= 100, print_expr(Exp1), fail.
make_exp(N, Exp):-
N < 10, set_op(N, Exp, Exp1), N1 is N + 1, make_exp(N1, Exp1).
solver :- make_exp(2, [1]).
それではプログラムを作りましょう。式 SEND + MORE = MONEY は足し算なので、M が 1 であることはすぐにわかります。ここでは、それ以外の数字を求めるプログラムを作ります。単純な生成検定法でプログラムを作ると、次のようになります。
リスト : 覆面算
% 部分集合の判定
selects([], Ys).
selects([X | Xs], Ys) :- select(X, Ys, Ys1), selects(Xs, Ys1).
% Send + More = Money のチェック
check(S, E, N, D, O, R, Y, Send, More, Money) :-
Send is S * 1000 + E * 100 + N * 10 + D,
More is 1000 + O * 100 + R * 10 + E,
Money is 10000 + O * 1000 + N * 100 + E * 10 + Y,
Money =:= Send + More.
% パズルの解法
solver2(Send, More, Money) :-
selects([S, E, N, D, O, R, Y], [0, 2, 3, 4, 5, 6, 7, 8, 9]),
check(S, E, N, D, O, R, Y, Send, More, Money).
1 を除いた 9 個の数字の中から selects で数字を 7 個選びます。selects の説明は拙作のページ「集合としてのリスト」をお読みください。あとは述語 check で数値 Send, More, Money を計算して、Send + More = Money を満たしているかチェックします。とても簡単なプログラムですね。さっそく実行してみましょう。
?- solver2(Send,More,Money). Send = 9567, More = 1085, Money = 10652 ; false. ?-
答えは 9567 + 1085 = 10652 の 1 通りしかありません。
それではプログラムを作りましょう。今回は単純な「反復深化」で最短手順を求めてみます。盤面はリストで表して、b を黒石、w を白石、s を空き場所と定義します。すると、石を移動して新しい局面を生成する述語 new_state は次のようになります。
リスト : 新しい局面の生成する new_state([b, s | Rest], [s, b | Rest]). % 移動 1 new_state([s, w | Rest], [w, s | Rest]). % 移動 2 new_state([b, w, s | Rest], [s, w, b | Rest]). % 移動 3 new_state([s, b, w | Rest], [w, b, s | Rest]). % 移動 4 new_state([X | R1], [X | R2]) :- new_state(R1, R2).
new_state(Board, Newborad) は局面 board の石を移動して、新しい局面 Newboard を生成します。蛙跳びゲームの場合、石の移動パターンは次に示す 4 通りしかありません。
石の移動パターンは、リストの 1 行目から 4 行目までの規則で表しています。あとは、最後の規則で再帰呼び出しを行って Board をコピーし、1 から 4 の移動パターンにマッチングする場合は、石を移動して新しい局面を生成します。これで新しい局面をすべて生成することができます。
あとは単純な反復深化です。とくに難しいところはないので、説明は省略いたします。詳細はプログラムリスト３をお読みくださいませ。
それでは実行結果を示します。
?- solver3. ----- 15 ----- [b,b,b,s,w,w,w] [b,b,s,b,w,w,w] [b,b,w,b,s,w,w] [b,b,w,b,w,s,w] [b,b,w,s,w,b,w] [b,s,w,b,w,b,w] [s,b,w,b,w,b,w] [w,b,s,b,w,b,w] [w,b,w,b,s,b,w] [w,b,w,b,w,b,s] [w,b,w,b,w,s,b] [w,b,w,s,w,b,b] [w,s,w,b,w,b,b] [w,w,s,b,w,b,b] [w,w,w,b,s,b,b] [w,w,w,s,b,b,b] ----- 15 ----- [b,b,b,s,w,w,w] [b,b,b,w,s,w,w] [b,b,s,w,b,w,w] [b,s,b,w,b,w,w] [b,w,b,s,b,w,w] [b,w,b,w,b,s,w] [b,w,b,w,b,w,s] [b,w,b,w,s,w,b] [b,w,s,w,b,w,b] [s,w,b,w,b,w,b] [w,s,b,w,b,w,b] [w,w,b,s,b,w,b] [w,w,b,w,b,s,b] [w,w,b,w,s,b,b] [w,w,s,w,b,b,b] [w,w,w,s,b,b,b] false. ?-
15 手で解くことができました。ちなみに、単純なバックトラックでも 15 手で解くことができます。実をいうと、蛙跳びゲームは 15 手よりも長い手順はありません。つまり、この回数でないと解くことができないのです。
蛙跳びゲームのプログラムは、deepgreen さんの Web サイト「Computer Puzzle Solution」の掲示板 (リンク切れ) にあるプログラムを参考にさせていただきました。deepgreen さんに感謝いたします。
%
% kaeru.pl : 蛙跳びゲーム
%
% Copyright (C) 2005-2023 Makoto Hiroi
%
% 新しい局面の生成
new_state([b, s | Rest], [s, b | Rest]).
new_state([s, w | Rest], [w, s | Rest]).
new_state([b, w, s | Rest], [s, w, b | Rest]).
new_state([s, b, w | Rest], [w, b, s | Rest]).
new_state([X | R1], [X | R2]) :- new_state(R1, R2).
% 手順の表示
print_answer([]) :- !.
print_answer([State | Rest]) :-
print_answer(Rest), write(State), nl.
% 反復深化による解法
depth_search(Limit, Limit, [State | History]) :-
State == [w,w,w,s,b,b,b],
format('----- ~d -----~n', Limit),
print_answer([State | History]),
fail.
depth_search(N, Limit, [State | History]) :-
N < Limit,
new_state(State, NewState),
not(member(NewState, History)),
N1 is N + 1,
depth_search(N1, Limit, [NewState, State | History]).
solver3 :-
between(1, 20, N),
depth_search(0, N, [[b,b,b,s,w,w,w]]).
それではプログラムを作りましょう。この問題も単純な「反復深化」で解くことができます。最初にデータ構造を定義します。岸の状態は次に示すリストで表すことにします。
[Boat, M_left, E_left, M_right, E_right] Boat : left or right M_left : 左岸にいる宣教師の数 E_left : 左岸にいる先住民の数 M_right : 右岸にいる宣教師の数 E_right : 右岸にいる先住民の数
次はボートを動かして新しい局面を生成する述語 move_boat を作ります。次のリストを見てください。
リスト : ボートを動かす
% ボートに乗る組み合わせ : boat(M, E)
boat(1, 0).
boat(0, 1).
boat(1, 1).
boat(2, 0).
boat(0, 2).
% 移動 (left -> right)
move_boat([left,A,B,C,D], [right,A1,B1,C1,D1]) :-
boat(X, Y),
A1 is A - X,
A1 >= 0,
B1 is B - Y,
B1 >= 0,
C1 is C + X,
D1 is D + Y.
ボートは 2 人乗りなので、1 人だけ乗る場合が 2 通り、2 人で乗る場合が 3 通りあります。その組み合わせを述語 boat で定義します。
述語 move_boat は左岸から右岸へ渡る場合と、右岸から左岸へ渡る場合の 2 通りあります。左岸から右岸へ渡る場合、boat(X, Y) でボートに乗る人数を求め、左岸の人数を減らします。このとき、左岸の人数が負にならないようにチェックします。負になる場合は、その人数でボートに乗ることはできません。それから、右岸の人数を増やします。これで、左岸から右岸へ渡ることができます。右岸から左岸へ渡る規則も同様に作ることができます。
最後に、岸の状態が安全かチェックする述語 safe を作ります。次のリストを見てください。
リスト : 安全確認 safe([_,A,B,C,D]) :- A >= B, C >= D. safe([_,0,_,_,_]). safe([_,_,_,0,_]).
安全な状態は A >= B かつ C >= D だけではありません。この条件が成立しない場合でも、宣教師がいない場合は安全ですね。つまり、[left, 3, 2, 0, 1] のような状態は安全なわけです。これを 2, 3 行目の規則で表しています。
あとは単純な反復深化なので、説明は省略いたします。詳細はプログラムリスト４をお読みくださいませ。
それでは実行結果を示します。
?- solver4. ----- 11 ----- [left,3,3,0,0] [right,2,2,1,1] [left,3,2,0,1] [right,3,0,0,3] [left,3,1,0,2] [right,1,1,2,2] [left,2,2,1,1] [right,0,2,3,1] [left,0,3,3,0] [right,0,1,3,2] [left,1,1,2,2] [right,0,0,3,3] true . ?-
最短手数は 11 手になります。川渡りの問題はいろいろなバリエーションがあります。興味のある方は拙作のページ「Puzzle DE Programming」の「農夫と山羊と狼とキャベツの問題」や「嫉妬深い夫の問題」をお読みくださいませ。
%
% problem4.pl : 宣教師と先住民
%
% Copyright (C) 2005-2023 Makoto Hiroi
%
% データ
% [Boat, M_left, E_left, M_right, E_right]
% Boat : left or right
% M_left : 左岸にいる宣教師の数
% E_left : 左岸にいる先住民の数
% M_right : 左岸にいる宣教師の数
% E_right : 左岸にいる先住民の数
% ボートに乗る組み合わせ : boat(M, E)
boat(1, 0).
boat(0, 1).
boat(1, 1).
boat(2, 0).
boat(0, 2).
% 移動
move_boat([left,A,B,C,D], [right,A1,B1,C1,D1]) :-
boat(X, Y),
A1 is A - X,
A1 >= 0,
B1 is B - Y,
B1 >= 0,
C1 is C + X,
D1 is D + Y.
move_boat([right,A,B,C,D], [left,A1,B1,C1,D1]) :-
boat(X, Y),
C1 is C - X,
C1 >= 0,
D1 is D - Y,
D1 >= 0,
A1 is A + X,
B1 is B + Y.
% 安全確認
safe([_,A,B,C,D]) :- A >= B, C >= D.
safe([_,0,_,_,_]).
safe([_,_,_,0,_]).
% 手順の表示
print_answer([]) :- !.
print_answer([State | Rest]) :-
print_answer(Rest), write(State), nl.
% 反復深化
depth_search(Limit, Limit, [State | History]) :-
State == [right,0,0,3,3],
format('----- ~d -----~n', Limit),
print_answer([State | History]).
depth_search(N, Limit, [State | History]) :-
N < Limit,
move_boat(State, NewState),
safe(NewState),
not(member(NewState, History)),
N1 is N + 1,
depth_search(N1, Limit, [NewState, State | History]).
solver4 :-
between(1, 15, N),
depth_search(0, N, [[left,3,3,0,0]]).
それではプログラムを作ります。斗桶 (A) と 7 升ます (B) と 3 升ます (C) の状態をリスト [A, B, C] で表すことにします。油分け算の場合、次に示す 3 通りの操作があります。
ますは 2 つあるので、操作は全部で 6 通りになります。この操作を述語 transfer で定義します。次のリストを見てください。
リスト : 油を移す操作
% 油を移す
transfer_sub(From, To, Max, From1, To1) :-
From > 0,
To < Max,
X is Max - To,
((X < From) -> (From1 is From - X, To1 is To + X);
(From1 is 0, To1 is To + From)).
% A -> B
transfer([A, B, C], MAX_B, _, [NewA, NewB, C]) :-
transfer_sub(A, B, MAX_B, NewA, NewB).
% A -> C
transfer([A, B, C], _, MAX_C, [NewA, B, NewC]) :-
transfer_sub(A, C, MAX_C, NewA, NewC).
% B -> A
transfer([A, B, C], _, _, [NewA, 0, C]) :-
B > 0, NewA is A + B.
% C -> A
transfer([A, B, C], _, _, [NewA, B, 0]) :-
C > 0, NewA is A + C.
% B -> C
transfer([A, B, C], _, MAX_C, [A, NewB, NewC]) :-
transfer_sub(B, C, MAX_C, NewB, NewC).
% C -> B
transfer([A, B, C], MAX_B, _, [A, NewB, NewC]) :-
transfer_sub(C, B, MAX_B, NewC, NewB).
述語 transfer(State, MAX_B, MAX_C, NewState) は、状態 State から油を移して新しい状態 NewState を生成します。MAX_B はます B の大きさ、MAX_C はます C の大きさを表します。ますに油を注ぐ操作は transfer_sub で行います。From と To はますに入っている油の量、Max はます To の大きさです。油を注いだあと、ますに入っている油の量は From から Form1 に、To から To1 になります。
最初に、注ぐ油の量 From とます To の空き容量をチェックします。From が 0 または To が Max ならば、油を注ぐことはできません。次に、From と To の空き容量 X を比較します。From が X よりも多ければ、X だけ油を注ぐことができます。From1 は From - X に、To1 は To + X になります。そうでなければ、From を全部注ぐことができるので、From1 は 0 に To1 は To + From になります。
ますの油を斗桶に戻す操作 (B -> A, C -> A) は簡単です。ますの油 (B or C) を斗桶 (A) に加算して、ますを空にするだけです。
あとは、幅優先探索か反復深化を使って簡単に解くことができます。今回は「幅優先探索」でプログラムを作りました。とくに難しいところはないので、説明は省略いたします。詳細はプログラムリスト５をお読みくださいませ。
それでは実行結果を示します。
?- solver5. ----- 9 ----- [10,0,0] [3,7,0] [3,4,3] [6,4,0] [6,1,3] [9,1,0] [9,0,1] [2,7,1] [2,5,3] [5,5,0] false. ?-
最短手数は 9 手になりました。反復深化でも簡単にプログラムを作ることができるので、興味のある方は挑戦してみてください。
%
% abura.pl : 油分け算 (幅優先探索版)
%
% Copyright (C) 2005-2023 Makoto Hiroi
%
% 状態はリストで表す [A, B, C]
%
% 油を移す
transfer_sub(From, To, Max, From1, To1) :-
From > 0,
To < Max,
X is Max - To,
((X < From) -> (From1 is From - X, To1 is To + X);
(From1 is 0, To1 is To + From)).
% A -> B
transfer([A, B, C], MAX_B, _, [NewA, NewB, C]) :-
transfer_sub(A, B, MAX_B, NewA, NewB).
% A -> C
transfer([A, B, C], _, MAX_C, [NewA, B, NewC]) :-
transfer_sub(A, C, MAX_C, NewA, NewC).
% B -> A
transfer([A, B, C], _, _, [NewA, 0, C]) :-
B > 0, NewA is A + B.
% C -> A
transfer([A, B, C], _, _, [NewA, B, 0]) :-
C > 0, NewA is A + C.
% B -> C
transfer([A, B, C], _, MAX_C, [A, NewB, NewC]) :-
transfer_sub(B, C, MAX_C, NewB, NewC).
% C -> B
transfer([A, B, C], MAX_B, _, [A, NewB, NewC]) :-
transfer_sub(C, B, MAX_B, NewC, NewB).
% 手順を表示
print_answer([]) :- !.
print_answer([State | Rest]) :-
print_answer(Rest), write(State), nl.
% ゴールのチェック
check_goal(N, Goal, [Goal | Rest]) :-
format('----- ~d -----~n', N), print_answer([Goal | Rest]).
% 次の状態へ移行
extend_one_move(N, MAX_B, MAX_C, Goal, [State | Rest]) :-
transfer(State, MAX_B, MAX_C, NewState),
not(member(NewState, Rest)),
assert(move(N, [NewState, State | Rest])),
check_goal(N, Goal, [NewState, State | Rest]).
extend_move(N, MAX_B, MAX_C, Goal) :-
move(N, Move),
N1 is N + 1,
extend_one_move(N1, MAX_B, MAX_C, Goal, Move).
% 幅優先探索
solve(N, MAX_B, MAX_C, Goal) :-
not(extend_move(N, MAX_B, MAX_C, Goal)),
N1 is N + 1,
move(N1, _),
!,
solve(N1, MAX_B, MAX_C, Goal).
abura(Start, MAX_B, MAX_C, Goal) :-
assert(move(0, 0)), % dummy
retractall(move(_, _)),
assert(move(0, [Start])), solve(0, MAX_B, MAX_C, Goal).
solver5 :- abura([10, 0, 0], 7, 3, [5, 5, 0]).