如何将递归Prolog代码转为DFS实现求解传教士与食人者问题？

你的递归代码已经是DFS雏形，只需补全关键部分 #

你当前的path/4递归逻辑本质就是深度优先搜索（DFS）——每次选择一个合法移动向下探索，直到抵达目标状态。之所以只输出一个解，核心问题是缺少终止条件，且未触发Prolog的回溯机制来枚举所有可能路径。

第一步：补全递归终止规则 #

给path/4添加终止条件，当当前状态等于目标状态时，输出整理后的移动序列（原代码中Moves是逆序存储的，需要反转）：

% 终止条件：当前状态匹配目标，输出正序的移动步骤
path(Goal, Goal, _, Moves) :-
    reverse(Moves, FinalMoves),
    print_solution(FinalMoves), nl.

% 辅助打印函数，让输出更易读
print_solution([]).
print_solution([Move|Rest]) :-
    write(Move), write(' → '),
    print_solution(Rest).

第二步：修复legal/1的逻辑与参数顺序 #

你当前的legal/1参数顺序混乱，建议统一状态格式为[左岸传教士数, 左岸食人者数, 船的位置]，重新实现合法性判断：

% 合法状态：两岸食人者数量均不超过传教士（或该岸无传教士）
legal([M_left, C_left, _]) :-
    % 左岸合法
    (M_left = 0 ; C_left =< M_left),
    % 右岸合法：总传教士3人，总食人者3人
    M_right is 3 - M_left,
    C_right is 3 - C_left,
    (M_right = 0 ; C_right =< M_right).

第三步：完善move/3规则，覆盖所有合法船运情况 #

move/3需要枚举船在左岸、右岸时的所有合法载人组合（船最多载2人，至少1人）：

% 船在左岸，移动到右岸
move([M1, C1, left], [M2, C2, right], MoveDesc) :-
    % 所有合法载人组合
    member([DeltaM, DeltaC], [[1,0], [2,0], [0,1], [0,2], [1,1]]),
    M2 is M1 - DeltaM,
    C2 is C1 - DeltaC,
    M2 >= 0, C2 >= 0,  % 左岸人数不能为负
    format(atom(MoveDesc), '运~d传~d食到右岸', [DeltaM, DeltaC]).

% 船在右岸，移动到左岸
move([M1, C1, right], [M2, C2, left], MoveDesc) :-
    member([DeltaM, DeltaC], [[1,0], [2,0], [0,1], [0,2], [1,1]]),
    M2 is M1 + DeltaM,
    C2 is C1 + DeltaC,
    M2 =< 3, C2 =< 3,  % 右岸人数不能超过总数
    format(atom(MoveDesc), '运~d传~d食到左岸', [DeltaM, DeltaC]).

第四步：编写主查询触发全解枚举 #

通过fail强制Prolog回溯，遍历所有可能的DFS路径：

% 主查询：生成所有合法解
solve_all :-
    path([3,3,left], [0,0,right], [[3,3,left]], []),
    fail.  % 找到一个解后继续回溯，直到所有路径都被尝试
solve_all.  % 所有解枚举完成后成功返回

原代码只出一个解的原因 #

1. 无终止条件：递归无法正确停止，仅偶然返回一个解
2. 未触发回溯：Prolog默认找到第一个解就停止，需用fail强制继续探索
3. 合法性判断错误：参数顺序混乱导致部分合法状态被误判

测试运行 #

调用solve_all.后，Prolog会输出所有合法的移动序列，例如其中一组解：

运1传1食到右岸 → 运1传到左岸 → 运2食到右岸 → 运1食到左岸 → 运2传到右岸 → 运1传1食到左岸 → 运2传到右岸 → 运1食到左岸 → 运2食到右岸

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