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.

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

`','(1,','(1,0))`

, i.e., nested "ands", also called "and-lists". A cleaner representation is for example:`x_y_v(1, 1, 0)`

.`(1, 2, 3) = (X, Y)`

would evaluate to true, I can see how this can produce unexpected results.. Thanks for the tip!`(-)/2`

for representing pairs—not`','/2`

or`(.)/2`

! This convention is used by many library predicates handling pairs, as it combines succinct syntax and efficient storage—with most Prolog systems`foo-bar`

takes (a bit) less memory than`[foo,bar]`

.For triples, follow @mat's advice!