M.Hiroi's Home Page

Prolog Programming

お気楽 Prolog プログラミング入門

[ PrevPage | Prolog | NextPage ]

パズルに挑戦 (2)

今回は簡単なパズルを 5 問出題します。Prolog で解法プログラムを作成してください。

●小町算

[問題1] 小町算

1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。

例:1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を 小町数 といいます。たとえば、123456789 とか 321654987 のような数字です。小町算 というものもあり、たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。問題1は小町算の中でも特に有名なパズルです。

解答

●覆面算

[問題2] 覆面算
      S E N D
  +   M O R E
 -------------
    M O N E Y

  図 : 覆面算

計算式の数字を文字や記号に置き換えて、それを元の数字に戻すパズルを 覆面算 といいます。異なる文字は異なる数字を表し、同じ文字は同じ数字を表します。使用する数字は 0 から 9 までで、最上位の桁に 0 を入れることはできません。

問題2はデュードニーが 1924 年に発表したもので、覆面算の古典といわれる有名なパズルです。

解答

●蛙跳びゲーム

[問題3] 蛙跳びゲーム

        図 : 蛙跳びゲーム

蛙跳びゲームは黒石と白石を使って遊ぶ、いわゆる 飛び石ゲーム と呼ばれる種類のパズルです。上図のように、蛙跳びゲームは黒石と白石を入れ替えることができれば成功です。スタートからゴールまでの最短手順を求めてください。

石を動かす規則は次のとおりです。

石の跳び越しは次の図を参考にしてください。


            図 : 石の跳び越し

解答

●川渡りの問題

[問題4] 宣教師と人食い人

3 人の宣教師と 3 人の人食い人が川を渡ることになりました。川には 2 人乗りのボートが 1 そうしかありません。どのような時でも人食い人の数が宣教師の数よりも多いと、宣教師は殺されてしまいます。6 人が安全に川を渡る最短手順を求めてください。

問題4は「川渡りの問題」とか「渡船問題」と呼ばれる古典的なパズルの一種です。その中でも「宣教師と人食い人」は特に有名な問題です。

解答

●油分け算

[問題5] 油分け算

斗桶に油が 1 斗(= 10 升)あります。これを 5 升ずつ 2 つの油に分けたいのですが、手元には 7 升ますと 3 升ますが 1 つずつしかありません。この 2 つのますを使って油を二等分してください。

油分け算は江戸時代の和算書『塵劫記(じんこうき)』にある問題です。

解答

●参考文献

  1. Leon Sterling, Ehud Shapiro, 『Prolog の技芸』, 共立出版, 1988
  2. 奥村晴彦, 『C言語による最新アルゴリズム事典』, 技術評論社, 1991
  3. 中村義作, 『どこまで解ける日本の算法 和算で頭のトレーニング』, 講談社(ブルーバックス), 1994
  4. 秋山仁, 中村義作, 『ゲームにひそむ数理』, 森北出版株式会社, 1998

●問題1「小町算」の解答

それではプログラムを作りましょう。式は次のようにリストで表すことにします。

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, write(Exp1), nl, 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 になれば write で式を出力します。

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) で計算を終了します。

それでは実行結果を示します。

solve :- make_exp(2, [1]).

?- solve.
[1, +, 2, +, 3, -, 4, +, 5, +, 6, +, 78, +, 9]
[1, +, 2, +, 34, -, 5, +, 67, -, 8, +, 9]
[1, +, 23, -, 4, +, 5, +, 6, +, 78, -, 9]
[1, +, 23, -, 4, +, 56, +, 7, +, 8, +, 9]
[12, +, 3, +, 4, +, 5, -, 6, -, 7, +, 89]
[12, +, 3, -, 4, +, 5, +, 67, +, 8, +, 9]
[12, -, 3, -, 4, +, 5, -, 6, +, 7, +, 89]
[123, +, 4, -, 5, +, 67, -, 89]
[123, +, 45, -, 67, +, 8, -, 9]
[123, -, 4, -, 5, -, 6, -, 7, +, 8, -, 9]
[123, -, 45, -, 67, +, 89]

No

全部で 11 通りの解が出力されます。ところで、今回は数式を表すリストをそのまま出力していますが、これを普通の数式で表示するとわかりやすくなるでしょう。興味のある方はプログラムを改造してみてください。


●プログラムリスト1

%
% komachi.swi : パズル「小町算」の解法
%
%               Copyright (C) 2005 Makoto Hiroi
%

%
% 式の計算 (+, -) だけ
%
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, write(Exp1), nl, fail.

