n-Queens SAT problem

I came across this nice snippet by John D. Cook, and it immediately possessed me to think about what the compressed Boolean representation of such a problem would look like. For those not aware of the 8 queens problem, here is a brief look below:

Question

Place 8 queens of either colour in an empty $8\times 8$ chessboard, such that no two queens lie on the same row, column or diagonal. Does there exist a valid arrangement under these constraints?

Assuming that there exists such an arrangement, we can convey the solution as a Boolean equation. A Boolean equation is simply a collection of predicates (or variables) which can take either True or False values and are connected together as an expression using logical operators like AND, OR and NOT. An example of a Boolean expression would be $p\wedge q\vee \neg r$, where $p$, $q$ and $r$ are Boolean variables and $\wedge$, $\vee$, $\neg$ are AND, OR and NOT logical operators respectively.

Boolean Satisfiability Problems

Consider an expression which can have a truth value, such as “the sky is blue and the road is empty”, it can be broken into two parts: “the sky is blue” ($p$), “the road is empty” ($q$) which are connected together using an AND operator. Thus if you represent the entire statement as an expression $S:=p\wedge q$, the truth value of the overall statement $S$ is contingent on whether both its predicates are True or not.

Similarly, you can condense the 8 queens problem into a Boolean expression and can tell whether a possible arrangement of queens satisfies the preset conditions based on what the truth value of the overall expression representing the overall problem is. Such a class of problems are called Boolean Satisfiability Problems, often abbreviated as SAT, and involves finding truth value assignments for which the overall expression is true.

Consider one of the above examples:

$$S:=p\wedge q\neg r$$

The statement $S$ is only true when $p$ is True, $q$ is True and $r$ is False, this can be represented as:

$$p\mapsto \text{True},q\mapsto \text{True},r\mapsto \text{False}$$

Therefore, the 8 queens problem holds only if we are able to find such a set of truth values for each of its predicates.

n-Queens problem

As illustrated in the blog, consider the $8\times 8$ chessboard as a grid each of whose cells is represented by $b_{i,j}$ where $b_{i,j}=\text{True}$ if there is a queen in that particular square or $\text{False}$ otherwise. There are three conditions that have to be met for any arrangement of queens to be valid:

1. Only one queen per row
2. Only one queen per column
3. No two queens on the same diagonal

Ensuring that there is at least one queen per row and column is simple. For each row and for each column we will have: $b_{i,1}\vee b_{i,2}\vee \cdots \vee b_{i,8}$ and $b_{1,j}\vee b_{2,j}\vee \cdots \vee b_{8,j}$ respectively. However, this alone is not sufficient to encode the necessary constraints. We must ensure that there is at least one queen for each row, column and additionally we must also ensure that there are not more that one queen for each row, column.

As mentioned in the blog, that is indeed the difficult part, and from the given two approaches, I will highlight the one that I felt was easier to understand and thus explain (although both approaches are equivalent).

For each grid cell in each row we will need to ensure that if that particular grid cell contains a queen none of the rest of the cells in its row should contain another queen. This can be expressed for each grid cell $b_{i,j}$ as:

$$b_{i,j}⟹\neg \left(\underset{k\in N_j}{\bigvee }{b}_{i,k}\right)$$

where $⟹$ is a logical operator that means “implies”, and can be broken down into $\neg p\vee q$. This means that if there is a queen in $b_{i,j}$, (i.e., $b_{i,j}=\text{True}$) there are no queens in any of the rest of the cells of that row. For a chessboard square, the number of rows and columns will be equal with each $i$ and $j$ being an element of the set $N$, which in this case is $\{1,2,\dots ,8\}$, with $N_j$ representing the set of all grid cells excepting $b_{i,j}$. This statement if valid for only a particular grid cell in context of the $i$-th row of the chessboard. Identical statement have to be constructed for all the elements of the $i$-th row and joined together using AND operators in the following manner:

$${\Phi }_i=\underset{j=1}{\overset{8}{\bigwedge }}\left(b_{i,j}⟹\neg \left(\underset{k\in N_j}{\bigvee }{b}_{i,k}\right)\right)$$

In a similar manner column specific constraints can be constructed.

$${\Phi }_j=\underset{i=1}{\overset{8}{\bigwedge }}\left(b_{i,j}⟹\neg \left(\underset{k\in N_i}{\bigvee }{b}_{k,j}\right)\right)$$

where again $N_i:=N\setminus \{i\}$.

Thus, the constraints for rows (${\Phi }_r$) and columns (${\Phi }_c$) can be encoded as:

$${\Phi }_r=\underset{i\in N}{\bigwedge }\left(\left(\underset{j\in N}{\bigvee }{b}_{i,j}\right)\wedge {\Phi }_i\right)$$

and

$${\Phi }_c=\underset{j\in N}{\bigwedge }\left(\left(\underset{j\in N}{\bigvee }{b}_{i,j}\right)\wedge {\Phi }_j\right)$$

Finally, we will have a diagonal constraint that ensure that there are no two queens that share the same diagonal. This is rather straightforward as you have:

$${\Phi }_d=\underset{i,j\in N}{\bigwedge }\neg b_{i,j}\vee \neg b_{i+k,i+k}\forall k\in K$$

where $K$ dictates the range of $k$ based on where the grid cell $b_{i,j}$ is situated. This might not be the most efficient encoding of the problem as it contains many redundant logical operations, but it certainly a valid one out of many. The overall expression that for the 8 queens problem therefore is:

$$\Phi ={\Phi }_r\wedge {\Phi }_c\wedge {\Phi }_d$$

For an $n\times n$ chessboard, this same representation can be scaled up by expanding the set $N$ to extend from $1$ to $n$.

n-Kings problem

I also became interested in a problem slightly reminiscent of the n-Queens problem. Here instead of having a chessboard with n queens we can have n kings, in such a way that no two kings exist in the same neighbourhood. A neighbourhood is defined as the 8 boxes surrounding a grid cell. An example of which can be seen below:

Again, a chessboard is expressed as a collection of grid cells each having some truth value. A grid cell will be true only when neither of the cell in the rows above and below it are true: $\neg (b_{i,j-1}\vee b_{i,j+1})$, similarly, no cells on either sides should be true $\neg (b_{i-1,j}\vee b_{i+1,j})$, additionally, no cells on either diagonals of the cell should contain a king $\neg (b_{i-1,j-1}\vee b_{i+1,j-1}\vee b_{i+1,j+1}\vee b_{i-1,j+1})$.

A complete and viable arrangement for a simple $4\times 4$ grid is shown below:

Putting it all together we will have a constraint ${\Phi }_{i,j}$ for each cell $b_{i,j}$:

$$b_{i,j}⟹\neg (b_{i,j-1}\vee b_{i,j+1}{b}_{i-1,j-1}\vee b_{i+1,j-1}\vee b_{i+1,j+1}\vee b_{i-1,j+1}\vee b_{i-1,j}\vee b_{i+1,j})$$

The expression that dictates the constraints of the n-kings problem is thus:

$$\underset{i,j\in N}{\bigwedge }{\Phi }_{i,j}$$

This is not the most efficient representation of the problem considering the high number of redundant operations being considered. However, it is a sufficiently complete one.