CLP(FD)场景下的奶奶生日谜题：可使用Prolog求解该问题吗

是否可以用支持CLP(FD)的Prolog求解该谜题？ #

完全可以，且无需处理分数蛋糕问题，我们可以通过整数约束直接过滤掉会产生非整数的非法解。

谜题约束转换 #

我们可以先把过桥规则转换为整数约束：
假设过某座桥前持有N块蛋糕，过桥后剩余M块：

• 交一半蛋糕给守桥人，意味着N必须是偶数，否则会出现拆分半块蛋糕的不符合常理的情况
• 交一半后剩余N/2块，守桥人返还1块，最终过桥后数量为M = N/2 + 1，转换为整数约束表达式为N #= 2 * (M - 1)
  我们的目标是经过7座桥后剩余2块，求初始携带的蛋糕数量，直接用逆推逻辑实现约束会更简单。

CLP(FD)实现代码 #

% 加载CLP(FD)库
:- use_module(library(clpfd)).

% 规则定义：过K座桥后剩余End块，初始需要携带Start块
cross_bridge(0, Start, Start). % 0座桥时初始值等于最终值
cross_bridge(K, Start, End) :-
    K #> 0,
    Prev #= 2 * (End - 1), % 逆推上一座桥之前的蛋糕数量
    K1 #= K - 1,
    cross_bridge(K1, Start, Prev).

% 求解入口：过7座桥剩余2块，求初始值
solve(Start) :-
    cross_bridge(7, Start, 2),
    label([Start]).

运行结果 #

调用solve(Start)查询，得到唯一解：Start = 2。
验证过程也很简单：初始携带2块蛋糕，每过一座桥交一半即1块，守桥人返还1块，过完桥后还是2块，经过7座桥后刚好剩余2块，全程不需要拆分蛋糕。

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