prolog - ECLiPSe CLP：缓慢的组合出现/3 约束行为

Question

作为一个更大问题的一个子集，我正在尝试为 NxN 板（包含 N² 个单元）编写以下 2 个约束：

每行/列包含由预定义提示给出的整数 K 的 N 次出现
没有 2x2 块（板上的任何地方）包含超过 1 次出现的整数 K

在板上，已经预先填充了几个单元格，对于这个 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 分钟而没有得到任何结果。

为了调查一个约束是否会比另一个更昂贵，我分别运行了它们：

当我们使用 hint_constraints/4 而不是 block_constraints/2 时，我们得到：

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