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

Question

我想使用 Prolog解决Dan Finkel 的“巨型猫军队之谜”。

基本上，您从 开始[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当你到达这里时，大概会绑定一些值，但L不受约束。L如果Ls是正确形式的非空列表，则将被绑定，并且您执行了目标add5(Ls, L)。但是你并没有执行这个目标。您正在一个列表中存储一个术语。然后，在L完全未绑定的情况下，期望将其绑定到列表的某些部分代码将引发此错误。大概那个sort/2电话是 inside all_different/1。

编辑：这里发布了一些令人惊讶的复杂或低效的解决方案。我认为 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 秒。

编辑：进一步缩减并使其速度提高 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 秒。