Queen or Not-Queen, That’s The Question

It's time to have fun with optimization again by solving another LinkedIn puzzles. This time it is the "Queen" puzzle turn.

Table of Contents

What is queen puzzle?

Like most LinkedIn puzzles, it is a board game. You are provided with a square board of size $n \times n$ . Cells are colored. The rules are easy:

You need to place one and only one queen in each colored region,
Each row can contain one and only one queen,
Each column can contain one and only one queen,
No two queens can be placed next to each other; Not even diagonally.

Here is an example puzzle:

How to solve it using Optimization?

Deciding the decision variables

We have to first decide on the decision variables. If you have read through the other posts for the other LinkedIn puzzles, you must be familiar now what you should do at this point.

The puzzle is asking us to choose which cell there should be a queen on it given certain constraints. So, it rather seems that for each cell we have to decide "queen" or "not-queen", that's the question. In math and optimization problem, that translates to a boolean variable. True means we have a queen in that cell and if False, we do not have any queen.

Let's call our decision variable:

$q_{i,j} \in \left \{ 0, 1 \right \}$

where essentially $i$ and $j$ refer to the row and column of the cell and $1$ (True) means there is a queen in that cell and $0$ (False) means there is no queen.

That's it. We already decided on our decision problem.

One and only one queen per row

One of the constraint is that there is one and only one queen per row. We have already learned how to enforce such constraint using OR-Tools. All we need to do is:

