prolog - ECLiPSe CLP : 組み合わせオカレンス/3 制約の動作が遅い

Question

より大きな問題のサブセットとして、NxN ボード (N² セルを含む) に対して次の 2 つの制約を記述しようとしています。

各行/列には、定義済みのヒントで指定された整数 K が正確に N 回出現します
2x2 ブロック (ボード上のどこでも) に整数 K が 1 回以上出現することはありません

ボード上では、いくつかのセルが事前に入力されており、この SO の質問の制約では無視する必要があります。したがって、整数 2 を使用してこれらのセルを表し、未知のセルをモデル化してバイナリブール値の有限領域を持たせます。

model(Board,N,Hints) :-
    dim(Board,[N,N]),
    ( foreach(Row-Col,Hints), param(Board)
    do
      2 is Board[Row,Col]
    ),
    ( multifor([I,J],1,N), param(Board)
    do
      Cell is Board[I,J],
      ( var(Cell) -> Cell :: 0..1 ; true )
    ).

それぞれコード内の制約:

hint_constraints(Board,N,RowHints,ColHints) :-
    ( for(I,1,N), foreach(RH,RowHints), foreach(CH,ColHints), param(Board,N)
    do
      Row is Board[I,1..N],
      Col is Board[1..N,I],
      ic_global:occurrences(1,Row,RH),           % Here, K=1 and N=RH
      ic_global:occurrences(1,Col,CH)            % Here, K=1 and N=CH
    ).

block_constraints(Board,N) :-
    ( multifor([I,J],1,(N-1)), param(Board)
    do
      Block is Board[I..I+1,J..J+1],
      flatten(Block,BlockFlat),
      Sum #:: [0,1],
      ic_global:occurrences(1,BlockFlat,Sum)     % Here, K=1
    ).

パズルの単純な実行の場合:

solve(BT) :-
    puzzle(N,_,RowHints,ColHints,Hints),
    model(N,RowHints,ColHints,Hints,Board),
    hint_constraints(Board,N,RowHints,ColHints),
    block_constraints(Board,N),
    once search(Board,0,most_constrained,indomain_max,complete,[backtrack(BT)]).

8x8 パズルの場合、最初の解はほぼ瞬時に見つかります。

?- solve(BT).
   [](0, 0, 0, 0, 0, 0, 1, 2)
   [](2, 1, 0, 2, 1, 0, 0, 2)
   [](0, 0, 0, 0, 0, 0, 1, 0)
   [](0, 0, 0, 1, 0, 0, 0, 0)
   [](1, 0, 0, 0, 2, 0, 0, 0)
   [](2, 2, 1, 0, 1, 2, 1, 2)
   [](1, 2, 0, 2, 0, 0, 2, 0)
   [](0, 0, 0, 0, 1, 0, 0, 1)

   BT = 0
   Yes (0.01s cpu)

ただし、20x20 インスタンスの場合、結果が得られずに約 5 分間実行したままにしました。

1 つの制約が他の制約よりも大幅にコストがかかるかどうかを調べるために、両方を別々に実行しました。

block_constraints/2 ではなく、hint_constraints/4 を使用すると、次のようになります。

?- solve(BT).
   [](1, 1, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0)
   [](1, 1, 2, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 2, 0)
   [](2, 1, 1, 1, 2, 1, 1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0)
   [](1, 1, 0, 0, 0, 0, 0, 2, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2)
   [](1, 0, 1, 1, 1, 2, 1, 1, 2, 1, 0, 0, 0, 0, 2, 2, 0, 0, 2, 0)
   [](2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0)
   [](2, 0, 0, 0, 1, 2, 1, 1, 1, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0)
   [](1, 0, 0, 0, 2, 1, 1, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 0)
   [](2, 0, 0, 0, 1, 1, 0, 1, 1, 2, 1, 0, 2, 0, 2, 0, 2, 0, 0, 2)
   [](2, 0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 0, 0, 0, 0, 0, 2, 0, 2, 0)
   [](0, 0, 0, 0, 2, 0, 2, 0, 0, 1, 2, 1, 2, 1, 1, 0, 0, 1, 0, 2)
   [](0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 2, 0, 0)
   [](0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 1, 1, 1, 0, 1, 0, 2, 0, 0)
   [](2, 0, 0, 0, 2, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1)
   [](0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1)
   [](0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 2, 2, 2, 1)
   [](0, 2, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 1, 1, 1)
   [](0, 0, 2, 0, 0, 0, 0, 0, 2, 2, 0, 2, 0, 1, 0, 0, 1, 2, 1, 1)
   [](2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2)
   [](0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 2, 0, 1, 2, 1, 1, 1, 2, 1)

   BT = 0
   Yes (0.04s cpu)

