块世界问题搜索用完堆栈 space
Block world problem search runs out of stack space
我有以下代码：
move(state(on(X, NewX), OldY, Z), state(NewX, on(X, OldY), Z)).
move(state(on(X, NewX), Y, OldZ), state(NewX, Y, on(X, OldZ))).
move(state(OldX, on(Y, NewY), Z), state(on(Y, OldX), NewY, Z)).
move(state(X, on(Y, NewY), OldZ), state(X, NewY, on(Y, OldZ))).
move(state(OldX, Y, on(Z, NewZ)), state(on(Z, OldX), Y, NewZ)).
move(state(X, OldY, on(Z, NewZ)), state(X, on(Z, OldY), NewZ)).
path(X,X,[]).
path(X,Y,[Z|ZS]) :-
move(X,Z),
path(Z,Y,ZS).
其中 move 为我们提供了您可以使用的可能动作，path 应该为我们提供了您必须从 X 到 Y 的路径。
问题是谓词 path 没有按我想要的那样工作，即，如果我键入 path(state(on(c,on(b,on(a,void))), void, void), state(void, void, on(c,on(a,on(b,void)))), X). 我得到错误：本地堆栈不足，但我希望 X 会成为
X=[state(void, void, on(c,on(a,on(b,void)))),
state(void, on(c,void), on(void(a,on(b,void))),
state(on(a,void), on(c,void), on(b,void)),
state(on(b,on(a,void)), on(c,void), void),
state(on(c,on(b,on(a,void))), void, void)].
那我做错了什么？
哦...一个块世界问题！
只是因为你做了两件事：
- 深度优先搜索状态 space。
- 无法测试某个状态是否已被访问。
（另外，你给的解不是可达状态，第二行有一个void位置不对，再加上路径反了）
实际上，您仅在return 上通过状态路径构造路径，此处的第三个参数：path(X,Y,[Z|ZS])。
您必须检查每个状态扩展是否有新状态可能已经在路径上。否则程序可能会永远循环（取决于它如何命中 move/2 移动生成谓词......实际上是一个很好的练习 select a move/2 概率......也许以后）。在下面的代码中，检查由 fail_if_visited/2.
完成
此外，根据上面的深度优先搜索将找到解决方案路径，但很可能不是路径而不是寻求的解决方案。
您确实需要广度优先搜索（或者更确切地说，Iterative Deepening）。由于 Prolog 不允许切换搜索算法（为什么不能？已经 40 多年了），您必须自己滚动一个。
观察：
% ===
% Transform a state into a string
% ===
express(state(A,B,C),S) :-
express_pos(A,SA),
express_pos(B,SB),
express_pos(C,SC),
atomic_list_concat(["[",SA,",",SB,",",SC,"]"],S).
express_pos(on(Top,Rest),S) :-
express_pos(Rest,S2),
atomic_list_concat([Top,S2],S).
express_pos(void,"").
% ===
% Transform a path into a string
% (The path is given in the reverse order; no matter)
% ===
express_path(Path,PathStr) :-
express_path_states(Path,StateStrs),
atomic_list_concat(StateStrs,"<-",PathStr).
express_path_states([S|Ss],[StateStr|SubStateStrs]) :-
express_path_states(Ss,SubStateStrs),
express(S,StateStr).
express_path_states([],[]).
% ===
% For debugging
% ===
debug_proposed(Current,Next,Moved,Path) :-
express(Current,CurrentStr),
express(Next,NextStr),
length(Path,L),
debug(pather,"...Proposed at path length ~d: ~w -> ~w (~q)",[L,CurrentStr,NextStr,Moved]).
debug_accepted(State) :-
express(State,StateStr),
debug(pather,"...Accepted: ~w",[StateStr]).
debug_visited(State) :-
express(State,StateStr),
debug(pather,"...Visited: ~w",[StateStr]).
debug_moved(X) :-
debug(pather,"...Already moved: ~w",[X]).
debug_final(State) :-
express(State,StateStr),
debug(pather,"Final state reached: ~w",[StateStr]).
debug_current(State,Path) :-
express(State,StateStr),
express_path(Path,PathStr),
length(Path,L),
debug(pather,"Now at: ~w with path length ~d and path ~w",[StateStr,L,PathStr]).
debug_path(Path) :-
express_path(Path,PathStr),
debug(pather,"Path: ~w",[PathStr]).
% ===
% Moving blocks between three stacks, also recording the move
% ===
move(state(on(X, A), B, C),
state(A, on(X, B), C),
moved(X,"A->B")).
move(state(on(X, A), B, C),
state(A, B, on(X, C)),
moved(X,"A->C")).
move(state(A, on(X, B), C),
state(on(X, A), B, C),
moved(X,"B->A")).
move(state(A, on(X, B), C),
state(A, B, on(X, C)),
moved(X,"B->C")).
move(state(A, B, on(X, C)),
state(on(X, A), B, C),
moved(X,"C->A")).
move(state(A, B, on(X, C)),
state(A, on(X, B), C),
moved(X,"C->B")).
move(_,_,_,_) :- debug(pather,"No more moves",[]).
% ===
% Finding a path from an Initial State I to a Final State F.
% You have to remember the path taken so far to avoid cycles,
% instead of trying to reach the final state while the path-so-far
% is sitting inaccessible on the stack, from whence it can only be
% be reconstructed on return-fro-recursion.
% ===
fail_if_visited(State,Path) :-
(memberchk(State,Path)
-> (debug_visited(State),fail)
; true).
fail_if_moved(moved(X,_),LastMoved) :-
(LastMoved = moved(X,_)
-> (debug_moved(X),fail)
; true).
path2(F,F,Path,Path,_) :-
debug_final(F).
path2(I,F,PathToI,FullPath,LastMoved) :-
dif(I,F), % I,F are sure different (program will block if it can't be sure)
debug_current(I,PathToI),
move(I,Next,Moved), % backtrackably pattern-match yourself an acceptable next state based on I
ground(Next), % fully ground, btw
debug_proposed(I,Next,Moved,PathToI),
fail_if_moved(Moved,LastMoved), % don't want to move the same thing again
fail_if_visited(Next,PathToI), % maybe already visited?
debug_accepted(Next), % if we are here, not visited
PathToNext = [Next|PathToI],
path2(Next,F,PathToNext,FullPath,Moved). % recurse with path-so-far (in reverse)
% ---
% Top call
% ---
path(I,F,Path) :-
PathToI = [I],
path2(I,F,PathToI,FullPath,[]), % FullPath will "fish" the full path out of the depth of the stack
reverse(FullPath,Path), % don't care about efficiency of reverse/2 at all
debug_path(Path).
% ===
% Test
% ===
:- begin_tests(pather).
test(one, true(Path = [state(void, void, on(c,on(a,on(b,void)))),
state(void, on(c,void), on(void(a,on(b,void)))),
state(on(a,void), on(c,void), on(b,void)),
state(on(b,on(a,void)), on(c,void), void),
state(on(c,on(b,on(a,void))), void, void)]))
:- I = state(on(c,on(b,on(a,void))), void, void),
F = state(void, void, on(c,on(a,on(b,void)))),
path(I,F,Path).
:- end_tests(pather).
rt :- debug(pather),run_tests(pather).
最后我们得到：
% ...Accepted: [c,,ab]
% Now at: [c,,ab] with path length 24 and path [c,,ab]<-[,c,ab]<-[,ac,b]<-[b,ac,]<-[ab,c,]<-[ab,,c]<-[b,a,c]<-[,a,bc]<-[a,,bc]<-[a,b,c]<-[,ab,c]<-[c,ab,]<-[ac,b,]<-[ac,,b]<-[c,a,b]<-[,ca,b]<-[b,ca,]<-[cb,a,]<-[cb,,a]<-[b,c,a]<-[,bc,a]<-[a,bc,]<-[ba,c,]<-[cba,,]
% ...Proposed at path length 24: [c,,ab] -> [,c,ab] (moved(c,"A->B"))
% ...Already moved: c
% ...Proposed at path length 24: [c,,ab] -> [,,cab] (moved(c,"A->C"))
% ...Already moved: c
% ...Proposed at path length 24: [c,,ab] -> [ac,,b] (moved(a,"C->A"))
% ...Visited: [ac,,b]
% ...Proposed at path length 24: [c,,ab] -> [c,a,b] (moved(a,"C->B"))
% ...Visited: [c,a,b]
% ...Proposed at path length 23: [,c,ab] -> [,,cab] (moved(c,"B->C"))
% ...Accepted: [,,cab]
% Final state reached: [,,cab]
% Path: [cba,,]<-[ba,c,]<-[a,bc,]<-[,bc,a]<-[b,c,a]<-[cb,,a]<-[cb,a,]<-[b,ca,]<-[,ca,b]<-[c,a,b]<-[ac,,b]<-[ac,b,]<-[c,ab,]<-[,ab,c]<-[a,b,c]<-[a,,bc]<-[,a,bc]<-[b,a,c]<-[ab,,c]<-[ab,c,]<-[b,ac,]<-[,ac,b]<-[,c,ab]<-[,,cab]
ERROR: /home/homexercises/pather.pl:146:
test one: wrong answer (compared using =)
ERROR: Expected: [state(void,void,on(c,on(a,on(b,void)))),state(void,on(c,void),on(void(a,on(b,void)))),state(on(a,void),on(c,void),on(b,void)),state(on(b,on(a,void)),on(c,void),void),state(on(c,on(b,on(a,void))),void,void)]
ERROR: Got: [state(on(c,on(b,on(a,void))),void,void),state(on(b,on(a,void)),on(c,void),void),state(on(a,void),on(b,on(c,void)),void),state(void,on(b,on(c,void)),on(a,void)),state(on(b,void),on(c,void),on(a,void)),state(on(c,on(b,void)),void,on(a,void)),state(on(c,on(b,void)),on(a,void),void),state(on(b,void),on(c,on(a,void)),void),state(void,on(c,on(a,void)),on(b,void)),state(on(c,void),on(a,void),on(b,void)),state(on(a,on(c,void)),void,on(b,void)),state(on(a,on(c,void)),on(b,void),void),state(on(c,void),on(a,on(b,void)),void),state(void,on(a,on(b,void)),on(c,void)),state(on(a,void),on(b,void),on(c,void)),state(on(a,void),void,on(b,on(c,void))),state(void,on(a,void),on(b,on(c,void))),state(on(b,void),on(a,void),on(c,void)),state(on(a,on(b,void)),void,on(c,void)),state(on(a,on(b,void)),on(c,void),void),state(on(b,void),on(a,on(c,void)),void),state(void,on(a,on(c,void)),on(b,void)),state(void,on(c,void),on(a,on(b,void))),state(void,void,on(c,on(a,on(b,void))))]
done
% 1 test failed
% 0 tests passed
false.
长度为23的路径成功到达最终状态，但根据求解是"too long"。即使使用 fail_if_moved/2.
中表达的启发式 "do not move a block twice"
附录：概率搜索
使用 Randomized Algorithm 收获惊人：
从上面删除 move/3 谓词并将其替换为：
move(From,To,Moved) :-
random_permutation([0,1,2,3,4,5],ONs), % permute order numbers
!, % no backtracking past here!
move_randomly(ONs,From,To,Moved). % try to match a move
move_randomly([ON|___],From,To,Moved) :- move(ON,From,To,Moved).
move_randomly([__|ONs],From,To,Moved) :- move_randomly(ONs,From,To,Moved).
move_randomly([],_,_,_) :- debug(pather,"No more moves",[]).
move(0,state(on(X, A), B, C),
state(A, on(X, B), C),
moved(X,"0: A->B")).
move(1,state(on(X, A), B, C),
state(A, B, on(X, C)),
moved(X,"1: A->C")).
move(2,state(A, on(X, B), C),
state(on(X, A), B, C),
moved(X,"2: B->A")).
move(3,state(A, on(X, B), C),
state(A, B, on(X, C)),
moved(X,"3: B->C")).
move(4,state(A, B, on(X, C)),
state(on(X, A), B, C),
moved(X,"4: C->A")).
move(5,state(A, B, on(X, C)),
state(A, on(X, B), C),
moved(X,"5: C->B")).
显然这不是高效 Prolog 的范例，但谁在乎呢：
仅在 7 次尝试中就找到了长度为 5 的解！
Path: [cba,,]<-[ba,c,]<-[a,c,b]<-[,c,ab]<-[,,cab] (Length 5)
对于第一次测试，无需重写代码。自 1972 年夏天1 以来就没有了。相反，您可以谨慎地重新表述您的查询。
与其要求您的 Prolog 系统需要相当多的独创性，不如要求一个具体的答案，让我们将您的答案表述为一个查询！我试了一下，发现你有一些讨厌的语法错误，然后查询失败了..
但还有更便宜的方法！让我们只限制列表的长度，让 Prolog 填写其余部分。这份清单应该有多长？我们不知道（也就是说，我不知道）。好的，让我们试试任意长度！这也是 Prolog 喜欢的东西。就像：
?- length(X,N), % new
path( state(on(c,on(b,on(a,void))), void, void),
state(void, void, on(c,on(a,on(b,void)))),
X).
X = [ state(on(b,on(a,void)),on(c,void),void),
state(on(a,void),on(c,void),on(b,void)),
state(void,on(c,void),on(a,on(b,void))),
state(void,void,on(c,on(a,on(b,void)))) ],
N = 4
; ...
看到我做了什么吗？我只在前面加了length(X, N)。突然之间，Prolog 的回答 比您预期的要短 ！
现在，这真的是最好的提问方式吗？毕竟，许多答案可能都是简单的循环，将一个方块放在一个地方然后再放回去……真的有循环吗？让我们先问一下：
... --> [] | [_], ... .
?- length(X,N),
path( state(on(c,on(b,on(a,void))), void, void),
state(void, void, on(c,on(a,on(b,void)))),
X),
phrase((...,[E],...,[E],...), X).
X = ...
N = 6,
E = state(void,on(c,void),on(a,on(b,void)))
; ...
哦，是的，有！现在排除这些路径确实有意义。这是一个干净的方法：
alldifferent([]).
alldifferent([X|Xs]) :-
maplist(dif(X), Xs),
alldifferent(Xs).
?- alldifferent(X),
length(X,N),
path( state(on(c,on(b,on(a,void))), void, void),
state(void, void, on(c,on(a,on(b,void)))),
X).
你能用这个公式走多远？目前，我找到了一条长度为 48 ... 55 ... 的路径，它不应该是有限的吗？并且：是否有可能为这种微不足道的问题排除如此长的路径？任何蹒跚学步的孩子都可以保持搜索 space 小...这些都是基本问题，但它们独立于编程问题本身。
或者，从另一个角度来看：X 的解决方案集非常大。那么如果我们要探索这个集合，我们应该从哪里开始呢？成为最佳解决方案意味着什么？上传到 Utube 上获得最多赞成票的那个？所以我们在这里做的完全是不知情的搜索。您需要告知程序您有什么样的偏好。它无法合理地猜测它。好的，一种启发式方法是解决方案的术语大小。 length/2 做到了。
请注意，我不敢碰你干净的代码。是的，我本可以稍微改进它，比如使用 path/4，但改进幅度不大。而是坚持你高度干净的风格，而是做更多的查询！这就是 Prolog 擅长的！
其他改进：使用列表来表示堆栈，这使状态更具吸引力。
1 那是 Prolog discovered/conceived/delivered 的那一年。
我有以下代码：
move(state(on(X, NewX), OldY, Z), state(NewX, on(X, OldY), Z)).
move(state(on(X, NewX), Y, OldZ), state(NewX, Y, on(X, OldZ))).
move(state(OldX, on(Y, NewY), Z), state(on(Y, OldX), NewY, Z)).
move(state(X, on(Y, NewY), OldZ), state(X, NewY, on(Y, OldZ))).
move(state(OldX, Y, on(Z, NewZ)), state(on(Z, OldX), Y, NewZ)).
move(state(X, OldY, on(Z, NewZ)), state(X, on(Z, OldY), NewZ)).
path(X,X,[]).
path(X,Y,[Z|ZS]) :-
move(X,Z),
path(Z,Y,ZS).
其中 move 为我们提供了您可以使用的可能动作，path 应该为我们提供了您必须从 X 到 Y 的路径。
问题是谓词 path 没有按我想要的那样工作，即，如果我键入 path(state(on(c,on(b,on(a,void))), void, void), state(void, void, on(c,on(a,on(b,void)))), X). 我得到错误：本地堆栈不足，但我希望 X 会成为
X=[state(void, void, on(c,on(a,on(b,void)))),
state(void, on(c,void), on(void(a,on(b,void))),
state(on(a,void), on(c,void), on(b,void)),
state(on(b,on(a,void)), on(c,void), void),
state(on(c,on(b,on(a,void))), void, void)].
那我做错了什么？
哦...一个块世界问题！
只是因为你做了两件事：
- 深度优先搜索状态 space。
- 无法测试某个状态是否已被访问。
（另外，你给的解不是可达状态，第二行有一个void位置不对，再加上路径反了）
实际上，您仅在return 上通过状态路径构造路径，此处的第三个参数：path(X,Y,[Z|ZS])。
您必须检查每个状态扩展是否有新状态可能已经在路径上。否则程序可能会永远循环（取决于它如何命中 move/2 移动生成谓词......实际上是一个很好的练习 select a move/2 概率......也许以后）。在下面的代码中，检查由 fail_if_visited/2.
此外，根据上面的深度优先搜索将找到解决方案路径，但很可能不是路径而不是寻求的解决方案。
您确实需要广度优先搜索（或者更确切地说，Iterative Deepening）。由于 Prolog 不允许切换搜索算法（为什么不能？已经 40 多年了），您必须自己滚动一个。
观察：
% ===
% Transform a state into a string
% ===
express(state(A,B,C),S) :-
express_pos(A,SA),
express_pos(B,SB),
express_pos(C,SC),
atomic_list_concat(["[",SA,",",SB,",",SC,"]"],S).
express_pos(on(Top,Rest),S) :-
express_pos(Rest,S2),
atomic_list_concat([Top,S2],S).
express_pos(void,"").
% ===
% Transform a path into a string
% (The path is given in the reverse order; no matter)
% ===
express_path(Path,PathStr) :-
express_path_states(Path,StateStrs),
atomic_list_concat(StateStrs,"<-",PathStr).
express_path_states([S|Ss],[StateStr|SubStateStrs]) :-
express_path_states(Ss,SubStateStrs),
express(S,StateStr).
express_path_states([],[]).
% ===
% For debugging
% ===
debug_proposed(Current,Next,Moved,Path) :-
express(Current,CurrentStr),
express(Next,NextStr),
length(Path,L),
debug(pather,"...Proposed at path length ~d: ~w -> ~w (~q)",[L,CurrentStr,NextStr,Moved]).
debug_accepted(State) :-
express(State,StateStr),
debug(pather,"...Accepted: ~w",[StateStr]).
debug_visited(State) :-
express(State,StateStr),
debug(pather,"...Visited: ~w",[StateStr]).
debug_moved(X) :-
debug(pather,"...Already moved: ~w",[X]).
debug_final(State) :-
express(State,StateStr),
debug(pather,"Final state reached: ~w",[StateStr]).
debug_current(State,Path) :-
express(State,StateStr),
express_path(Path,PathStr),
length(Path,L),
debug(pather,"Now at: ~w with path length ~d and path ~w",[StateStr,L,PathStr]).
debug_path(Path) :-
express_path(Path,PathStr),
debug(pather,"Path: ~w",[PathStr]).
% ===
% Moving blocks between three stacks, also recording the move
% ===
move(state(on(X, A), B, C),
state(A, on(X, B), C),
moved(X,"A->B")).
move(state(on(X, A), B, C),
state(A, B, on(X, C)),
moved(X,"A->C")).
move(state(A, on(X, B), C),
state(on(X, A), B, C),
moved(X,"B->A")).
move(state(A, on(X, B), C),
state(A, B, on(X, C)),
moved(X,"B->C")).
move(state(A, B, on(X, C)),
state(on(X, A), B, C),
moved(X,"C->A")).
move(state(A, B, on(X, C)),
state(A, on(X, B), C),
moved(X,"C->B")).
move(_,_,_,_) :- debug(pather,"No more moves",[]).
% ===
% Finding a path from an Initial State I to a Final State F.
% You have to remember the path taken so far to avoid cycles,
% instead of trying to reach the final state while the path-so-far
% is sitting inaccessible on the stack, from whence it can only be
% be reconstructed on return-fro-recursion.
% ===
fail_if_visited(State,Path) :-
(memberchk(State,Path)
-> (debug_visited(State),fail)
; true).
fail_if_moved(moved(X,_),LastMoved) :-
(LastMoved = moved(X,_)
-> (debug_moved(X),fail)
; true).
path2(F,F,Path,Path,_) :-
debug_final(F).
path2(I,F,PathToI,FullPath,LastMoved) :-
dif(I,F), % I,F are sure different (program will block if it can't be sure)
debug_current(I,PathToI),
move(I,Next,Moved), % backtrackably pattern-match yourself an acceptable next state based on I
ground(Next), % fully ground, btw
debug_proposed(I,Next,Moved,PathToI),
fail_if_moved(Moved,LastMoved), % don't want to move the same thing again
fail_if_visited(Next,PathToI), % maybe already visited?
debug_accepted(Next), % if we are here, not visited
PathToNext = [Next|PathToI],
path2(Next,F,PathToNext,FullPath,Moved). % recurse with path-so-far (in reverse)
% ---
% Top call
% ---
path(I,F,Path) :-
PathToI = [I],
path2(I,F,PathToI,FullPath,[]), % FullPath will "fish" the full path out of the depth of the stack
reverse(FullPath,Path), % don't care about efficiency of reverse/2 at all
debug_path(Path).
% ===
% Test
% ===
:- begin_tests(pather).
test(one, true(Path = [state(void, void, on(c,on(a,on(b,void)))),
state(void, on(c,void), on(void(a,on(b,void)))),
state(on(a,void), on(c,void), on(b,void)),
state(on(b,on(a,void)), on(c,void), void),
state(on(c,on(b,on(a,void))), void, void)]))
:- I = state(on(c,on(b,on(a,void))), void, void),
F = state(void, void, on(c,on(a,on(b,void)))),
path(I,F,Path).
:- end_tests(pather).
rt :- debug(pather),run_tests(pather).
最后我们得到：
% ...Accepted: [c,,ab]
% Now at: [c,,ab] with path length 24 and path [c,,ab]<-[,c,ab]<-[,ac,b]<-[b,ac,]<-[ab,c,]<-[ab,,c]<-[b,a,c]<-[,a,bc]<-[a,,bc]<-[a,b,c]<-[,ab,c]<-[c,ab,]<-[ac,b,]<-[ac,,b]<-[c,a,b]<-[,ca,b]<-[b,ca,]<-[cb,a,]<-[cb,,a]<-[b,c,a]<-[,bc,a]<-[a,bc,]<-[ba,c,]<-[cba,,]
% ...Proposed at path length 24: [c,,ab] -> [,c,ab] (moved(c,"A->B"))
% ...Already moved: c
% ...Proposed at path length 24: [c,,ab] -> [,,cab] (moved(c,"A->C"))
% ...Already moved: c
% ...Proposed at path length 24: [c,,ab] -> [ac,,b] (moved(a,"C->A"))
% ...Visited: [ac,,b]
% ...Proposed at path length 24: [c,,ab] -> [c,a,b] (moved(a,"C->B"))
% ...Visited: [c,a,b]
% ...Proposed at path length 23: [,c,ab] -> [,,cab] (moved(c,"B->C"))
% ...Accepted: [,,cab]
% Final state reached: [,,cab]
% Path: [cba,,]<-[ba,c,]<-[a,bc,]<-[,bc,a]<-[b,c,a]<-[cb,,a]<-[cb,a,]<-[b,ca,]<-[,ca,b]<-[c,a,b]<-[ac,,b]<-[ac,b,]<-[c,ab,]<-[,ab,c]<-[a,b,c]<-[a,,bc]<-[,a,bc]<-[b,a,c]<-[ab,,c]<-[ab,c,]<-[b,ac,]<-[,ac,b]<-[,c,ab]<-[,,cab]
ERROR: /home/homexercises/pather.pl:146:
test one: wrong answer (compared using =)
ERROR: Expected: [state(void,void,on(c,on(a,on(b,void)))),state(void,on(c,void),on(void(a,on(b,void)))),state(on(a,void),on(c,void),on(b,void)),state(on(b,on(a,void)),on(c,void),void),state(on(c,on(b,on(a,void))),void,void)]
ERROR: Got: [state(on(c,on(b,on(a,void))),void,void),state(on(b,on(a,void)),on(c,void),void),state(on(a,void),on(b,on(c,void)),void),state(void,on(b,on(c,void)),on(a,void)),state(on(b,void),on(c,void),on(a,void)),state(on(c,on(b,void)),void,on(a,void)),state(on(c,on(b,void)),on(a,void),void),state(on(b,void),on(c,on(a,void)),void),state(void,on(c,on(a,void)),on(b,void)),state(on(c,void),on(a,void),on(b,void)),state(on(a,on(c,void)),void,on(b,void)),state(on(a,on(c,void)),on(b,void),void),state(on(c,void),on(a,on(b,void)),void),state(void,on(a,on(b,void)),on(c,void)),state(on(a,void),on(b,void),on(c,void)),state(on(a,void),void,on(b,on(c,void))),state(void,on(a,void),on(b,on(c,void))),state(on(b,void),on(a,void),on(c,void)),state(on(a,on(b,void)),void,on(c,void)),state(on(a,on(b,void)),on(c,void),void),state(on(b,void),on(a,on(c,void)),void),state(void,on(a,on(c,void)),on(b,void)),state(void,on(c,void),on(a,on(b,void))),state(void,void,on(c,on(a,on(b,void))))]
done
% 1 test failed
% 0 tests passed
false.
长度为23的路径成功到达最终状态，但根据求解是"too long"。即使使用 fail_if_moved/2.
附录：概率搜索
使用 Randomized Algorithm 收获惊人：
从上面删除 move/3 谓词并将其替换为：
move(From,To,Moved) :-
random_permutation([0,1,2,3,4,5],ONs), % permute order numbers
!, % no backtracking past here!
move_randomly(ONs,From,To,Moved). % try to match a move
move_randomly([ON|___],From,To,Moved) :- move(ON,From,To,Moved).
move_randomly([__|ONs],From,To,Moved) :- move_randomly(ONs,From,To,Moved).
move_randomly([],_,_,_) :- debug(pather,"No more moves",[]).
move(0,state(on(X, A), B, C),
state(A, on(X, B), C),
moved(X,"0: A->B")).
move(1,state(on(X, A), B, C),
state(A, B, on(X, C)),
moved(X,"1: A->C")).
move(2,state(A, on(X, B), C),
state(on(X, A), B, C),
moved(X,"2: B->A")).
move(3,state(A, on(X, B), C),
state(A, B, on(X, C)),
moved(X,"3: B->C")).
move(4,state(A, B, on(X, C)),
state(on(X, A), B, C),
moved(X,"4: C->A")).
move(5,state(A, B, on(X, C)),
state(A, on(X, B), C),
moved(X,"5: C->B")).
显然这不是高效 Prolog 的范例，但谁在乎呢：
仅在 7 次尝试中就找到了长度为 5 的解！
Path: [cba,,]<-[ba,c,]<-[a,c,b]<-[,c,ab]<-[,,cab] (Length 5)
对于第一次测试，无需重写代码。自 1972 年夏天1 以来就没有了。相反，您可以谨慎地重新表述您的查询。
与其要求您的 Prolog 系统需要相当多的独创性，不如要求一个具体的答案，让我们将您的答案表述为一个查询！我试了一下，发现你有一些讨厌的语法错误，然后查询失败了..
但还有更便宜的方法！让我们只限制列表的长度，让 Prolog 填写其余部分。这份清单应该有多长？我们不知道（也就是说，我不知道）。好的，让我们试试任意长度！这也是 Prolog 喜欢的东西。就像：
?- length(X,N), % new
path( state(on(c,on(b,on(a,void))), void, void),
state(void, void, on(c,on(a,on(b,void)))),
X).
X = [ state(on(b,on(a,void)),on(c,void),void),
state(on(a,void),on(c,void),on(b,void)),
state(void,on(c,void),on(a,on(b,void))),
state(void,void,on(c,on(a,on(b,void)))) ],
N = 4
; ...
看到我做了什么吗？我只在前面加了length(X, N)。突然之间，Prolog 的回答 比您预期的要短 ！
现在，这真的是最好的提问方式吗？毕竟，许多答案可能都是简单的循环，将一个方块放在一个地方然后再放回去……真的有循环吗？让我们先问一下：
... --> [] | [_], ... .
?- length(X,N),
path( state(on(c,on(b,on(a,void))), void, void),
state(void, void, on(c,on(a,on(b,void)))),
X),
phrase((...,[E],...,[E],...), X).
X = ...
N = 6,
E = state(void,on(c,void),on(a,on(b,void)))
; ...
哦，是的，有！现在排除这些路径确实有意义。这是一个干净的方法：
alldifferent([]).
alldifferent([X|Xs]) :-
maplist(dif(X), Xs),
alldifferent(Xs).
?- alldifferent(X),
length(X,N),
path( state(on(c,on(b,on(a,void))), void, void),
state(void, void, on(c,on(a,on(b,void)))),
X).
你能用这个公式走多远？目前，我找到了一条长度为 48 ... 55 ... 的路径，它不应该是有限的吗？并且：是否有可能为这种微不足道的问题排除如此长的路径？任何蹒跚学步的孩子都可以保持搜索 space 小...这些都是基本问题，但它们独立于编程问题本身。
或者，从另一个角度来看：X 的解决方案集非常大。那么如果我们要探索这个集合，我们应该从哪里开始呢？成为最佳解决方案意味着什么？上传到 Utube 上获得最多赞成票的那个？所以我们在这里做的完全是不知情的搜索。您需要告知程序您有什么样的偏好。它无法合理地猜测它。好的，一种启发式方法是解决方案的术语大小。 length/2 做到了。
请注意，我不敢碰你干净的代码。是的，我本可以稍微改进它，比如使用 path/4，但改进幅度不大。而是坚持你高度干净的风格，而是做更多的查询！这就是 Prolog 擅长的！
其他改进：使用列表来表示堆栈，这使状态更具吸引力。
1 那是 Prolog discovered/conceived/delivered 的那一年。