Пролог бесконечной петли

Question

мой код следующий, этот код является кодом для решения Sudoku, но только для строки и столбца первый запуск div2 проверяет, все ли исходные все разные, после переноса второго прогона div2 следует проверить, столбец все разные.

:- use_module(library(clpfd)). 

len(P):- 
    div2(P), 
    write("\n 1P2: "), 
    write(P), 
    transpose(P,X), 
    div2(X), 
    write("\n 1X: "), 
    write(X). 

div2([H|T]) :- 
    H ins 1..9, 
    all_distinct(H), 
    label(H), 
    div2(T). 
div2([]). 

Почему он застрял в бесконечной петле? при тестировании в этом примере это не повторять его сам в петлю бесконечности, где он должен остановиться после первого запуска с X.

 len([ 
      [_,_,_,_,_,4,3,_,7], 
      [7,6,_,1,5,_,_,_,9], 
      [_,5,_,_,_,_,_,_,_], 
      [6,_,5,_,_,8,7,_,_], 
      [9,_,_,_,_,_,_,_,4], 
      [_,_,3,2,_,_,1,_,5], 
      [_,_,_,_,_,_,_,6,_], 
      [5,_,_,_,3,1,_,2,8], 
      [1,_,9,4,_,_,_,_,_]]). 

Answer 1

Сво не «петли бесконечности», просто очень длинный.

Предположим, что div2(P) находит предлагаемое решение, которое определяет div2(X), не является решением проблемы. div2(P) будет откатываться & создать другое решение, предложив новую маркировку для последней строки только, по крайней мере до тех пор, пока она не исчерпала все способы маркировки последней строки, а затем получите новую маркировку для второго-последнего- строка, затем пробежать все возможности для последней строки снова. Сверните это через все 9 строк, и у вас будет много комбинаций, большинство из которых выглядят ОЧЕНЬ похожими.

Answer 2

@ Ответ Скотта правильный, ваша программа действительно находит все решения. Но нам кажется слишком долго ждать.

Вместо этого снимите цель label/1, которая является источником перечисления этих решений и добавьте ее в конце!

latin_(P,Vs) :- 
    div2(P), 
    transpose(P,X), 
    div2(X), 
    append(P,Vs). 

latin(P) :- 
    latin_(P, Vs), 
    labeling([], Vs). 

Идея программирования ограничений с конечными доменами заключается в том, чтобы задержать фактическое перечисление (маркировку) на более позднюю точку. Таким образом, маркировка может принимать во внимание все существующие ограничения. Самый простой способ убедиться, что вы следуете этому подходу, состоит в том, чтобы разбить предикат на две части. Фактическое отношение керна (latin_/2) и полное соотношение (latin/1). Часто можно наблюдать за прекращением отношения основных отношений, в то время как это было бы очень дорогостоящим для полного отношения.