关于构建列表直至满足条件

我想解决《巨猫军团之谜》 https://youtu.be/YeMVoJKn1Tg由 Dan Finkel 使用 Prolog 编写。

基本上你从[0]，然后使用以下三个操作之一构建此列表：添加5，添加7，或采取sqrt。当您成功建立一个列表后，您就成功完成了游戏2,10 and 14按该顺序出现在列表中，并且它们之间可以有其他数字。

规则还要求所有元素都是不同的，它们都是<=60和 都只是整数。 例如，从[0]，你可以申请(add5, add7, add5)，这会导致[0, 5, 12, 17]，但由于它没有按顺序排列 2,10,14，因此不能满足游戏。

我想我已经成功地写出了所需的事实，但我不知道如何实际构建列表。我认为使用dcg是一个不错的选择，但我不知道如何。

这是我的代码：

:- use_module(library(lists)).
:- use_module(library(clpz)).
:- use_module(library(dcgs)).

% integer sqrt
isqrt(X, Y) :- Y #>= 0, X #= Y*Y.

% makes sure X occurs before Y and Y occurs before Z
before(X, Y, Z) --> ..., [X], ..., [Y], ..., [Z], ... .
... --> [].
... --> [_], ... .

% in reverse, since the operations are in reverse too.
order(Ls) :- phrase(before(14,10,2), Ls).

% rule for all the elements to be less than 60.
lt60_(X) :- X #=< 60.
lt60(Ls) :- maplist(lt60_, Ls).

% available operations
add5([L0|Rs], L) :- X #= L0+5, L = [X, L0|Rs].  
add7([L0|Rs], L) :- X #= L0+7, L = [X, L0|Rs].
root([L0|Rs], L) :- isqrt(L0, X), L = [X, L0|Rs].

% base case, the game stops when Ls satisfies all the conditions.
step(Ls) --> { all_different(Ls), order(Ls), lt60(Ls) }.

% building the list
step(Ls) --> [add5(Ls, L)], step(L).
step(Ls) --> [add7(Ls, L)], step(L).
step(Ls) --> [root(Ls, L)], step(L).

该代码发出以下错误，但我没有尝试跟踪它或任何其他内容，因为我确信我错误地使用了 DCG：

?- phrase(step(L), X).
caught: error(type_error(list,_65),sort/2)

我正在使用 Scryer-Prolog，但我认为所有模块都可以在swipl也喜欢clpfd代替clpz.

step(Ls) --> [add5(Ls, L)], step(L).

这不会做你想要的。它描述了表单的列表元素add5(Ls, L)。想必Ls当你到达这里时必然会产生一些价值，但是L没有绑定。L如果Ls是一个正确形式的非空列表，并且您executed目标add5(Ls, L)。但你并没有执行这个目标。您正在将一个术语存储在列表中。然后，与L完全未绑定，期望将其绑定到列表的代码的某些部分将抛出此错误。大概是这样sort/2电话在里面all_different/1.

Edit:这里发布了一些令人惊讶的复杂或低效的解决方案。我认为 DCG 和 CLP 在这里都太过分了。所以这是一个相对简单且快速的方法。为了执行正确的 2/10/14 顺序，它使用状态参数来跟踪我们以正确的顺序看到了哪些：

puzzle(Solution) :-
    run([0], seen_nothing, ReverseSolution),
    reverse(ReverseSolution, Solution).
    
run(FinalList, seen_14, FinalList).
run([Head | Tail], State, Solution) :-
    dif(State, seen_14),
    step(Head, Next),
    \+ member(Next, Tail),
    state_next(State, Next, NewState),
    run([Next, Head | Tail], NewState, Solution).
    
step(Number, Next) :-
    (   Next is Number + 5
    ;   Next is Number + 7
    ;   nth_integer_root_and_remainder(2, Number, Next, 0) ),
    Next =< 60,
    dif(Next, Number).  % not strictly necessary, added by request

    
state_next(State, Next, NewState) :-
    (   State = seen_nothing,
        Next = 2
    ->  NewState = seen_2
    ;   State = seen_2,
        Next = 10
    ->  NewState = seen_10
    ;   State = seen_10,
        Next = 14
    ->  NewState = seen_14
    ;   NewState = State ).

SWI-Prolog 上的计时：

?- time(puzzle(Solution)), writeln(Solution).
% 13,660,415 inferences, 0.628 CPU in 0.629 seconds (100% CPU, 21735435 Lips)
[0,5,12,17,22,29,36,6,11,16,4,2,9,3,10,15,20,25,30,35,42,49,7,14]
Solution = [0, 5, 12, 17, 22, 29, 36, 6, 11|...] .

重复的member确保不重复的调用占据了大部分执行时间。使用“已访问”表（未显示）可将时间缩短至约 0.25 秒。

Edit:进一步削减一点，速度提高 100 倍：

prev_next(X, Y) :-
    between(0, 60, X),
    (   Y is X + 5
    ;   Y is X + 7
    ;   X > 0,
        nth_integer_root_and_remainder(2, X, Y, 0) ),
    Y =< 60.

moves(Xs) :-
    moves([0], ReversedMoves),
    reverse(ReversedMoves, Xs).
    
moves([14 | Moves], [14 | Moves]) :-
    member(10, Moves).
moves([Prev | Moves], FinalMoves) :-
    Prev \= 14,
    prev_next(Prev, Next),
    (   Next = 10
    ->  member(2, Moves)
    ;   true ),
    \+ member(Next, Moves),
    moves([Next, Prev | Moves], FinalMoves).

?- time(moves(Solution)), writeln(Solution).
% 53,207 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 8260575 Lips)
[0,5,12,17,22,29,36,6,11,16,4,2,9,3,10,15,20,25,30,35,42,49,7,14]
Solution = [0, 5, 12, 17, 22, 29, 36, 6, 11|...] .

移动表可以预先计算（枚举所有解决方案）prev_next/2，在动态谓词中断言它们，并调用它）以获得另外一两毫秒的时间。使用 CLP(FD) 而不是“直接”算术会使 SWI-Prolog 上的速度显着变慢。尤其，Y in 0..60, X #= Y * Y而不是nth_integer_root_and_remainder/4目标将此时间延长至约 0.027 秒。