make_exp(N, Exp):-
    N < 10, set_op(N, Exp, Exp1), N1 is N + 1, make_exp(N1, Exp1).

solve :- make_exp(2, [1]).

●問題2「覆面算」の解答

それではプログラムを作りましょう。式 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.

% パズルの解法
solve_puz(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 を満たしているかチェックします。とても簡単なプログラムですね。さっそく実行してみましょう。

?- solve_puz(Send, More, Money).

Send = 9567
More = 1085
Money = 10652 ;

No

答えは 9567 + 1085 = 10652 の 1 通りしかありません。使用した処理系は SWI-Prolog で、実行時間は M.Hiroi のオンボロマシン (Windows 95, Pentium 166 MHz) で約 27 秒でした。けっこう時間ががかかりますね。興味のある方は、ほかの方法でも試してみてください。


●問題3「蛙跳びゲーム」の解答

それではプログラムを作りましょう。今回は単純な「反復深化」で最短手順を求めてみます。盤面はリストで表して、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. 黒石が右隣の空き場所へ移動
  2. 白石が左隣の空き場所へ移動
  3. 黒石が白石を跳び越して右側の空き場所へ移動
  4. 白石が黒石を跳び越して左側の空き場所へ移動

石の移動パターンは、リストの 1 行目から 4 行目までの規則で表しています。あとは、最後の規則で再帰呼び出しを行って Board をコピーし、1 から 4 の移動パターンにマッチングする場合は、石を移動して新しい局面を生成します。これで新しい局面をすべて生成することができます。

あとは単純な反復深化です。とくに難しいところはないので、説明は省略いたします。詳細は プログラムリスト3 をお読みくださいませ。

それでは実行結果を示します。

?- solve.
----- 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]

No

15 手で解くことができました。ちなみに、単純なバックトラックでも 15 手で解くことができます。実をいうと、蛙跳びゲームは 15 手よりも長い手順はありません。つまり、この回数でないと解くことができないのです。

●謝辞

蛙跳びゲームのプログラムは、deepgreen さんの Web サイト Computer Puzzle Solution掲示板 にあるプログラムを参考にさせていただきました。deepgreen さんに感謝いたします。


●プログラムリスト3

%
% kaeru.swi : 蛙跳びゲーム
%
%             Copyright (C) 2005 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]).

solve :- 
    between(1, 20, N),
    depth_search(0, N, [[b,b,b,s,w,w,w]]).

●問題4「宣教師と人食い人」の解答

それではプログラムを作りましょう。この問題も単純な「反復深化」で解くことができます。最初にデータ構造を定義します。岸の状態は次に示すリストで表すことにします。

[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 行目の規則で表しています。

あとは単純な反復深化なので、説明は省略いたします。詳細は プログラムリスト4 をお読みくださいませ。

それでは実行結果を示します。

?- solve.
----- 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]

Yes

最短手数は 11 手になります。川渡りの問題はいろいろなバリエーションがあります。興味のある方は、拙作のページ Puzzle DE Programming農夫と山羊と狼とキャベツの問題嫉妬深い夫の問題 をお読みくださいませ。


●プログラムリスト4

%
% 宣教師と人食い人
%
%       Copyright (C) 2005 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]).

solve :- 
    between(1, 15, N),
    depth_search(0, N, [[left,3,3,0,0]]).

●問題5「油分け算」の解答

それではプログラムを作ります。斗桶 (A) と 7 升ます (B) と 3 升ます (C) の状態をリスト [A, B, C] で表すことにします。油分け算の場合、次に示す 3 通りの操作があります。

  1. 斗桶からますへ油を注ぐ。
  2. ますの油を斗桶に戻す。
  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) に加算して、ますを空にするだけです。

あとは、幅優先探索反復深化 を使って簡単に解くことができます。今回は「幅優先探索」でプログラムを作りました。とくに難しいところはないので、説明は省略いたします。詳細は プログラムリスト5 をお読みくださいませ。

それでは実行結果を示します。

?- solve.
----- 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]

No

最短手数は 9 手になりました。反復深化でも簡単にプログラムを作ることができるので、興味のある方は挑戦してみてください。


●プログラムリスト5

%
% abura.swi : 油分け算 (幅優先探索版)
%
%             Copyright (C) 2005 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).

solve :- abura([10, 0, 0], 7, 3, [5, 5, 0]).

Copyright (C) 2005 Makoto Hiroi
All rights reserved.

[ PrevPage | Prolog | NextPage ]