How to model the n-queens problem using linear programming

Chess is one of the oldest and most celebrated board games in history, with origins dating back over a thousand years. Traditionally played on an $8 \times 8$ board, chess involves strategy, tactics, and deep thinking, as each piece moves according to specific rules. Beyond the game itself, the chessboard and its pieces have inspired a variety of logic puzzles and mathematical challenges.

One of the most famous of these is the eight queens problem, which asks how to place eight queens on a standard chessboard so that no two queens threaten each other—meaning that no two queens share the same row, column, or diagonal. This puzzle has fascinated mathematicians and enthusiasts alike, as it combines combinatorial reasoning with spatial visualization.

The problem can also be generalized to place the maximum number of queens on a board of different dimensions, $m \times n$, creating a family of logic challenges with increasing complexity. For example, the board shown below represents one possible solution to the eight queens problem. On a standard chessboard, 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.

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}, c \in \mathcal{C}\]

Notes for the reader:

• This model allows solving the n-queens problem using binary linear programming solvers like Gurobi.
• Although this approach is more mathematical than manually placing the queens, it demonstrates how optimization modeling can systematically solve combinatorial logic problems.