SWI-Prolog: findall/3 not finding all solutions?

Question

I'm trying to solve this Pebble Solitaire problem, and this is part of my code:

% 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]).

Yeah, it's ugly.

However, when I call findall( Value, play(Game, Value), Values), where Game is just any sequence of 45 and 111 (for example [45, 111, 45, 45, 45, 45, 111, 111, 111, 45, 45, 45]), Values is only ever unified with a list of 2 items (EDIT: Not true, it unifies with more items, see comments).

From what I understand, when I call findall/3, it finds one solution in the base case predicate (which just counts the amount of pebbles and unifies it with X), and then one solution from any one of the 20 other play predicates, and then just... stops?

I need it to keep going until all solutions have been found. Why does it stop after 2 solutions? How can I make it continue?

Just realized it doesn't always unify with 2 items, it sometimes finds more. — Mossmyr, May 02 '16 at 14:52
I found the error: All the "JUMP RIGHT" predicates are play/2, all of the "JUMP LEFT" predicates are play/1 <.<" — Mossmyr, May 02 '16 at 15:00

false · Answer 1 · 2022-08-19T11:04:04.083

There are several issues with your program. You found one. There are more!

1mo As a convention, omit empty lines between clauses that belong to the same predicate. This helps avoiding such accidental problems you had.

2do Another useful convention is to avoid using ASCII-codes. Instead use chars (atoms of length one) like so:

[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).

Note that the directive set_prolog_flag(double_quotes, chars) only influences the way double quoted "strings" are read. It still spews out the actual characters for answer substitutions:

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

To get also compact answers use use_module(library(double_quotes))! (To start with just download double_quotes.pl for SWI into the same directory as your Prolog file and say):

?- use_module(double_quotes).
   true.
?- L = "-o--".
   L = "-o--".

3tio Here is a rewrite: First split your predicate play/2 into single moves. Mixing recursion with other code is often quite cumbersome. Imagine, the recursive predicate would not terminate! Anyway, too much at the same time. Here is my take on it:

:- 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.

So now, we have only a single move. Next, we want multiple moves in sequence. To be sure that we are not going into cycles, I will use closure0/3 defined in another example.

?- 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----"
;  ... .

These are many intermediary steps. Will there be finitely many or infinitely many? And will there be cycles? We can stare at all the answers, or let Prolog do the thinking for us:

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

This fails, thus there are no cycles back to the original state. Can we prove this in general? For all possible lengths? Up to N = 9, I got failures as expected:

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

Let me just repeat this: Here, Prolog proved that all possible boards with 9 holes do not have cycles. Of course there is a simpler argument: One move removes a pebble, the other move moves pebbles to the right. But the point of the last query is: Prolog did prove that by considering all possible boards at once!

Beautifly done. 1mo) True. 2do) True, but the predicates I use for user input when the program is run outputs ASCII-codes. Converting them back to chars seems reduntant. 3tio) The code here has some syntax I'm not familiar with, I'll have to look into it. Running your first code-snippet in SWI-Prolog 6.6.4 gives me "ERROR: Out of global stack" — Mossmyr, May 08 '16 at 12:14
Yes. I copied the code above `move("-o----ooo---",S).` into a file "test.pl", ran `$ prolog test.pl` and it compiled, then called `move("-o----ooo---",S).`. — Mossmyr, May 08 '16 at 12:31
BTW: Consider to change the interface of those programs. Most probably they all use get_code or even get0 in place of get_char etc. — false, May 08 '16 at 12:41
You don't use get_char in that code snippet. What do you mean exactly? — Mossmyr, May 08 '16 at 13:30
@Mossmyr: You wrote "but the predicates I use for user input when ... outputs ASCII-codes". Well, that part needs to be reconsidered. — false, May 08 '16 at 17:03

SWI-Prolog: findall/3 not finding all solutions?

1 Answers1