$\sum{q_{i,\cdot} = 1$

One and only one queen per column

This is very similar to the previous constraint, except that now we are enforcing the same constraint over the columns rather than over the rows:

$\sum{q_{\cdot,j} = 1$

No two queens next two eachother; Not even diagonally

In this case, we have sort of the similar situation as the other previous two constraints, with some tiny changes:

The way that the variables are selected is different. Instead of row and column we need to enforce this on variables that are around another variable.
The sum of the decision variables around another variable must add up to 0 (i.e. no queen), rather than 1,
This constraint should only apply if the cell in the middle (the one that we are looking for its neighboring cells) must have a queen. If that cell does not have a queen, then this constraint does not apply.

So, let's define $\mathscr{N}(i, j)$ to be the cells that are around a central cell, as shown by orange cells in the image below:

So, now this constraint is applied as follows:

$q_{i,j}=1 \implies sum\left( \mathscr{N}( i,j ) \right ) = 0$

One and only one queen for each colored region

This is again very similar to the other conditions. The only difference is that we need to limit the constraint to cells that have the same colors. If we assume $c_{i,j}$ is the color assigned to the cell on i-th row and j-th coloumn, and

$\mathscr{N}\left ( c_{i,j} \right ) = \left \{ q_{s,t} \mid c_{s,t} = c_{i,j} \right \}$

Then our constraint will look like:

$\sum{\left ( \mathscr{N}(c_{i,j})\right )} = 1$

How do we implement these using OR-Tools

Now in previous section we expressed the constraint and model using Math language. Now you can implement that using any optimization package that you want to use. Here we are going to learn how to do that using OR-Tools.

Setting Decision Variables

You should be familiar already with this step. We are going to add bunch of Boolean variable to our model and we are going to keep track of them so that later we can use them to impose the constraints.

self.variables = [
    [
        self.model.NewBoolVar(f"{i}:{j}")
        for j in range(self.n)
    ]
    for i in range(self.n)
]

Now that we have created one decision variable for each of the cells we are going to enforce the constraints.

One and only one queen per row/columns

We are going to use the variables that we created in previous step to enforce these two constraints.

# one and only one queen per rows
for i in range(self.n):
    self.model.Add(
        sum(self.variables[i]) == 1
    )

# one and only one queen per columns
for j in range(self.n):
    self.model.Add(
        sum([
            self.variables[i][j]
            for i in range(self.n)
        ]) == 1
    )

Note that these constraints should be enforced for each row and column.

No two queens can be next to each other; not even diagonally

Before enforcing this constraint, we are going to first create a small utility function that returns all the row and column tuples surrounding our central cell.

def get_neighbors(self, row: int, col: int) -> list[tuple[int, int]]:
    return [
        (row + di, col + dj)
        for di in [-1, 0, 1]
        for dj in [-1, 0, 1]
        if (
            ((di,dj) != (0,0)) &
            (col + dj >=0) &
            (col + dj < self.n) &
            (row + di >=0) &
            (row + di < self.n)
        )
    ]

This simple utility method returns all the neighboring cell. Notice that it will adjust for the corners and edges of the boards.

Now, all we need to do is:

if the central cell value is 1 (True), meaning a queen is assigned,
sum of all it's neighboring cells should add up to zero.

This can be done using:

# no queen next to each other; not even diagonally
for i in range(self.n):
    for j in range(self.n):
        self.model.Add(
            sum([
                self.variables[neighbor_row][neighbor_col]
                for (neighbor_row, neighbor_col) in self.get_neighbors(row=i, col=j)
            ]) == 0
        ).OnlyEnforceIf(self.variables[i][j])

Notice the use of $\mathtext{OnlyEnforceIf}$ . In Zipping where we show how to implement a solver to solve LinkedIn's Zip puzzle, we introduced this feature, that is putting a constraint on constraint and controlling when that constraint should be enforced, and when it should be neglected. In that post we created some new boolean variable, because of the situation in that problem. However, here, we are going to reuse the same decision variables, without introducing new boolean variables.

One and only one queen for each region

There is nothing specific about this constraint. The only difference is how we are collecting the cells that are of the same type. We can make use of Python's Dictionary type:

# One queen per region
region_map: dict[str, list[IntVar]] = {}

for i in range(self.n):
    for j in range(self.n):
        region_map.setdefault(
            self.cell_colors[i][j],
            []
        ).append(self.variables[i][j])

First we are creating an empty dictionary called "region_map". This dictionary will have a key for each region (their color) and a list of boolean variables that are associated with that region. Notice the use of "dict.setdefault" in when pulling the list. Essentially, if it is the first time that we see a new region color, by calling "setdefault", we are initializing its value to an empty list, and then we keep adding the boolean variables to it. If the region color is already seen before (the key exists in the dictionary), the existing list is returned and then another boolean variables is appended to it. This way helps us to pass all the cell only once and collect all the cells belonging to the same colored region in one list.

Now enforcing the constraint is easy:

for v in region_map.values():
    self.model.add(sum(v) == 1)

All the code

We discussed different code snippet on how to implement a Queen Puzzle Solver using OR-Tools. If you want to see all these snippet put together in one code (and download the code and run it for yourself) you can grab a Python notebook implementing this here.

Now let’s decide: Queen? or Not-Queen?

Let's solve the puzzle shown at beginning of this page:

queen_solver = QueenSolver(
    cell_colors=[
        [ "p",  "p",  "p",  "p",  "p",  "p",  "p",  "o",  "r", ],
        ["op", "op",  "p", "op", "op",  "p",  "o",  "o",  "r", ],
        [ "p", "op", "op", "op",  "p",  "p",  "o",  "r",  "r", ],
        [ "p",  "p",  "p",  "p",  "p",  "w",  "o",  "o",  "r", ],
        [ "p",  "b",  "p",  "p",  "p",  "w",  "w",  "o",  "y", ],
        [ "p",  "b",  "b",  "p",  "w",  "w",  "w",  "y",  "y", ],
        [ "p",  "p",  "b", "dg",  "w",  "g",  "g",  "g",  "y", ],
        [ "p",  "b",  "b", "dg",  "g",  "g", "dg",  "g",  "g", ],
        [ "p",  "b", "dg", "dg", "dg", "dg", "dg", "dg", "dg", ],
    ]
)
queen_solver.solve()

When you run this code, you will get:

+---+---+---+---+---+---+---+---+---+
| . | . | . | . | . | . | . | . | Q |
+---+---+---+---+---+---+---+---+---+
| . | . | . | . | . | . | Q | . | . |
+---+---+---+---+---+---+---+---+---+
| . | . | . | Q | . | . | . | . | . |
+---+---+---+---+---+---+---+---+---+
| . | . | . | . | . | Q | . | . | . |
+---+---+---+---+---+---+---+---+---+
| . | Q | . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+---+
| . | . | . | . | . | . | . | Q | . |
+---+---+---+---+---+---+---+---+---+
| Q | . | . | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+---+
| . | . | . | . | Q | . | . | . | . |
+---+---+---+---+---+---+---+---+---+
| . | . | Q | . | . | . | . | . | . |
+---+---+---+---+---+---+---+---+---+