How to model the n-queens problem using linear programming

Solution to the challenge

For the eight queens problem on a standard chessboard, one solution is presented below. For this case, there are a total of 92 distinct solutions, making this a rich and engaging puzzle for anyone interested in logic, mathematics, and chess.

To model Sudoku as a binary linear optimization problem, we need to first define all the components of the model.

Sets of indices

• \(\mathcal{R}\): Rows of the board.
• \(\mathcal{C}\): Columns of the board.

Parameters

• There are no additional parameters, since the board is initially considered empty.

Decision variables

• \(x_{rc} = 1\) if there is a queen located at coordinate $(r,c)$ of the board, and 0 otherwise, $\forall r \in \mathcal{R}, \; \forall c \in \mathcal{C}$.

The objective is to place the maximum number of queens on the chessboard.

Objective function

\[\max z = \displaystyle \sum_{r \in \mathcal{R}} \displaystyle \sum_{c \in \mathcal{C}} x_{rc}\]

Below, we enumerate the constraints that ensure no queens attack each other.

Each row must contain one queen at most:

\[\displaystyle \sum_{r \in \mathcal{R}} x_{rc} \leq 1 \quad \forall c \in \mathcal{C}\]

Each column must contain one queen at most:

\[\displaystyle \sum_{c \in \mathcal{C}} x_{rc} \leq 1 \quad \forall r \in \mathcal{R}\]

Each diagonal can contain at most one queen:

\[\displaystyle \sum_{(r,c):r-c=k} x_{rc} \leq 1 \quad \forall k = -(-|\mathcal{C}|-1),\ldots,(|\mathcal{R}|-1)\] \[\displaystyle \sum_{(r,c):r+c=k} x_{rc} \leq 1 \quad \forall k = 2,\ldots,|\mathcal{R}|+|\mathcal{C}|\]

Variables domain

\[x_{rc} \in \{0,1\} \quad \forall r \in \mathcal{R}, \; \forall c \in \mathcal{C}\]

Source Code

The complete Python implementation of the optimization model presented in this post, is available in the project’s GitHub repository.

GitHub repository: fjmartincampo/Queens