如何避免Prolog汉诺塔实现陷入无限往复的回溯循环？

原实现代码 #

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).

问题描述 #

上述代码无法终止，会陷入无限循环——程序会反复将最小的圆盘（1）在A杆和B杆之间来回移动。回溯轨迹如下：

[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]) ? 
   [...]

解决方案 #

1. 使用cut操作终止回溯 #

原代码的问题在于，处理空杆的移动时，Prolog会回溯尝试其他规则，导致循环。我们可以在所有处理空杆的确定性移动规则末尾添加cut（!）——因为当某根杆为空时，合法的移动方式是唯一的，无需回溯：

修改后的代码如下：

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).

cut的作用是阻止Prolog回溯到当前子句之后的其他子句，避免无效的移动尝试，从而打破循环。

2. 不依赖回溯轨迹的通用修复方法 #

要从根本上避免循环，需要确保递归有明确的终止条件和单调递减的规模度量，以下是两种可行方案：

方案一：基于汉诺塔标准递归逻辑重写

汉诺塔的核心逻辑是分三步执行，天然保证递归规模递减：

1. 将n-1个圆盘从源杆移到辅助杆
2. 将第n个圆盘从源杆移到目标杆
3. 将n-1个圆盘从辅助杆移到目标杆

重写后的代码如下：

% 终止条件：没有圆盘需要移动
hanoi([], _, _, []).
% 递归步骤：完成三步移动逻辑
hanoi([N|Ns], A, B, C, [move(N,A,C)|Moves]) :-
    hanoi(Ns, A, C, B, Moves1),
    hanoi(Ns, B, A, C, Moves2),
    append(Moves1, Moves2, Moves).

调用示例：hanoi([1,2,3], a, b, c, Moves). 会直接生成所有合法移动步骤，不会陷入循环。

方案二：添加规模参数跟踪递归深度

给原谓词增加一个参数，跟踪剩余需要移动的圆盘总数，强制每次递归调用时该数值严格减小：

% 终止条件：所有圆盘已按降序排列在目标杆
f([],[], Target) :- is_sorted_desc(Target).
f([], Source, Target) :- is_sorted_desc(Target), length(Source, 0).

% 带规模参数的递归谓词
f(Source, Aux, Target, N) :-
    N > 0,
    % 合法移动逻辑（此处可复用原代码的移动规则）
    N1 is N - 1,
    f(NewSource, NewAux, NewTarget, N1).

% 辅助谓词：判断列表是否降序排列
is_sorted_desc([]).
is_sorted_desc([_]).
is_sorted_desc([X,Y|Rest]) :- X > Y, is_sorted_desc([Y|Rest]).

这种方式通过强制规模参数递减，确保递归最终会触发终止条件。

内容的提问来源于stack exchange，提问作者Raffael