Prologで4ナイト入れ替え問題を実装
4 Knights Problem?
4 Knights Problemという問題があります。「ナイト 入れ替え チェス」などとググれば、簡単にヒットしますが、簡単に説明すると、3x3のマスの四隅に白・黒のチェスのナイトが２つずつ置かれていて、それを動かして、白と黒の位置を交換するという問題です。本来のナイトの動きと異なる移動をしたり、盤面ごと回転させるというのはダメ。
今回私は必要に迫られて、このパズルを実装せざるを得なくなりました（ソルバではなく、パズルを人間が遊ぶための対話環境！）。
以下のような初期状態からはじまり、
| ♘ | ♘ | |
| ♞ | ♞ |
以下のような終了状態に移動させるのが目標。
| ♞ | ♞ | |
| ♘ | ♘ |
Java Appletで実装されたゲームがたくさんあるので、それでチャレンジしてみると面白いです。
Prologによる実装
諸事情により、Prologでこのゲームを実装しました。短いコードですので以下にそのまま書きます。
遊び方
[From, To]:
というプロンプトが出ますので、移動元のマスの番号と、移動先のマスの番号を以下のように入力してください。
[Fromt, To]: [0, 1].
なお、マスの番号は、左上から右下へ、0, 1, 2, ... 8 というように振られています。
| 0 | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
ソースコード
% start game chess :- game_loop([w, x, b, x, x, x, w, x, b]). show([A, B, C, D, E, F, G, H, I]) :- write(A), write(' '), write(B), write(' '), write(C), nl, nl, write(D), write(' '), write(E), write(' '), write(F), nl, nl, write(G), write(' '), write(H), write(' '), write(I), nl, nl. % replace(idx, NewValue, List1, List2) % List1のidx番目の要素をNewValueに置き換えたものはList2である。 replace(0, NewValue, [_|Tail], [NewValue|Tail]) :- !. replace(Idx, NewValue, [Head|Tail], [Head|Tail2]) :- Idx2 is Idx - 1, replace(Idx2, NewValue, Tail, Tail2). % Board上のFromにある駒を、Toに移動させたら、NewBoardになる。 move(From, To, Board, NewBoard) :- nth0(From, Board, Elem1), nth0(To, Board, Elem2), Elem1 \= x, Elem2 = x, replace(From, Elem2, Board, PreNewBoard), replace(To, Elem1, PreNewBoard, NewBoard). % can_move(X, Y) % 盤面上の位置Xにいるナイトは、位置Yへ移動できる。 can_move(0, 5). can_move(0, 7). can_move(1, 6). can_move(1, 8). can_move(2, 3). can_move(2, 7). can_move(3, 2). can_move(3, 8). can_move(5, 0). can_move(5, 6). can_move(6, 1). can_move(6, 5). can_move(7, 0). can_move(7, 2). can_move(8, 1). can_move(8, 3). can_move(_, _) :- write('cannot move'), nl, fail. % 終了条件 game_loop([b, x, w, x, x, x, b, x, w]) :- !, write('finish!'), nl. % ゲームのループ game_loop(Board) :- show(Board), write('[From, To]: '), read(FromTo), [From, To] = FromTo, % 移動して、次の入力へ can_move(From, To), (move(From, To, Board, NewBoard), !, game_loop(NewBoard)); game_loop(Board).
実行例
実行例をなんとなく書いておきます。ピリオドを忘れないのがポイントです。wは白、bは黒、xは空のマスの意味です。
$ swipl ?- [fourknights]. ?- chess. w x b x x x w x b [From, To]: [0,5]. x x b x x w w x b [From, To]:
