9  The N-queens Problem

The n-queens problem is a classic puzzle that involves placing \(n\) queens on an \(n \times n\) chessboard in such a way that no two queens threaten each other. In other words, no two queens can be placed on the same row, column, or diagonal. The problem is called the \(n\)-queens problem because it can be generalized to any size of \(n\).

For example, the 8-queens problem involves placing 8 queens on an 8x8 chessboard, and the solution requires that no two queens share the same row, column, or diagonal.

The n-queens problem is a well-known problem in computer science and has been studied extensively because it has applications in various fields, such as optimization, artificial intelligence, and computer graphics. There are various algorithms and techniques that can be used to solve the n-queens problem, including brute-force search, backtracking, and genetic algorithms. In this chapter, we’ll model this problem as an integer programming problem and solve it using OR-Tools.

To model this problem on an \(n \times n\) chessboard, we define the following decision variable:

The complete model given below is based on Letavec and Ruggiero (2002).

\[\begin{align} \text{max.} &\quad 0 \label{nq-obj}\\ \text{s.t.} &\quad \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} x_{ij} = n \label{nq-cons1} \\ &\quad \sum_{j=0}^{n-1} x_{ij} \leq 1, \ \forall i = 0, \cdots, n-1 \label{nq-cons2} \\ &\quad \sum_{i=0}^{n-1} x_{ij} \leq 1, \ \forall j = 0, \cdots, n-1 \label{nq-cons3}\\ &\quad \sum_{i=0}^{n-1} \sum_{j=0, i+j=k}^{n-1} x_{ij} \leq 1, \ \forall k = 1, \cdots, 2(n-1) - 1 \label{nq-cons4}\\ &\quad \sum_{i=0}^{n-1} \sum_{j=0, i-j=k}^{n-1} x_{ij} \leq 1, \ \forall k = 2-n, \cdots, n-2 \label{nq-cons5}\\ &\quad x_{ij} \in \{0, 1\},\ i, j = 0, \cdots, n-1 \end{align}\]

In the formulation, the objective function \(\eqref{nq-obj}\) serves no practical use as our goal is to find any feasible solution to the puzzle. Constraints \(\eqref{nq-cons1}\) require that there are exactly \(n\) queens be placed on a board of size \(n \times n\). Constraints \(\eqref{nq-cons2}\) make sure that there is at most one queen be placed in any row of the board. Similarly, constraints \(\eqref{nq-cons3}\) ensure that there is at most one queen be placed in any column of the board. To understand constraints \(\eqref{nq-cons4}\) and \(\eqref{nq-cons5}\), let’s look at a 8-queens solution in Figure 9.1.

Note that no two queens can be placed on the same diagonal anywhere on the board. Upon observing the chessboard, we can see that there are two types of diagonals:

The first type of diagonals can be expressed as constraints \(\eqref{nq-cons4}\) and the second type of diagonals can be expressed as constraints \(\eqref{nq-cons5}\). Both constraints guarantee that there cannot be any two queens showing up in the same diagonal.

Figure 9.1: A 8-Queens solution

The complete code to solve the problem is given below.

from ortools.linear_solver import pywraplp
import numpy as np
from itertools import product

class NQueensSolver:
    
    def __init__(self, size: int):
        self._size = size
        
        self._solver = None
        self._var_x = None
        self._opt_x = None
        
    def build_model(self):
        # instantiate solver
        self._solver = pywraplp.Solver.CreateSolver('SCIP')

        # create decision variables
        self._var_x = np.empty((self._size, self._size), 
                            dtype=object)
        for i, j in product(range(self._size), 
                            range(self._size)):
            self._var_x[i][j] = \
                self._solver.BoolVar(name=f'x_{i,j}')

        # declare objective function
        self._solver.Maximize(0)
        
        # constraint: there must be n queens on the board
        expr = [self._var_x[i][j]
                for i in range(self._size)
                for j in range(self._size)]
        self._solver.Add(self._solver.Sum(expr) == self._size)

        # constraint: no two queens can be in the same row
        for row in range(self._size):
            expr = [self._var_x[row][j]
                    for j in range(self._size)]
            self._solver.Add(self._solver.Sum(expr) <= 1)
            
        # constraint: no two queens can be in the same column
        for col in range(self._size):
            expr = [self._var_x[i][col]
                    for i in range(self._size)]
            self._solver.Add(self._solver.Sum(expr) <= 1)

        # constraint: no two queens can be in the same diagonal
        for k in range(1, 2 * (self._size - 1) - 1):
            expr = [self._var_x[i][j]
                    for i in range(self._size)
                    for j in range(self._size)
                    if i + j == k]
            self._solver.Add(self._solver.Sum(expr) <= 1)

        for k in range(2 - self._size, self._size - 2):
            expr = [self._var_x[i][j]
                    for i in range(self._size)
                    for j in range(self._size)
                    if i - j == k]
            self._solver.Add(self._solver.Sum(expr) <= 1)
    
    def optimize(self):
        status = self._solver.Solve()
        if status == pywraplp.Solver.OPTIMAL:
            self._opt_x = np.zeros((self._size, 
                                    self._size))
            for i, j in product(range(self._size), 
                                range(self._size)):
                self._opt_x[i][j] = \
                    self._var_x[i][j].solution_value()
        else:
            print("solve failure!")
            print(f"status={status}")

    @property
    def opt_x(self): return self._opt_x
    
    def get_queen_coordinates(self):
        coordinates = [(i, j) 
            for i in range(self._size)
            for j in range(self._size)
            if self._opt_x[i][j] == 1]
        return coordinates

Figure 9.2 shows a 4-Queens puzzle solution.

Figure 9.2: A 4-Queens solution

Figure 9.3 shows a 10-Queens puzzle solution.

Figure 9.3: A 10-Queens solution

Figure 9.4 shows a 20-Queens puzzle solution.

Figure 9.4: A 20-Queens solution