1

问题是在 3x3 棋盘中用两个白骑士交换 2 个黑骑士位置，请参阅链接http://www.puzzles.com/puzzleplayground/FourKnights/FourKnights.htm 我必须让 Prolog 给我至少一个解决方案，在这些步骤之后，我完全迷失了。

%mouvement possibilities
mouv(2,1).
mouv(-2,1).
mouv(2,-1).
mouv(-2,-1).
mouv(1,2).
mouv(-1,2).
mouv(1,-2).
mouv(-1,-2).
%conditions for valid mouvement

%not going out of the small chessboard
pos(X,Y):- X<4 ,X>0,Y<4,Y>0.

%free position
%????????

%initial positions
kgt(b,3,1).
kgt(b,3,3).
kgt(w,1,3).
kgt(w,1,1).
%mouv knight

%???

接下来我该怎么办？

4

1 回答 1

3

一种简单（且效率低下）的方法可以对棋子应用有效的移动，并迭代直到出现所需的位置。当然，我们应该避免重复已经访问过的位置，因为这会导致无限循环。

然后我们需要一种方法来表示这个搜索空间。板列表是显而易见的选择。

一个棋盘可以是一个排序的棋子列表，在查看我们是否到达目标位置时很方便，并且移动后的棋盘还没有被访问过。

puzzle :-
  setof(kgt(C,X,Y), kgt(C,X,Y), InitialBoard),
  apply_moves([InitialBoard], Boards),
  maplist(writeln, Boards).

apply_moves([Board|Visited], Solution) :-
  move_knight(Board, Moved),
  not_visited(Moved, Visited),
  Next = [Moved,Board|Visited],
  (  is_target(Moved)
  -> Solution = Next
  ;  apply_moves(Next, Solution)
  ).

move_knight(Board, Moved) :-
  select(kgt(C,X,Y), Board, B1),
  ...

is_target(Board) :-
  ...

not_visited(Moved, Visited) :-
  \+ memberchk(Moved, Visited).

看看你是否可以填写省略号。

于 2013-01-21T15:05:05.277 回答