如何让Prolog永远不会在相同的两个步骤之间来回？

Question

请看以下汉诺塔问题的“解决方案”：

f([],[],_).

f([A|As],[],C) :- f(As,[A],C).
f([A|As],B,[]) :- f(As,B,[A]).

f([],[B|Bs],C) :- f([B],Bs,C).
f(A,[B|Bs],[]) :- f(A,Bs,[B]).

f([],B,[C|Cs]) :- f([C],B,Cs).
f(A,[],[C|Cs]) :- f(A,[C],Cs).

f([A|As],[B|Bs],C) :- A < B, f(As,[A,B|Bs],C).
f([A|As],B,[C|Cs]) :- A < C, f(As,B,[A,C|Cs]).

f([A|As],[B|Bs],C) :- B < A, f([B,A|As],Bs,C).
f(A,[B|Bs],[C|Cs]) :- B < C, f(A,Bs,[B,C|Cs]).

f([A|As],B,[C|Cs]) :- C < A, f([C,A|As],B,Cs).
f(A,[B|Bs],[C|Cs]) :- C < B, f(A,[C,B|Bs],Cs).

但这永远不会结束，因为 Prolog 被卡在杆 A 和 B 之间来回移动磁盘 1 上，无限循环：

[trace]  ?- f([1,2,3],[],[]).
   Call: (10) f([1, 2, 3], [], []) ? creep
   Call: (11) f([2, 3], [1], []) ? creep
   Call: (12) f([3], [1], [2]) ? creep
   Call: (13) 3<1 ? creep
   Fail: (13) 3<1 ? creep
   Redo: (12) f([3], [1], [2]) ? creep
   Call: (13) 3<2 ? creep
   Fail: (13) 3<2 ? creep
   Redo: (12) f([3], [1], [2]) ? creep
   Call: (13) 1<3 ? creep
   Exit: (13) 1<3 ? creep
   Call: (13) f([1, 3], [], [2]) ? creep
   Call: (14) f([3], [1], [2]) ? creep
   Call: (15) 3<1 ? creep
   Fail: (15) 3<1 ? creep
   Redo: (14) f([3], [1], [2]) ? creep
   Call: (15) 3<2 ? creep
   Fail: (15) 3<2 ? creep
   Redo: (14) f([3], [1], [2]) ? creep
   Call: (15) 1<3 ? creep
   Exit: (15) 1<3 ? creep
   Call: (15) f([1, 3], [], [2]) ? creep
   Call: (16) f([3], [1], [2]) ? creep
   Call: (17) 3<1 ? creep
   Fail: (17) 3<1 ? creep
   Redo: (16) f([3], [1], [2]) ? creep
   Call: (17) 3<2 ? creep
   Fail: (17) 3<2 ? creep
   Redo: (16) f([3], [1], [2]) ? creep
   Call: (17) 1<3 ? creep
   Exit: (17) 1<3 ? creep
   Call: (17) f([1, 3], [], [2]) ? creep
   Call: (18) f([3], [1], [2]) ? 
   [...]

我通常知道

cut

在类似情况下使用。但是如果需要或指示的话，您会在哪里进行剪切？

如何使该程序完成，而不必根据回溯跟踪的具体情况重新排列它？因为我认为这将是一个选项，但这当然是一个玩具示例。

Answer 1

根据 /u/brebs ，类似的东西将是我的代码最直接的改编，跟踪并避免过去的状态。这不仅看起来丑陋——如果我敢说的话——完全无法维护。因此，我希望 Prolog Yedi 能够注意到我的困境，并启发我如何正确地做这件事。

f([],[],_,P,P).

f([A|As],[],C,P,P_) :- 
    \+ member([As,[A],C],P), 
    f(As,[A],C,[[As,[A],C]|P],P_).
f([A|As],B,[],P,P_) :- 
    \+ member([As,B,[A]],P), 
    f(As,B,[A],[[As,B,[A]]|P],P_).

f([],[B|Bs],C,P,P_) :- 
    \+ member([[B],Bs,C],P), 
    f([B],Bs,C,[[[B],Bs,C]|P],P_).
f(A,[B|Bs],[],P,P_) :- 
    \+ member([A,Bs,[B]],P), 
    f(A,Bs,[B],[[A,Bs,[B]]|P],P_).

f([],B,[C|Cs],P,P_) :- 
    \+ member([[C],B,Cs],P), 
    f([C],B,Cs,[[[C],B,Cs]|P],P_).
f(A,[],[C|Cs],P,P_) :- 
    \+ member([A,[C],Cs],P), 
    f(A,[C],Cs,[[A,[C],Cs]|P],P_).

f([A|As],[B|Bs],C,P,P_) :- A < B, 
    \+ member([As,[A,B|Bs],C],P), 
    f(As,[A,B|Bs],C,[[As,[A,B|Bs],C]|P],P_).
f([A|As],B,[C|Cs],P,P_) :- A < C, 
    \+ member([As,B,[A,C|Cs]],P), 
    f(As,B,[A,C|Cs],[[As,B,[A,C|Cs]]|P],P_).

f([A|As],[B|Bs],C,P,P_) :- B < A, 
    \+ member([[B,A|As],Bs,C],P), 
    f([B,A|As],Bs,C,[[[B,A|As],Bs,C]|P],P_).
f(A,[B|Bs],[C|Cs],P,P_) :- B < C, 
    \+ member([A,Bs,[B,C|Cs]],P), 
    f(A,Bs,[B,C|Cs],[[A,Bs,[B,C|Cs]]|P],P_).

f([A|As],B,[C|Cs],P,P_) :- C < A, 
    \+ member([[C,A|As],B,Cs],P), 
    f([C,A|As],B,Cs,[[[C,A|As],B,Cs]|P],P_).
f(A,[B|Bs],[C|Cs],P,P_) :- C < B, 
    \+ member([A,[C,B|Bs],Cs],P), 
    f(A,[C,B|Bs],Cs,[[A,[C,B|Bs],Cs]|P],P_).

至少它以解决方案结束。

?- f([1,2,3],[],[],[[[1,2,3],[],[]]],P), reverse(P,P_), write(P_).

[[[1,2,3],[],[]],[[2,3],[1],[]],[[3],[1],[2]],[[1,3],[],[2]],
 [[1,3],[2],[]],[[3],[2],[1]],[[3],[1,2],[]],[[],[1,2],[3]],
 [[1],[2],[3]],[[],[2],[1,3]],[[2],[],[1,3]],[[2],[1],[3]],
 [[],[1],[2,3]],[[1],[],[2,3]],[[],[],[1,2,3]]]

Answer 2

对于初学者来说，包含 clpfd 是值得商榷的（对于这个简单的任务来说也有点过分），所以这里是 Peano 相当于 lurker 的答案：

% Ending state
move(0, _, _, _) --> [].
% "s" for "successor"
move(s(N), P1, P2, P3) -->
    move(N, P1, P3, P2),
    [P1-to-P2],
    move(N, P3, P2, P1).

swi-prolog 中的结果：

?- phrase(move(s(s(s(0))), left, center, right), Moves).
Moves = [left-to-center, left-to-right, center-to-right,
left-to-center, right-to-left, right-to-center, left-to-center].

这减少了不需要的选择点，因为

0

与

s(N)

被第一个参数索引覆盖。

作为皮亚诺，

s(s(s(0)))

是 4。 这是要转换的代码。

-->

是 DCG 表示法，本质上提供了高效且简洁的列表处理。