M.Hiroi's Home Page

Prolog Programming

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

[ PrevPage | Prolog | NextPage ]

パズルに挑戦!

今回は 4 つのパズルを出題します。Prolog で解法プログラムを作成してください。

●問題1「魔方陣」

3 行 3 列の魔方陣を解くプログラムを作ってください。

[問題] 魔方陣

          図 : 魔方陣

上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。縦横斜めの合計が等しくなるように数字を配置してください。

解答

●問題2「騎士の巡歴 (Knight's Tour) 」

騎士 (ナイト) はチェスの駒のひとつで、将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。


                  図 : ナイトの巡歴

このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。大きな盤面を解くのは大変なので、3 行 4 列の盤面でナイトの移動経路を求めてください。プログラムを作る前に、自分で考えてみるのも面白いでしょう。

解答

●問題3「Hoppers」

Hoppers は「ペグ・ソリテア」と呼ばれるパズルのひとつです。出典は C magazine 2000 年 2 月号の「Cマガ電脳クラブ第 107 回 Hoppers」です。

ペグ・ソリテアは、盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。

盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。33 穴英国盤と Hoppers を図に示します。


      (1) 33 穴英国盤

     (2) Hoppers

    図 : ペグ・ソリテア

それぞれのマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。図では黒丸でペグを表し、白丸で空き場所を表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、ペグを取り除く位置によって、解けない場合もあるので注意してください。

それでは問題です。図 (2) に示したように、Hoppers の中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。

解答

●問題4「ニム(nim)」

ニムは「三山くずし」とも呼ばれている「石取りゲーム」です。ルールはとても簡単です。石の山を 3 つ作り、交互にどれかひとつの山から 1 個以上の石を取っていきます。複数の山から石を取ることはできません。そして、最後に石を取った方が勝ちとなります。

問題は、ニムをプレイするプログラムを作ることです。いきなり「作れ」といわれても困ってしまいますね。そこで、ヒントを出しましょう。ニムはとても簡単な方法で、とても強いプログラムを作ることができます。

各山の石の数を N1, N2, N3 として、ビットごとの排他的論理和 N1 xor N2 xor N3 を計算します。これを「ニム和」といいます。そして、ニム和を 0 にすることができれば、勝つことができるのです。ここで、石を全部取った状態は、ニム和が 0 になることに注意してください。ニム和が 0 の状態では、どのような石の取り方をしても、ニム和は 0 になりません。したがって、自分の手番でニム和を 0 にすることができれば、相手に最後の石を取られることはないわけです。もし、ニム和を 0 にできなければ、最大の山から石をひとつだけとって、相手のミスを待ちます。

これで本当に強くなるのか、実際にプログラムを作って確かめてください。

解答


●問題1「魔方陣」解答

リスト : 魔方陣

magic :-
    permutation([1,2,3,4,5,6,7,8,9], [A,B,C,D,E,F,G,H,I]),
    X is A + B + C,
    X =:= D + E + F,
    X =:= G + H + I,
    X =:= A + D + G,
    X =:= B + E + H,
    X =:= C + F + I,
    X =:= A + E + I,
    X =:= C + E + G,
    format('~d ~d ~d~n~d ~d ~d~n~d ~d ~d~n~n', [A,B,C,D,E,F,G,H,I]),
    fail.

単純な生成検定法です。permutation/2 は SWI-Prolog に用意されている順列を生成する述語です。簡単な使用例を示します。

?- permutation([a,b,c], Xs), write(Xs), nl, fail.
[a,b,c]
[a,c,b]
[b,a,c]
[b,c,a]
[c,a,b]
[c,b,a]
false.

?- permutation([a,b,c,d], Xs), write(Xs), nl, fail.
[a,b,c,d]
[a,b,d,c]
[a,c,b,d]
[a,c,d,b]
[a,d,b,c]
[a,d,c,b]
[b,a,c,d]
[b,a,d,c]
[b,c,a,d]
[b,c,d,a]
[b,d,a,c]
[b,d,c,a]
[c,a,b,d]
[c,a,d,b]
[c,b,a,d]
[c,b,d,a]
[c,d,a,b]
[c,d,b,a]
[d,a,b,c]
[d,a,c,b]
[d,b,a,c]
[d,b,c,a]
[d,c,a,b]
[d,c,b,a]
false.

実行結果は次のようになります。

?- time(magic).
2 7 6
9 5 1
4 3 8

2 9 4
7 5 3
6 1 8

4 3 8
9 5 1
2 7 6

4 9 2
3 5 7
8 1 6

6 1 8
7 5 3
2 9 4

6 7 2
1 5 9
8 3 4

8 1 6
3 5 7
4 9 2

8 3 4
1 5 9
6 7 2

% 3,341,780 inferences, 0.401 CPU in 0.401 seconds (100% CPU, 8325728 Lips)
false.

解は 8 通り出力されましたが、重複解を取り除くと解は一通りしかありません。重複解のチェックは面倒だと思われる方もいるでしょう。ところが、下図のように四隅の大小関係を利用すると簡単です。


      図 : 対称解のチェック

魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。また、順列を生成するとき、重複解のチェックを入れると枝刈りと同じ効果を得ることができます。興味のある方は試してみてください。


●問題2「騎士の巡歴 (Knight's Tour) 」解答

それではプログラムを作りましょう。次の図を見てください。


          図 : ナイトの移動

図 (A) のように、3 行 4 列盤の各マスに名前を付けて表します。すると、ナイトの移動は (B) のようにグラフで表すことができます。これならば、コンピュータを使わなくても解くことができますね。プログラムも隣接関係を定義すれば簡単です。次のリストを見てください。

リスト : ナイトの移動

next(a, f). next(a, h). next(b, g). next(b, i).
next(c, d). next(c, h). next(d, i). next(d, k).
next(e, j). next(e, l). next(f, g). next(f, k).
next(g, l). next(i, j).

jump(X, Y) :- next(X, Y).
jump(X, Y) :- next(Y, X).

あとは単純な深さ優先探索でナイトの経路を探すだけです。プログラムは次のようになります。

リスト : ナイトの巡歴

search(12, Path) :-
    reverse(Answer, Path), write(Answer), nl, !, fail.

search(N, [Postion | Rest]) :-
    jump(Postion, NextPostion),
    not(member(NextPostion, Rest)),
    N1 is N + 1,
    search(N1, [NextPostion, Postion | Rest]).

経路はリストで表します。述語 search の最初の引数 N が訪れたマスの個数を表し、 次の引数が経路を表します。最初の規則で、N が 12 になったら見つけた経路を write で表示します。次の経路を探すため、fail で強制的にバックトラックします。また、これ以上ナイトを動かす必要はないので、次の規則を実行しないようにカット (!) を使っていることに注意してください。

次の規則でナイトを移動します。次の移動地点を述語 jump で求め、その場所が経路に含まれていないか述語 member を使ってチェックします。あとは search を再帰呼び出しするだけです。

プログラムはこれだけです。とても簡単ですね。それでは実行してみましょう。

?- search(1, [a]).
[a,h,c,d,k,f,g,l,e,j,i,b]
[a,h,c,d,k,f,g,b,i,j,e,l]
false.

2 通りの経路を見つけることができました。

このほかに、どのマスにもちょうど一回ずつ訪れたのち、最初のマスに戻ってくることを条件にする場合もあります。この場合、3 行 4 列盤には解がありません。また、N 行 M 列の盤面でマスの個数が奇数のときにも、最初のマスに戻ることはできません。これは簡単に証明できるので、息抜きや気分転換に考えてみてください。

答えはこちら


●問題3「Hoppers」解答

それでは、プログラムを作りましょう。今回は、Hoppers の盤面をリストではなく、整数値のビットを使って表すことにします。つまり、ペグがある状態をビットオンで、ペグがない状態をビットオフで表します。位置とビットの対応は、下図の座標を見てください。


              図 : Hoppers

ペグの移動は跳び先表を用意すると簡単です。次のプログラムを見てください。

リスト : 跳び先表

/* 跳び先表 */
jump_table(0, 1, 2).  jump_table(0, 3, 6).   jump_table(0, 5, 10).
jump_table(1, 3, 5).  jump_table(1, 6, 11).  jump_table(1, 4, 7).
jump_table(2, 4, 6).  jump_table(2, 7, 12).
jump_table(3, 6, 9).
jump_table(4, 6, 8).
jump_table(5, 6, 7).  jump_table(5, 8, 11).
jump_table(6, 8, 10). jump_table(6, 9, 12).
jump_table(7, 9, 11).
jump_table(10, 11, 12).

/* ペグの移動 */
jump(From, Del, To) :- jump_table(From, Del, To).
jump(From, Del, To) :- jump_table(To, Del, From).

ペグの跳び先表は jump_table で定義します。jump_table は一方向ではなく双方向の関係を表していることに注意してください。たとえば、jump_table(0, 1, 2) は 0 から 1 を跳び越して 2 へ移動するだけではなく、2 から 1 を跳び越して 0 へ移動することも表しています。述語 jump(From, Del, To) は jump_table を使って、From の位置にあるペグが Del の位置にあるペグを飛び越して To に移動することを表しています。

実際にペグを動かす場合、動かすペグと跳び越すペグがあり、移動先の位置にペグがないことを確認しなければいけません。ペグを動かして新しい盤面を生成するプログラムは、次のようになります。

リスト : ペグの移動

jump_peg(Peg, Del, To, Board, NewBoard) :-
    PegBit is 1 << Peg,
    Board /\ PegBit > 0,    % Peg の位置にペグがある
    DelBit is 1 << Del,
    Board /\ DelBit > 0,    % Del の位置にペグがある
    ToBit is 1 << To,
    Board /\ ToBit =:= 0,   % To の位置は空いている
    NewBoard is (Board /\ ((\ PegBit) /\ (\ DelBit))) \/ ToBit.

ビット操作でペグの有無をチェックしています。条件を満たしていたら、Peg と Del のビットをオフに、To のビットをオンにして、新しい盤面 NewBoard を生成します。

あとは単純な反復深化で最短手順を求めます。プログラムは次のようになります。

リスト : 反復深化による解法

search_id(Limit, Limit, Board, Move) :-
    Board =:= 0b1000000, !, reverse(Move, Ans), write(Ans), nl.
search_id(N, Limit, Board, [[PrevFrom, PrevTo] | Rest]) :-
    N =< Limit,
    jump(From, Del, To),
    jump_peg(From, Del, To, Board, NewBoard),
    ((PrevTo =:= From) -> N1 is N ; N1 is N + 1),
    search_id(N1, Limit, NewBoard, [[From, To], [PrevFrom, PrevTo] | Rest]).

述語 search_id の引数 N が跳んだ回数、Limit は反復深化の上限値、Board が盤面で、最後の引数が移動手順を格納するリストです。移動手順は、[移動元の位置, 移動先の位置] で表します。

このプログラムのポイントは連続跳びを判断するところです。直前に移動した場所 PrevTo からペグを動かすときは、連続跳びと判断することができますね。したがって、PrevTo と From が等しい場合は跳んだ回数 N を増やしません。異なっている場合は連続跳びではないので N をひとつ増やします。

あとは search_id を再帰呼び出しして、上限値 Limit まで深さ優先探索を行います。上限値に達したとき、最初の規則で 6 の位置にペグがひとつ残っているかチェックします。条件を満たしていれば、移動手順 Move を reverse で逆にしてから write で表示します。すべての解を表示すると時間がかかりそうなので、今回は解をひとつ見つけたら探索を終了することにします。

それから、跳び回数 N が上限値 Limit に達していても、2 番目の規則は実行されることに注意してください。回数が Limit に達していても連続跳びすることで解ける場合もあるので、N =< Limit を N < Limit にすると最短手順を求めることができなくなります。ご注意くださいませ。

これでプログラムは完成です。それでは実行してみましょう。最初の移動は、四隅にあるペグのひとつを中央に動かす手順しかありません。そこで、最初は 0 のペグを 6 へ動かすことに決めて、その状態から探索を開始します。

リスト : 実行

test :- between(4, 11, Limit), 
        write(Limit), nl,
        search_id(1, Limit, 0b1111111110110, [[0, 6]]).
?- time(test).
4
5
6
7
[[0,6],
 [9,3],
 [2,6],
 [8,4],
 [10,0],[0,2],[2,6],
 [11,1],
 [12,2],[2,0],[0,6]]
% 2,142,720 inferences, 0.351 CPU in 0.351 seconds (100% CPU, 6098142 Lips)
true .

7 手で解くことができました。移動手順はリストを表示しているだけなので、連続跳びがわかるように手作業でちょっと直してみました。プログラムの改良は皆さんにお任せいたしますね。実行時間は 0.35 秒でした。最近のパソコンは高性能なので、穴の数が少ない盤面であれば、単純な反復深化でも高速に解くことができるようです。


●問題4「ニム(nim)」解答

それではプログラムを作りましょう。ポイントは、ニム和を 0 にする指し手を求める処理です。次の図を見てください。

三山 : [1, 2, 4] 

ニム和 :  0b001 xor 0b010 xor 0b100 = 0b111 (7)

指し手の決定

0b001 (1) xor 0b111 = 0b110 (6)  1 - 6 = -5 NG 
0b010 (2) xor 0b111 = 0b101 (5)  2 - 5 = -3 NG 
0b100 (4) xor 0b111 = 0b011 (3)  4 - 3 = 1  OK 

最後の山から石をひとつ取る

ニム和 : 0b001 xor 0b010 xor 0b011 = 0


        図 : 指し手の決定

三山をリストで表します。今、石は 1, 2, 4 個あるとします。この場合、ニム和は 0b111 (7) になります。ニム和を 0 にするには、同じ数値 0b111 と排他的論理和をとります。つまり、0b001 xor 0b010 xor 0b100 xor 0b111 とすればいいわけです。ここで、論理演算は交換法則と結合法則が成立するので、0b111 の位置を入れ替えて、各山の石数と 0b111 の排他的論理和を先に計算してみましょう。

最初の山は 0b001 xor 0b111 = 0b110 になります。ここで、最初の山の石数 0b001 を 0b110 にすることができれば、ニム和が 0 になることに注意してください。この場合は石を 1 個から 6 個へと 5 個増やすことになり、残念ながら実現できません。次の山も 0b010 xor 0b111 = 0b101 になり、石を 3 個増やさないといけません。最後の山は 0b100 xor 0b111 = 0b011 ですから、石を 4 個から 3 個へ 1 個減らせばニム和を 0 にすることができますね。したがって、指し手は「最後の山から石を 1 個取る」となります。

このように、簡単な方法でコンピュータの指し手を求めることができます。プログラムは次のようになります。

リスト : コンピュータの指し手

/* コンピュータの指し手 */
com_move(Nim, Move) :-
    nim_sum(Nim, Sum),
    (Sum =:= 0 -> unsafe_move(Nim, Move) ; safe_move(0, Nim, Sum, Move)).

/* ニム和を計算 */
nim_sum([N0, N1, N2], NimSum) :- NimSum is N0 xor N1 xor N2.

/* ニム和を 0 にする取り方 */
safe_move(Pos, [M | _], Sum, [Pos, Num]) :-
    Num is M - (M xor Sum), Num > 0.
safe_move(Pos, [_ | Rest], Sum, Move) :-
    Pos1 is Pos + 1, safe_move(Pos1, Rest, Sum, Move).

/* 石がいちばん多い山からひとつ取る */
unsafe_move(Nim, [Pos, 1]) :- max_sum(Nim, Pos).

/* 石がいちばん多い山を求める */
max_sum([N0, N1, N2], 0) :- N0 > 0, N0 >= N1, N0 >= N2.
max_sum([N0, N1, N2], 1) :- N1 > 0, N1 >= N0, N1 >= N2.
max_sum([N0, N1, N2], 2) :- N2 > 0, N2 >= N0, N2 >= N1.

指し手はリスト [山, 取る石の数] で表すことにします。コンピュータの指し手は述語 com_move で求めます。引数 Nim が三山を表すリスト、Move が求める指し手を表します。まず、述語 nim_sum でニム和を求めます。その値が 0 ならば、石がいちばん多い山からひとつだけ取ります。この処理を述語 unsafe_move で行います。ニム和が 0 でなければ、述語 safe_move でニム和が 0 になるように石を取ります。

safe_move の引数 Pos が山の位置、次の引数が三山を表すリスト、Sum がニム和で、最後の引数が指し手を表しています。石の個数 (M) を調べて M - (M xor Sum) が 0 より大きければ、その山から石を取ることができます。そうでなければ、次の規則でほかの山を調べます。unsafe_move は、石がいちばん多い山から石をひとつ取ります。山は 3 つしかないので、述語 max_sum では単純な方法でいちばん多い山を求めています。

あとはとくに難しいところはないでしょう。詳細は プログラムリスト をご覧ください。それでは実行してみましょう。

?- start.
turn is human : Nim is (5, 2, 3)
|: [0,3].
Move is (0, 3) : Nim is (2, 2, 3)
turn is com : Nim is (2, 2, 3)
Move is (0, 1) : Nim is (1, 2, 3)
turn is human : Nim is (1, 2, 3)
|: [2,1].
Move is (2, 1) : Nim is (1, 2, 2)
turn is com : Nim is (1, 2, 2)
Move is (0, 1) : Nim is (0, 2, 2)
turn is human : Nim is (0, 2, 2)
|: [1,2].
Move is (1, 2) : Nim is (0, 0, 2)
turn is com : Nim is (0, 0, 2)
Move is (2, 2) : Nim is (0, 0, 0)
com win!!
true .

うーん、やっぱりニム和を計算しないと勝てませんね。皆さんも挑戦してみてください。

●プログラムリスト

リスト : ニム(nim)

/* 三山を作る */
make_nim(3, Nim, Nim).
make_nim(N, Lst, Nim) :-
    N < 3,
    M  is 1 + random(10),   % 1 - 10 まで
    N1 is N + 1,
    make_nim(N1, [M | Lst], Nim).

/* 入力のチェック */
check_move(Nim, [Postion, Number]) :-
    0 =< Postion, Postion =< 2,
     nth0(Postion, Nim, M), M > 0, M >= Number.

/* 指し手の入力 [位置, 個数] */
input_move(Nim, Move) :-
    repeat,
    read(Move), length(Move, 2), check_move(Nim, Move), !.

/* 石がいちばん多い山を求める */
max_sum([N0, N1, N2], 0) :- N0 > 0, N0 >= N1, N0 >= N2.
max_sum([N0, N1, N2], 1) :- N1 > 0, N1 >= N0, N1 >= N2.
max_sum([N0, N1, N2], 2) :- N2 > 0, N2 >= N0, N2 >= N1.

/* 石がいちばん多い山からひとつ取る */
unsafe_move(Nim, [Pos, 1]) :- max_sum(Nim, Pos).

/* ニム和を 0 にする取り方 */
safe_move(Pos, [M | _], Sum, [Pos, Num]) :-
    Num is M - (M xor Sum), Num > 0.
safe_move(Pos, [_ | Rest], Sum, Move) :-
    Pos1 is Pos + 1, safe_move(Pos1, Rest, Sum, Move).

/* ニム和を計算 */
nim_sum([N0, N1, N2], NimSum) :- NimSum is N0 xor N1 xor N2.

/* コンピュータの指し手 */
com_move(Nim, Move) :-
    nim_sum(Nim, Sum),
    (Sum =:= 0 -> unsafe_move(Nim, Move) ; safe_move(0, Nim, Sum, Move)).

/* 石を取る */
get_stone(Pos, [Pos, N1], [N2 | Rest], [M | Rest]) :- M is N2 - N1.
get_stone(N0, [Pos, N1], [N2 | Rest], [N2 | Result]) :-
    M is N0 + 1, get_stone(M, [Pos, N1], Rest, Result).

/* ゲームの実行 */
play_nim(Turn, Nim) :-
    format('turn is ~a : Nim is (~d, ~d, ~d)~n', [Turn | Nim]),
    (Turn == com -> (com_move(Nim, Move), Next = human) ;
                    (input_move(Nim, Move), Next = com)),
    get_stone(0, Move, Nim, NewNim),
    format('Move is (~d, ~d) ', Move),
    format(': Nim is (~d, ~d, ~d)~n', NewNim),
    (NewNim == [0, 0, 0] -> format('~a win!!~n', [Turn]) ;
                            play_nim(Next, NewNim)).

/* ゲームの開始 */
start :- make_nim(0, [], Nim), play_nim(human, Nim).

初版 2001 年 8 月 13 日
改訂 2023 年 5 月 7 日

Copyright (C) 2001-2023 Makoto Hiroi
All rights reserved.

[ PrevPage | Prolog | NextPage ]