我认为用 CLPFD 建模这个难题可以用 automaton/8 完成。在 Prolog 我会写
escape_zurg(T,S) :-
aggregate(min(T,S), (
solve([5,10,20,25], [], S),
sum_timing(S, T)), min(T,S)).
solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
select(A, L0, L1),
select(B, L1, L2),
append([A, B], R0, R1),
select(C, R1, R2),
solve([C|L2], R2, T).
sum_timing(S, T) :-
aggregate(sum(E), member(E, S), T).
产生这个解决方案
?- escape_zurg(T,S).
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].
编辑
好吧，automaton/8 远远超出我的能力范围......让我们开始更简单：什么可以是 state 的简单表示？在左/右我们有 4 个插槽，可以是空的：所以
escape_clpfd(T, Sf) :-
L0 = [_,_,_,_],
Zs = [0,0,0,0],
L0 ins 5\/10\/20\/25,
all_different(L0),
...
现在，由于问题很简单，我们可以“硬编码”状态变化
...
lmove(L0/Zs, 2/2, L1/R1, T1), rmove(L1/R1, 1/3, L2/R2, T2),
lmove(L2/R2, 3/1, L3/R3, T3), rmove(L3/R3, 2/2, L4/R4, T4),
lmove(L4/R4, 4/0, Zs/ _, T5),
...
第一个lmove/4必须将 2 个元素从左向右移动，完成后，我们将在左侧有 2 个零，在右侧有 2 个零。时间 (T1) 将是max(A,B)，此时 A,B 是不认识的。
rmove/4类似，但将在 T2 中“返回”唯一的元素（隐身），它将从右向左移动。我们正在对进化进行编码，断言每一侧的 0 的数量（似乎不难概括）。
让我们完成：
...
T #= T1 + T2 + T3 + T4 + T5,
Sf = [T1,T2,T3,T4,T5].
现在， rmove/4 更简单，所以让我们编写代码：
rmove(L/R, Lz/Rz, Lu/Ru, M) :-
move_one(R, L, Ru, Lu, M),
count_0s(Ru, Rz),
count_0s(Lu, Lz).
它遵循 move_one/5 的实际工作，然后应用我们在上面硬编码的数字约束：
count_0s(L, Z) :-
maplist(is_0, L, TF),
sum(TF, #=, Z).
is_0(V, C) :- V #= 0 #<==> C.
is_0 /2将空槽条件具体化，即使真值可数。值得测试一下：
?- count_0s([2,1,1],X).
X = 0.
?- count_0s([2,1,C],1).
C = 0.
?- count_0s([2,1,C],2).
false.
在 CLP(FD) 中编码 move_one/5 似乎很困难。这里 Prolog 的不确定性似乎真的很合适......
move_one(L, R, [Z|Lt], [C|Rt], C) :-
select(C, L, Lt), is_0(C, 0),
select(Z, R, Rt), is_0(Z, 1).
select/3 它是一个纯谓词，当需要标记时 Prolog 将回溯......
没有最小化，但在我们得到解决方案后很容易添加。到目前为止，对我来说，一切似乎都是“合乎逻辑的”。但是当然...
?- escape_clpfd(T, S).
false.
所以，这里是龙...
?- spy(lmove),escape_clpfd(T, S).
% Spy point on escape_zurg:lmove/4
* Call: (9) escape_zurg:lmove([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}]/[0, 0, 0, 0], 2/2, _G12658/_G12659, _G12671) ? creep
Call: (10) escape_zurg:move_one([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}], [0, 0, 0, 0], _G12673, _G12674, _G12661) ? sskip
...等等等等
抱歉，如果我有空闲时间调试，将发布解决方案...
编辑有几个错误......这个 lmove/4
lmove(L/R, Lz/Rz, Lu/Ru, max(A, B)) :-
move_one(L, R, Lt, Rt, A),
move_one(Lt, Rt, Lu, Ru, B),
count_0s(Lu, Lz),
count_0s(Ru, Rz).
至少我们开始得到解决方案（从外部添加变量到标签的接口......）
escape_clpfd(T, Sf, L0) :- ...
?- escape_clpfd(T, S, Vs), label(Vs).
T = 85,
S = [max(5, 10), 10, max(10, 20), 20, max(20, 25)],
Vs = [5, 10, 20, 25] ;
T = 95,
S = [max(5, 10), 10, max(10, 25), 25, max(25, 20)],
Vs = [5, 10, 25, 20] ;
...
编辑
上面的代码有效，但速度非常慢：
?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 15,326,054 inferences, 5.466 CPU in 5.485 seconds (100% CPU, 2803917 Lips)
Sf = [max(5, 10), 10, max(20, 25), 5, max(5, 10)],
L0 = [5, 10, 20, 25]
将此更改为 move_one/5：
move_one([L|Ls], [R|Rs], [R|Ls], [L|Rs], L) :-
L #\= 0,
R #= 0.
move_one([L|Ls], [R|Rs], [L|Lu], [R|Ru], E) :-
move_one(Ls, Rs, Lu, Ru, E).
我有更好的表现：
?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 423,394 inferences, 0.156 CPU in 0.160 seconds (97% CPU, 2706901 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
L0 = [5, 10, 20, 25]
然后，添加到 lmove/4
... A #< B, ...
我明白了
% 233,953 inferences, 0.089 CPU in 0.095 seconds (94% CPU, 2621347 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
整体它仍然比我的纯 Prolog 解决方案慢很多......
编辑
其他小的改进：
?- time((escape_clpfd(60, Sf, L0),maplist(#=,L0,[5,10,20,25]))).
% 56,583 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 2901571 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
其中 all_different/1 已替换为
...
chain(L0, #<),
...
另一个改进：将两边都计数为零是没有用的：在 lmove 和 rmove 中删除（任意）一侧，我们得到
% 35,513 inferences, 0.014 CPU in 0.014 seconds (100% CPU, 2629154 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
编辑
只是为了好玩，这里是相同的纯（聚合除外）Prolog 解决方案，使用简单的确定性“提升”变量（礼貌 ' lifter '）：
:- use_module(carlo(snippets/lifter)).
solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
solve([C|select(B, select(A, L0, °), °)],
select(C, append([A, B], R0, °), °),
T).
顺便说一句，它相当快：
?- time(escape_zurg(T,S)).
% 50,285 inferences, 0.065 CPU in 0.065 seconds (100% CPU, 769223 Lips)
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].
（绝对时间不太好，因为我正在运行为调试而编译的 SWI-Prolog）