すべての行/列のオカレンスが満たされていることを確認できます。逆に、block_constraints/2 を使用し、hint_constraints/2 を使用しない場合:

?- solve(BT).
   [](0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0)
   [](0, 1, 2, 1, 0, 2, 1, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 2, 0)
   [](2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0)
   [](0, 1, 0, 1, 0, 1, 0, 2, 2, 1, 2, 1, 0, 1, 0, 1, 0, 0, 2, 2)
   [](0, 0, 0, 0, 0, 2, 0, 1, 2, 0, 0, 0, 0, 0, 2, 2, 0, 1, 2, 1)
   [](2, 1, 0, 1, 0, 1, 0, 0, 0, 1, 2, 1, 0, 1, 2, 1, 0, 0, 0, 0)
   [](2, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 1, 0, 1)
   [](0, 1, 0, 1, 2, 1, 0, 0, 0, 2, 1, 0, 1, 0, 2, 1, 0, 2, 0, 0)
   [](2, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 2, 0, 2, 0, 2, 1, 0, 2)
   [](2, 1, 0, 1, 0, 1, 2, 0, 0, 1, 0, 1, 0, 1, 0, 1, 2, 0, 2, 1)
   [](0, 0, 0, 0, 2, 0, 2, 1, 0, 0, 2, 0, 2, 0, 0, 0, 0, 1, 0, 2)
   [](0, 1, 0, 1, 2, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0)
   [](0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2, 1, 0)
   [](2, 1, 0, 1, 2, 2, 0, 0, 0, 2, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0)
   [](0, 0, 2, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0)
   [](0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 1, 2, 1, 0, 1, 2, 2, 2, 0)
   [](0, 2, 0, 0, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 1, 0, 1)
   [](0, 1, 2, 1, 0, 0, 0, 0, 2, 2, 1, 2, 1, 0, 1, 0, 0, 2, 0, 0)
   [](2, 0, 0, 0, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2)
   [](0, 1, 2, 1, 0, 0, 0, 0, 2, 0, 2, 2, 1, 0, 2, 0, 0, 0, 2, 0)

   BT = 0
   Yes (0.01s cpu)

2x2 ブロック制約が正常に保持されていることをもう一度確認できます。残念ながら、両方の制約を一緒に使用すると、プログラムは 5 分以内に終了しないようです。両方の制約が別々に非常に高速に機能するように見えるため、この動作には少し混乱しています。プロセス全体でブロック制約を満たしながら、各行/列の正しいオカレンスが存在することを確認するために、内部で多くのチェックを行う必要があることは理解していますが、5 分以上かかるという事実は、何か他のことが必要であると考えさせました。ブロック制約の記述方法が間違っている可能性があります。

ブロック発生制約の実装を最適化する方法について誰か考えがありますか?

前もって感謝します！

パズルインスタンス

パズル(8, 簡単, [1,2,1,1,1,3,1,2], [2,1,1,1,3,0,3,1], [1-8, 2-1] 、2-4、2-8、5-5、6-1、6-2、6-6、6-8、7-2、7-4、7-7])。

パズル(20,中,[5,2,6,2,7,1,6,3,5,4,5,3,4,2,4,3,5,4,4,5], [5 ,4,3,3,6,3,4,5,2,4,4,4,2,7,1,5,3,6,3,6]、[1-6、1-15、2 -3、2-6、2-8、2-14、2-18、2-19、3-1、3-5、3-11、4-8、4-9、4-11、4-19 、4-20、5-6、5-9、5-15、5-16、5-19、6-1、6-11、6-15、7-1、7-6、7-15、8 -5、8-10、8-15、8-18、9-1、9-10、9-13、9-15、9-17、9-20、10-1、10-7、10-17 , 10-19, 11-5, 11-7, 11-11, 11-13, 11-20, 12-5, 12-18, 13-6, 13-11, 13-18, 14-1, 14 -5、14-6、14-10、15-3、15-12、16-6、16-13、16-17、16-18、16-19、17-2、17-5、17-7 , 17-15, 18-3, 18-9, 18-10, 18-12, 18-18, 19-1, 19-6, 19-20, 20-3, 20-9, 20-11, 20 -12, 20-15, 20-19])。

prolog - ECLiPSe CLP : 組み合わせオカレンス/3 制約の動作が遅い

0 に答える 0

Related

Reference