1

我正在尝试解决这个Pebble Solitaire问题，这是我的代码的一部分：

% Base case
play(List, X) :-
    count_pebbles(List, X).

%%%%%%%%%%%%%%
% JUMP RIGHT %
%%%%%%%%%%%%%%
    % oo-XXXXXXXXX
    play(    [111, 111, 45|Tail], X) :-
        play([45,  45,  111|Tail], X).

    % Xoo-XXXXXXXX
    play(    [A, 111, 111, 45|Tail], X) :-
        play([A, 45,  45,  111|Tail], X).

    % XXoo-XXXXXXX
    play(    [A, B, 111, 111, 45|Tail], X) :-
        play([A, B, 45,  45,  111|Tail], X).

    % XXXoo-XXXXXX
    play(    [A, B, C, 111, 111, 45|Tail], X) :-
        play([A, B, C, 45,  45,  111|Tail], X).

    % XXXXoo-XXXXX
    play(    [A, B, C, D, 111, 111, 45|Tail], X) :-
        play([A, B, C, D, 45,  45,  111|Tail], X).

    % XXXXXoo-XXXX
    play(    [A, B, C, D, E, 111, 111, 45|Tail], X) :-
        play([A, B, C, D, E, 45,  45,  111|Tail], X).

    % XXXXXXoo-XXX
    play(    [A, B, C, D, E, F, 111, 111, 45|Tail], X) :-
        play([A, B, C, D, E, F, 45,  45,  111|Tail], X).

    % XXXXXXXoo-XX
    play(    [A, B, C, D, E, F, G, 111, 111, 45|Tail], X) :-
        play([A, B, C, D, E, F, G, 45,  45,  111|Tail], X).

    % XXXXXXXXoo-X
    play(    [A, B, C, D, E, F, G, H, 111, 111, 45|Tail], X) :-
        play([A, B, C, D, E, F, G, H, 45,  45,  111|Tail], X).

    % XXXXXXXXXoo-
    play(    [A, B, C, D, E, F, G, H, I, 111, 111, 45], X) :-
        play([A, B, C, D, E, F, G, H, I, 45,  45,  111], X).


%%%%%%%%%%%%%
% JUMP LEFT %
%%%%%%%%%%%%%
    % -ooXXXXXXXXX
    play(    [45, 111, 111|Tail]) :-
        play([111, 45, 45|Tail]).

    % X-ooXXXXXXXX
    play(    [A, 45, 111, 111|Tail]) :-
        play([A, 111, 45, 45|Tail]).

    % XX-ooXXXXXXX
    play(    [A, B, 45, 111, 111|Tail]) :-
        play([A, B, 111, 45, 45|Tail]).

    % XXX-ooXXXXXX
    play(    [A, B, C, 45, 111, 111|Tail]) :-
        play([A, B, C, 111, 45, 45|Tail]).

    % XXXX-ooXXXXX
    play(    [A, B, C, D, 45, 111, 111|Tail]) :-
        play([A, B, C, D, 111, 45, 45|Tail]).

    % XXXXX-ooXXXX
    play(    [A, B, C, D, E, 45, 111, 111|Tail]) :-
        play([A, B, C, D, E, 111, 45, 45|Tail]).

    % XXXXXX-ooXXX
    play(    [A, B, C, D, E, F, 45, 111, 111|Tail]) :-
        play([A, B, C, D, E, F, 111, 45, 45|Tail]).

    % XXXXXXX-ooXX
    play(    [A, B, C, D, E, F, G, 45, 111, 111|Tail]) :-
        play([A, B, C, D, E, F, G, 111, 45, 45|Tail]).

    % XXXXXXXX-ooX
    play(    [A, B, C, D, E, F, G, H, 45, 111, 111|Tail]) :-
        play([A, B, C, D, E, F, G, H, 111, 45, 45|Tail]).

    % XXXXXXXXX-oo
    play(    [A, B, C, D, E, F, G, H, I, 45, 111, 111]) :-
        play([A, B, C, D, E, F, G, H, I, 111, 45, 45]).

