Некоторые хорошие ответы по правилу, но не могу получить их все

Это мои правила, в которых заключается моя проблема:

get_row([H|_],1,H):-!.
get_row([_|T],I,X) :-
    I1 is I-1,
    get_row(T,I1,X).

get_column([],_,[]).
get_column([H|T], I, [R|X]):-
   get_row(H, I, R), 
   get_column(T,I,X).

good_by_coulmns(Solution) :-
      length(Solution, Length),
      forall((between(1, Length, X),
              get_column(Solution, X, Y)),
              all_distinct(Y)).

createRow(Solution, Domain, Row) :- 
      maplist(member, Row, Domain),
      all_distinct(Row), 
      good_by_coulmns(Solution).
      %, write(Solution), nl.

tryToSolve(Domains, Solution) :-
      maplist(createRow(Solution),
              Domains, Solution),
      length(Solution, L), 
      length(Domains, L),
      good_by_coulmns(Solution).

Проблема в том, что последнее правило генерирует около 20 хороших ответов, но после этого оно уходит в бесконечный цикл. В первом правиле есть отладочная запись.

Он пишет такие строки (с постоянно меняющимися числами) при бесконечном цикле:

[[1, 2, 3, 4], [3, 1, 4, 2], [4, 3, 2, 1], [2, 4, 1, 3], _8544, _8550, _8556, _8562]
[[1, 2, 3, 4], [3, 4, 1, 2], _8532, _8538, _8544, _8550, _8556, _8562]

Решение, ждем, это матрица 4х4. в первой строке, если вырезать первые 4 элемента, это хорошее решение.

Количество переменных, начинающихся с _, всегда увеличивается, а первая строка матрицы ([1,2,3,4]) никогда не меняется.

У вас есть идеи, что здесь не так?

Фактический запрос:

tryToSolve([[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]], [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]], [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]], [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]], L).

list infinite-loop matrix prolog failure-slice
person Falcon    schedule 13.11.2017    source источник
comment
@nullpointer: такие тривиальные правки бесполезны, без исправления даже орфографических ошибок.   -  person false    schedule 13.11.2017
comment
Я добавил базовый запрос и добавил правила. Пожалуйста, смотрите выше. Он реализует решение головоломок, на данный момент похожее на базовое судоку.   -  person Falcon    schedule 13.11.2017
comment
clpfd - это то, что вам нужно...   -  person false    schedule 13.11.2017
comment
Я не знаю эту библиотеку, можете ли вы показать мне, как я могу использовать ее здесь?   -  person Falcon    schedule 13.11.2017
comment
Да, но у меня есть наполовину работающее решение, я хочу выяснить, почему оно не работает. Я могу переписать его, используя вышеуказанную библиотеку, но я хочу сначала исправить этот код, если это возможно, а не изучать новую библиотеку, ничего не зная о том, почему эта попытка абсолютно не годится. Можете ли вы помочь мне исправить это? Или предоставить альтернативное решение с упомянутой библиотекой?   -  person Falcon    schedule 13.11.2017
comment
Он появился здесь только после отправки моего комментария, извините за это, я добавил недостающие правила.   -  person Falcon    schedule 13.11.2017
comment
Вы уже используете library(clpfd)! Вот откуда all_distinct/1.   -  person false    schedule 13.11.2017
comment
Частичное использование library(clpfd), что опасно... Если вы используете SWI Prolog, вам, должно быть, пришлось вручную включать библиотеку.   -  person lurker    schedule 13.11.2017
comment
Спасибо, предупредил меня об этом! Я заменю это тогда. Я использую пролог SICStus, я его включил.   -  person Falcon    schedule 13.11.2017

Ответы (1)


arrow_upward
3
arrow_downward

Чтобы определить проблему, я буду использовать failure- срез. В нем я вставляю цели false в вашу программу. Вставив эти цели, я уменьшу количество выводов, которые должна выполнить ваша программа. Если это число по-прежнему бесконечно, то видимая часть содержит ошибку1.

?- D = [1,2,3,4], D4 = [D,D,D,D], tryToSolve([D4,D4,D4,D4], L), false.

good_by_coulmns(Solution) :-
   length(Solution, Length), false,
   forall((between(1, Length, X),get_column(Solution, X, Y)), all_distinct(Y)).

createRow(Solution, Domain, Row) :-
   maplist(member, Row, Domain),
   all_distinct(Row),         % false, % terminates here
   good_by_coulmns(Solution), false.

tryToSolve(Domains, Solution) :-
   maplist(createRow(Solution), Domains, Solution), false,
   length(Solution, L),
   length(Domains, L),
   good_by_coulmns(Solution).

Этот фрагмент уже зацикливается. Поэтому в видимой части должна быть ошибка. Обратите внимание на переменную Solution! Это должен быть список фиксированной длины, чтобы length(Solution, Length) завершилось, ведь Length встречается здесь впервые.

Предложение: поставьте цели length(Domains, L), length(Solution, L) на первое место.

Несколько замечаний по вашей программе: forall/2 очень проблемная конструкция. Избегайте этого любой ценой. Хорошо, что в фрагменте его нет - это сильно усложнило бы диагностику.

Кроме того, попробуйте сначала начать с более короткой задачи — это упрощает наблюдение завершения.

Как я разместил эти false цели? Ну, это было немного интуиции и проб и ошибок. Строго говоря, допустимо любое1 размещение целей false, которое приводит к зацикливанию фрагмента. При рассмотрении всех возможностей, то есть ~2lines срезов отказов, наиболее интересны те, которые минимальны. Дополнительную информацию см. в разделе failure-slice. .

1 На самом деле точные предварительные условия немного сложнее. Грубо говоря, полученный фрагмент должен быть в определенной степени чистым.

person false    schedule 13.11.2017
comment
Благодарю вас! Это хороший трюк отладки, чтобы знать! Теперь кажется, что почти все решения найдены нормально, но теперь у меня возникает ошибка нехватки памяти в самых последних решениях. Я надеюсь, что это исчезнет, ​​если дать ему больше ограничений. - person Falcon; 13.11.2017
comment
Я получаю 576 решений. Как в SICStus, так и в SWI. - person false; 13.11.2017
comment
Может быть, вы можете помочь мне улучшить это: stackoverflow.com/questions/47272417/ - person Falcon; 13.11.2017