Search code examples
prologconstraintsconstraint-programmingeclipse-clpclp

3-in-a-row logic puzzle: optimisation for sequence constraints in lists/arrays

In the following puzzle we try and fill the grid with blue and white squares in such a way that:

  • A 3-in-a-row (or column) of the same colour is not allowed.
  • Each row and column has an equal number of blue and white squares.

example_puzzle

If we now represent white with a 0 and blue with a 1, we get:

0 _ _ _ 1 _
_ 0 _ _ _ _
_ _ _ _ _ 0
1 _ _ 0 _ _
_ _ 1 1 _ _
_ 0 _ _ 1 _

And we can pretty quickly verify that

0 1 0 0 1 1 
0 0 1 1 0 1 
1 1 0 1 0 0 
1 1 0 0 1 0 
0 0 1 1 0 1 
1 0 1 0 1 0

is the solution for this example.

As constraints I wrote the following:

constraints(Board,N) :-
    N2 is N // 2,
    ( for(I,1,N), param(Board,N2,N)
    do
      Row is Board[I,1..N],
      Col is Board[1..N,I],
      ic_global:sequence_total(N2,N2,1,2,3,Row),
      ic_global:sequence_total(N2,N2,1,2,3,Col)
    ).

sequence_total/6 ensures that the value 1 should occur exactly N2 times (half the times of N) in the row/col and that every sequence in the specified row/col of 3 elements should contain between 1 and 2 times the value of 1 (so no 3 squares with value 1 can appear next each other).

I get the following results for an 18x18 puzzle instance (*):

Solved in 147 backtracks
Yes (10.39s cpu, solution 1)

It looks like the constraints are doing their job very well before any search is performed, since 'only' 147 backtracks are needed. The running time however seems really long to me, especially in comparison with the amount of backtracks. I'm guessing this is due to all the sequence-checking that has to occur? The fact that changing any of the selection/choice methods in search/6 has barely any impact on the running time seems to confirm that.

If so, are there any other, more efficient, ways to constraint sequences in a list/array to not have N identical elements next to each other and improve running time?

EDIT

After using the decomposed version provided by @jschimpf below, following results are obtained:

Solved in 310 backtracks
Yes (0.22s cpu, solution 1)

The new constraints are not as strong as sequence/6, we do need a bit more backtracks, but our running time went down from 10.39secs to 0.22secs, so the overall result is very desirable.

Sample data:

Puzzle used for this question (solves without backtracks)

problem(p(6,1),[(1,1,0),(1,5,1),(2,2,0),(3,6,0),(4,1,1),(4,4,0),(5,3,1),(5,4,1),(6,2,0),(6,5,1)]).

Puzzle (*) for which I posted my results:

problem(p(18,1),[(1,3,0),(1,9,0),(1,10,0),(1,12,0),(1,14,0),(1,18,1),(2,4,0),(2,7,1),(2,8,1),(3,2,1),(3,6,0),(3,16,0),(3,17,0),(4,2,1),(4,4,1),(4,10,1),(4,13,1),(4,18,1),(5,8,1),(5,10,1),(5,15,0),(5,16,1),(6,12,1),(7,3,0),(7,4,0),(7,6,1),(7,9,0),(7,12,1),(7,17,0),(8,1,1),(8,4,0),(8,8,1),(8,15,1),(8,16,1),(9,7,0),(9,10,0),(9,14,0),(10,2,1),(10,4,1),(10,6,1),(10,13,1),(11,7,0),(11,10,1),(12,1,1),(12,4,1),(12,7,1),(12,15,1),(12,16,1),(13,1,1),(13,6,0),(13,8,1),(13,10,0),(13,16,1),(14,5,1),(14,10,0),(14,13,1),(15,1,1),(15,3,1),(15,12,0),(15,13,1),(15,15,0),(16,2,1),(16,4,0),(16,12,0),(16,18,0),(17,9,0),(17,15,0),(17,18,0),(18,2,1),(18,8,1),(18,11,1),(18,15,1),(18,16,1)]).

Solution

  • It turns out that, in this case, a hand-crafted, decomposed version of the sequence constraint is much more efficient. Use for example

    sequence_1_2([X1,X2,X3|Xs]) :- !,
    S #:: 1..2,
    X1+X2+X3 #= S,
    sequence_1_2([X2,X3|Xs]).
sequence_1_2(_).

    which constrains the sum of any 3-element sub-sequence to 1 or 2, and replace the sequence_total/6 constraints with

        ...,
    sum(Row) #= N2,
    sequence_1_2(Row),

    This brings the solving time down to 0.2 seconds.