是的，很丑。

但是，当我调用 时findall( Value, play(Game, Value), Values)，其中 Game 只是 45 和 111 的任意序列（例如 [45, 111, 45, 45, 45, 45, 111, 111, 111, 45, 45, 45]），Values 只是永远与 2 个项目的列表统一（编辑：不正确，它与更多项目统一，请参阅评论）。

据我了解，当我调用 findall/3 时，它会在基本情况谓词中找到一个解决方案（它只计算鹅卵石的数量并将其与 X 统一），然后从其他 20 个游戏谓词中的任何一个中找到一个解决方案，然后就……停下来？

我需要它继续下去，直到找到所有解决方案。为什么它在 2 个解决方案后停止？我怎样才能让它继续？

4

1 回答 1

3

你的程序有几个问题。你找到了一个。还有更多！

1mo 按照惯例，在属于同一谓词的子句之间省略空行。这有助于避免您遇到的此类意外问题。

2do 另一个有用的约定是避免使用 ASCII 码。而是像这样使用字符（长度为一的原子）：

[45,111,45,45,45,45,111,111,111,45,45,45]  % your example

[-,o,-,-,-,-,o,o,o,-,-,-] % using chars

"-o----ooo---" % :- set_prolog_flag(double_quotes, chars).

请注意，该指令set_prolog_flag(double_quotes, chars)仅影响"strings"读取双引号的方式。它仍然会吐出实际字符以进行答案替换：

?- L = "-o--".
L = [-,o,-,-].

要获得紧凑的答案，请使用use_module(library(double_quotes))！（首先将double_quotes.plSWI 下载到与 Prolog 文件相同的目录中，然后说）：

?- use_module(double_quotes).
true.

?- L = "-o--".
L = "-o--".

3tio 这是一个重写：首先将你的谓词play/2分成单个动作。将递归与其他代码混合起来通常很麻烦。想象一下，递归谓词不会终止！无论如何，同时太多了。这是我的看法：

:- set_prolog_flag(double_quotes,chars).

move(Xs0, Xs) :-
   phrase( ( seq(Prefix), localmove ) , Xs0, Xs1),
   phrase(   seq(Prefix),               Xs, Xs1).

localmove, "o--" --> "-oo".
localmove, "-oo" --> "oo-".

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

?- move("-o----ooo---",S).
S = "-o---o--o---" ;
S = "-o----o-oo--" ;
false.

所以现在，我们只有一个动作。接下来，我们想要按顺序进行多次移动。为了确保我们不会进入循环，我将closure0/3在另一个示例中使用定义。

?- S0 = "-o----ooo---", closure0(move, S0,S).
   S0 = "-o----ooo---", S = S0
;  S0 = "-o----ooo---", S = "-o---o--o---"
;  S0 = "-o----ooo---", S = "-o----o-oo--"
;  S0 = "-o----ooo---", S = "-o----oo----"
...

这些是许多中间步骤。会有有限多还是无限多？会有周期吗？我们可以盯着所有的答案，或者让 Prolog 为我们思考：

?- S0 = "-o----ooo---", move(S0,S1), closure0(move, S1,S0).
%                       one move ahead,  more moves,   ^^ and back
false.

这失败了，因此没有循环回到原始状态。我们可以一般地证明这一点吗？对于所有可能的长度？直到N = 9，我如预期的那样失败了：

?- length(S0,9), move(S0,S1), closure0(move,S1,S0).
false.

让我重复一遍：在这里，Prolog 证明了所有可能的 9 孔板都没有循环。当然还有一个更简单的论点：一步移走小石子，另一步移走小石子到右边。但是最后一个查询的重点是：Prolog 确实通过同时考虑所有可能的板证明了这一点！

于 2016-05-07T11:28:19.770 回答