list - 关于建立一个列表直到它满足条件

Question

我想解决"the giant cat army riddle"丹芬克尔使用 Prolog。
基本上你从 [0] 开始，然后使用以下三种操作之一构建此列表:添加 5 , 添加 7 ，或采取sqrt .当您设法建立一个列表时，您就成功完成了游戏 2 , 10和 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 .

Answer 1

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

这不符合您的要求。它描述了 add5(Ls, L) 形式的列表元素。 .大概是 Ls当你到达这里时，一定会有一些值(value)，但是 L不受约束。 L如果 Ls 将成为约束是正确形式的非空列表，而您 执行目标 add5(Ls, L) .但是你没有执行这个目标。您将一个术语存储在列表中。然后，使用 L完全未绑定(bind)，期望它绑定(bind)到列表的代码的某些部分将抛出此错误。大概是 sort/2通话在 all_different/1 内.
编辑:这里发布了一些令人惊讶的复杂或低效的解决方案。我认为 DCG 和 CLP 在这里都过大了。所以这里有一个相对简单和快速的。为了执行正确的 2/10/14 顺序，这使用了一个 state 参数来跟踪我们以正确的顺序看到了哪些:

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 秒。
编辑:进一步缩减，速度提高了 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 秒。