尝试解决 Prolog 中的跳钉拼图 [英] Trying to solve the peg jump puzzle in Prolog
问题描述
九个洞有 8 个钉子.一开始，左边的四个红色钉子和右边的四个蓝色钉子，中间有一个空洞.谜题是将所有红色向右移动，将蓝色钉向左移动(在其他相反方向).这些是这样做的合法举措:
There are 8 pegs in nine holes. At beginning, the four red pegs on the left and the four blue pegs are on the right, and one empty hole between them. The puzzle is to move all the red to the right, and blue pegs to the left(in other opposite). These are the legal moves to do so:
- 钉子只能向前移动(红色可以向右移动，蓝色可以向左移动).
- 挂钩可以向前移动一步进入打开位置.
- 如果超出它的位置是开放的，则挂钩可能会跳过正好相反颜色的一个挂钩.
这是我写的，但它不起作用
This is what I wrote, but it doesn't work
% Form of board, b for blue, r for red, o for empty.
% [ [r,r,r,r], [o], [b,b,b,b] ]
% jumps
linjmp([x, x, o | T], [o, o, x | T]).
linjmp([o, x, x | T], [x, o, o | T]).
linjmp([H|T1], [H|T2]) :- linjmp(T1,T2).
% Series of legal boards.
series(From, To, [From, To]) :- jump(From, To).
series(From, To, [From, By | Rest])
:- jump(From, By),
series(By, To, [By | Rest]).
% Print a series of boards. This puts one board per line and looks a lot
% nicer than the jumble that appears when the system simply beltches out
% a list of boards. The write_ln predicate is a built-in which always
% succeeds (is always satisfied), but prints as a side-effect. Therefore
% print_series(Z) will succeed with any list, and the members of the list
% will be printed, one per line, as a side-effect of that success.
print_series_r([]) :-
write_ln('*******************************************************').
print_series_r([X|Y]) :- write_ln(X), print_series_r(Y).
print_series(Z) :-
write_ln('\n*******************************************************'),
print_series_r(Z).
% A solution.
solution(L) :- series([[r,r,r,r], [o], [b,b,b,b]],
[[b,b,b,b], [o], [r,r,r,r]], L).
% Find a print the first solution.
solve :- solution(X), print_series(X).
% Find all the solutions.
solveall :- solve, fail.
% This finds each solution with stepping.
solvestep(Z) :- Z = next, solution(X), print_series(X).
工作时应该是这样的:
?- consult(linejump).
% linejump compiled 0.00 sec, 3,612 bytes
true.
?- solve.
*******************************************************
[r, r, r, r, o, b, b, b, b]
[r, r, r, o, r, b, b, b, b]
[r, r, r, b, r, o, b, b, b]
[r, r, r, b, r, b, o, b, b]
[r, r, r, b, o, b, r, b, b]
[r, r, o, b, r, b, r, b, b]
[r, o, r, b, r, b, r, b, b]
[r, b, r, o, r, b, r, b, b]
[r, b, r, b, r, o, r, b, b]
[r, b, r, b, r, b, r, o, b]
[r, b, r, b, r, b, r, b, o]
[r, b, r, b, r, b, o, b, r]
[r, b, r, b, o, b, r, b, r]
[r, b, o, b, r, b, r, b, r]
[o, b, r, b, r, b, r, b, r]
[b, o, r, b, r, b, r, b, r]
[b, b, r, o, r, b, r, b, r]
[b, b, r, b, r, o, r, b, r]
[b, b, r, b, r, b, r, o, r]
[b, b, r, b, r, b, o, r, r]
[b, b, r, b, o, b, r, r, r]
[b, b, o, b, r, b, r, r, r]
[b, b, b, o, r, b, r, r, r]
[b, b, b, b, r, o, r, r, r]
[b, b, b, b, o, r, r, r, r]
*******************************************************
true ;
*******************************************************
[r, r, r, r, o, b, b, b, b]
[r, r, r, r, b, o, b, b, b]
[r, r, r, o, b, r, b, b, b]
[r, r, o, r, b, r, b, b, b]
[r, r, b, r, o, r, b, b, b]
[r, r, b, r, b, r, o, b, b]
[r, r, b, r, b, r, b, o, b]
[r, r, b, r, b, o, b, r, b]
[r, r, b, o, b, r, b, r, b]
[r, o, b, r, b, r, b, r, b]
[o, r, b, r, b, r, b, r, b]
[b, r, o, r, b, r, b, r, b]
[b, r, b, r, o, r, b, r, b]
[b, r, b, r, b, r, o, r, b]
[b, r, b, r, b, r, b, r, o]
[b, r, b, r, b, r, b, o, r]
[b, r, b, r, b, o, b, r, r]
[b, r, b, o, b, r, b, r, r]
[b, o, b, r, b, r, b, r, r]
[b, b, o, r, b, r, b, r, r]
[b, b, b, r, o, r, b, r, r]
[b, b, b, r, b, r, o, r, r]
[b, b, b, r, b, o, r, r, r]
[b, b, b, o, b, r, r, r, r]
[b, b, b, b, o, r, r, r, r]
*******************************************************
true .
?-
推荐答案
一个简单明了的 Prolog 代码，力求做到最简单明了，根本不关心效率:
A straightforward Prolog code which tries to be the simplest and clearest, and doesn't care about efficiency at all:
start([r,r,r,r,e,b,b,b,b]). % starting position
% can move from a position P1 to position P2
move(P1,P2):- append(A,[r,e|B],P1), append(A,[e,r|B],P2).
move(P1,P2):- append(A,[e,b|B],P1), append(A,[b,e|B],P2).
move(P1,P2):- append(A,[e,r,b|B],P1), append(A,[b,r,e|B],P2).
move(P1,P2):- append(A,[r,b,e|B],P1), append(A,[e,b,r|B],P2).
solved([b,b,b,b,e,r,r,r,r]). % the target position to be reached
pegs :- start(P), solve(P, [], R),
maplist(writeln, R), nl, nl, fail ; true.
% solve( ?InitialPosition, +PreviousPositionsList, ?ResultingPath)
solve(P, Prev, R):-
solved(P) -> reverse([P|Prev], R) ;
move(P, Q), \+memberchk(Q, Prev), solve(Q, [P|Prev], R).
没什么特别的.在 Ideone 上花费 0.08 秒 来找到两个解决方案，均为 24 步.
Nothing special about it. Takes whole of 0.08 seconds on Ideone to find two solutions, both of 24 moves.
对于 N-pegs 问题，我们只需要相应地修改 start 和 solved 谓词.
For an N-pegs problem, we only need to modify the start and solved predicates accordingly.
感谢 Cary Swoveland，从他的答案我接受了符号(这是解决方案的一半).一个更高效的代码，遵循 mat 的 answer，以 Prolog 特有的自上而下的方式构建结果列表(类似于 difference-lists 技术，参见 tailrecursion-modulo-cons ):
Kudos go to Cary Swoveland from whose answer I took the notation (that's half the solution). A more efficient code, following mat's answer, building the result list in Prolog's characteristic top-down manner (similar to difference-lists technique, cf. tailrecursion-modulo-cons ):
swap([r,e|B],[e,r|B]).
swap([e,b|B],[b,e|B]).
swap([e,r,b|B],[b,r,e|B]).
swap([r,b,e|B],[e,b,r|B]).
move(A,B):- swap(A,B).
move([A|B],[A|C]):- move(B,C).
moves(S,[S]):- solved(S).
moves(S,[S|B]):- move(S,Q), moves(Q,B).
pegs(PS) :- start(P), moves(P, PS), maplist( writeln, PS), nl.
<小时>
一般来说，任何有位置和移动的棋盘游戏都可以被看作是一个位置搜索空间中的搜索问题，位置搜索空间由有效移动定义，即带我们从开始到结束(最终)位置.可以使用各种搜索策略，深度优先，广度优先，迭代深化，最佳优先启发式......这将搜索空间视为一个图，其中节点是位置(板配置)，边是移动；否则我们可以说这是一个 move 关系的传递闭包.
有时move 关系被定义为产生一个新的合法配置(就像这里)；有时更容易定义一般移动关系并检查产生的位置的合法性(如N-皇后问题).在搜索时维护已访问节点列表并检查任何新发现的节点是否是已访问节点之一也是很常见的 - 丢弃该路径，以避免进入循环.
Sometimes the move relation is defined such that it produces a new legal configuration (like here); sometimes it is easier to define a general move relation and check the produced position for legality (like in N-queens problem). It is also common to maintain the visited nodes list while searching, and check any newly discovered node for being one of those already visited - discarding that path, to avoid getting into a loop.
广度优先搜索将显式维护被发现节点的边界，并将其保持为队列，同时扩展一次；深度优先 作为一个堆栈.Best first 搜索将根据一些启发式重新排序该边界.这里，moves/2 是深度优先隐式，因为它依赖于本身是深度优先的 Prolog 搜索.
Breadth first search will explicitly maintain the frontier of the nodes being discovered, and maintain it as a queue while extending it by one move at a time; depth first as a stack. Best first search will reorder this frontier according to some heuristics. Here, moves/2 is depth-first implicitly, because it relies on Prolog search which is itself depth-first.
有时保证搜索空间没有这些循环(即成为 DAG - 有向无环图)，因此没有必要检查唯一性.至于最终节点，有时它是由值定义的(如这里)，有时我们对某些条件感兴趣(例如在国际象棋中).请参阅此答案，了解如何使用懒惰的方式强制执行此唯一性all_dif/1 前置谓词.有了里面定义的谓词，这个问题就变得简单了
Sometimes the search space is guaranteed to not have these cycles (i.e. to be a DAG - directed acyclic graph) so the check for uniqueness is not necessary. As for the final node, sometimes it is defined by value (like here), sometimes we're interested in some condition to hold (like e.g. in chess). See this answer for how to enforce this uniqueness with a lazy all_dif/1 predicate upfront. With the predicates defined in it, this problem becomes simply
pegs(Ps):-
path( move, Ps, [r,r,r,r,e,b,b,b,b], [b,b,b,b,e,r,r,r,r]).
这篇关于尝试解决 Prolog 中的跳钉拼图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
