Prolog無限ループ

Question

私のコードは以下の通りですが、このコードは数独解決のためのコードですが、行と列のdiv2チェックの最初の実行はrawがすべて異なる場合、div2の2回目の実行を転置した後列はすべて異なっています。

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

そのない「無限ループ」、本当に長い1で最初に実行した後に停止すべきで無限ループに自己それを繰り返すん。

div2(P)が提案された解決策を見つけるとしたら、div2(X)は解決策ではないとします。 div2(P) &は、最後の行にラベルを付けるためのすべての方法を使い果たすまで、最後の行の新しいラベル付けを使用して別のソリューションを生成します。少なくとも最後の行にラベルを付けるまですべてを使い果たしてから、最後の行のすべての可能性を再度実行する。 9行すべてをロールアウトすると、多くの組み合わせがありますが、そのほとんどは非常によく似ています。

Answer 2

@ Scottの答えは正しいです、あなたのプログラムは実際にすべての解決策を見つけ出します。しかし、私たちが待つのは長すぎるようです。

代わりに、label/1の目標を削除してください。これは、これらのソリューションを列挙するソースであり、最後に追加します。

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

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

有限ドメインによる制約プログラミングでは、実際の列挙（ラベル付け）を後の時点まで遅らせることが考えられます。このように、ラベル付けは既存の制約のすべてを考慮に入れることができる。このアプローチに従うことを確実にする最も簡単な方法は、述語を2つの部分に分割することです。実際のコア関係（latin_/2）と完全な関係（latin/1）。しばしば、コア関係の終了を観察することは可能であるが、これは完全な関係にとって非常にコストがかかる。