SWI-Prolog: findall/3 не находит все решения?
Я пытаюсь решить эту проблему пасьянс Pebble, и это часть моего кода:
% 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]), значения только когда-либо объединяются со списком 2 элемента (РЕДАКТИРОВАТЬ: не соответствует действительности, объединяет больше элементов, см. Комментарии).
Из того, что я понимаю, когда я вызываю findall/3, он находит одно решение в предикате базового случая (которое просто подсчитывает количество камешков и объединяет его с X), а затем одно решение из любого из 20 других предикатов воспроизведения, а потом просто... останавливается?
Мне нужно, чтобы оно продолжалось до тех пор, пока не будут найдены все решения. Почему это останавливается после 2 решений? Как я могу заставить это продолжаться?
1 ответ
Есть несколько проблем с вашей программой. Вы нашли один. Есть еще!
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.pl для SWI в ту же директорию, что и ваш файл 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----"
...
Это много промежуточных шагов. Будет ли бесконечно много или бесконечно много? И будут ли циклы? Мы можем смотреть на все ответы или позволить Прологу думать за нас:
?- 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.
Позвольте мне просто повторить это: здесь Пролог доказал, что все возможные доски с 9 лунками не имеют циклов. Конечно, есть более простой аргумент: одно движение удаляет гальку, другое движение перемещает гальку вправо. Но смысл последнего запроса: Пролог доказал это, рассмотрев все возможные доски одновременно!