Now, we are able to

solve a basic problem

The 8 queens puzzle

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal.

Wikipedia

A first idea is to indicate by a Boolean variable if a cell is occupied by a queen or not.

But we wouldn’t be able to use our constraints.

Also, it is very MILP-like or SAT-like.

A more CP way to model it

A variable per column.

Each domain encodes the row where the queen is set.

Four groups of inequality constraints are posed:

1. no two queens share the same row
2. no two queens share the same column (➡️ handled by the model 🤘)
3. no two queens share the same upward diagonal
4. no two queens share the same downward diagonal

>>🥛<<

6 Queens puzzle in Python

import model as m

n = 8
vs = {}
for i in range(1, n + 1):
    vs["x" + str(i)] = {k for k in range(1, n + 1)}

cs = []
for i in range(1, n):
    for j in range(i + 1, n + 1):
        cs.append(m.NotEqual("x" + str(i), "x" + str(j)))
        cs.append(m.NotEqual("x" + str(i), "x" + str(j), c=(j - i)))
        cs.append(m.NotEqual("x" + str(i), "x" + str(j), c=-(j - i)))

# mirror symm. breaking
vs["cst"] = {int(n / 2) + 1}
cs.append(m.LessThan("x1", "cst"))

# search for all solutions
sols = []
m.dfs(vs, cs, sols, nos=0)
print(len(sols), "solution(s) found")
print(sols)

46 solutions

46 solution(s) found
[[1, 5, 8, 6, 3, 7, 2, 4, 5], ..., [4, 8, 5, 3, 1, 7, 2, 6, 5]]

There are 92 solutions without the (simple) symmetry breaking constraint, 46 otherwise.

We did it 🍾

We build a minimalist CP solver :

• based on integer variables,
• using two different types of constraints,
  • each equipped with a filtering algorithm,
• exploring the search space in DFS way.

And we were able to enumerate solutions
on a puzzle !