ECLiPSe CLP : slow combined occurrence/3 constraint behaviour

Question

As a subset of a larger problem, I'm trying to write the 2 following constraints for an NxN board (containing N² cells):

• Each row/col contains exactly N occurrences of integer K given by pre-defined hints
• No 2x2 block (anywhere on the board) contains more than 1 occurrence of integer K

On the board, several cells will already be filled in on beforehand and should be ignored for the constraints in this SO question, therefore we use integer 2 to represent these cells and model the unknown cells to have a finite domain of binary boolean values:

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 )
    ).

The constraints in code respectively:

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
    ).

For a simple execution of a puzzle:

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)]).

For the 8x8 puzzle, the first solution is found almost instantly:

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

for the 20x20 instance however, I have left it running for around 5 minutes without getting any result.

To investigate whether one constraint would be significantly more costly than the other, I ran both of them separately:

When we use hint_constraints/4, but not block_constraints/2, we get:

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

and can verify that all row/col occurrences are satisfied. The other way around, when we use block_constraints/2, but not 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)

we can once more verify that the 2x2 block constraint successfully holds. Unfortunately, when using both constraints together the program seems not to finish anywhere within 5 minutes. I'm a bit confused by this behaviour since both constraints separately appear to work very fast. Though I understand that a lot of checks will have to occur internally to make sure the correct occurrences for each row/col are present while still satisfying the block constraint throughout the process, the fact that it takes over 5 minutes made me think something else must be wrong with the way I have written the block constraint.

Does anyone have an idea on how to optimise my implementation of the block occurrence constraint?

Thanks in advance!

Puzzle instances

puzzle(8, easy, [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]).

puzzle(20,medium,[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]).