Linear constraints to placing $N$ queens on an $N \times N$ chessboard?

Question

I'm trying to formulate the problem of placing $N$ queens on an $N \times N$ chessboard such that no two queens share any row, column, or diagonal.

I managed to define my decision variable as $x[n][n]$, a binary variable indicating if the location is used or not. But I couldn't find a way to write any linear constraints. Any ideas on how to proceed, please?

Answer 1

I will use the following convention :

Any space is refered to by its coordinate (i,j). The bottom left space is (1,1), The bottom right space is (1,8), the top right is (8,1) and top left is (8,8).

Variables

$x_{ij} = 1$ if a queen is on the space (i,j), 0 otherwise

Problem

$$\max \sum\limits_{i,j} x_{ij}$$

(All the spaces in an increasing diagonal have the same value for $i-j$) $$ \sum\limits_{i,j|j-i = k} x_{ij} \leq 1 \mbox{ for } k\in \{-6, -5, ..., 5, 6\}$$

(all the spaces in a decreasing diagonal have the same value for $i+j$) $$ \sum\limits_{i,j|i+j = k} x_{ij} \leq 1 \mbox{ for } k\in \{2, 3, ..., 14\}$$

$$x_{ij}\in \{0,1\}$$

Answer 2

There are several different formulations for the problem as both a Linear Program and as a Constraint Program. Let's look at the Linear Program first.

Binary Linear Program Formulation:

Let $Q_{ij}$ be a binary variable to denote if a Queen is placed in column $i$, row $j$, and let $n$ denote the board size of a $n\times n$ board. Then, the formulation will go as follows:

$$\max z = 0$$ Subject to:

There should only exist one queen in each row:

$$\sum_{i=1}^n Q_{ij} = 1\quad\forall j\in 1,2,\ldots,n$$

There should only exist one queen in each column:

$$\sum_{j=1}^n Q_{ij} = 1\quad\forall i\in 1,2,\ldots,n$$

Queens shouldn't attack each other on each diagonal: $$\sum_{i-j=k}^nQ_{ij}\le 1,\quad\forall k = 2-n, \ldots,n-2$$ $$\sum_{i+j=k}^nQ_{ij}\le 1,\quad\forall k = 2, \ldots,2n-2$$

Variable Restrictions:

$$Q_{ij}\in\{0,1\}\quad\forall i,j \in 1,\ldots, n$$

Integer Linear Program Formulation:

Let $Q_{i}$ be a integer variable to denote if a Queen of a certain column is placed in row $i$ (since we know all columns will have a Queen), and let $n$ denote the board size of a $n\times n$ board. Then, the formulation will go as follows:

$$\min z = S_1 + S_2$$

Queens cannot be placed in the same rows:

$$Q_i \le Q_j-1 + M b_1 \quad\forall i < j$$ $$Q_i \ge Q_j+1 - M (1-b_1) \quad\forall i < j$$

Queens diagonals must be respected:

$$Q_{i} - Q_{j} \le S_1\quad\forall i,j\in{1,2,\ldots, n}\quad\text{where }i\ne j$$

$$Q_{j} - Q_{i} \le S_2\quad\forall i,j\in{1,2,\ldots, n}\quad\text{where }i\ne j$$

$$S_1 + S_2\le |i - j| + M b_2 \quad\forall i < j$$ $$S_1 + S_2\ge |i - j|+1 - M(1-b_2) \quad\forall i < j$$

Variable Restrictions: $$1\le Q_{i}\le n\quad\forall i \in 1,\ldots, n$$ $$Q_{i}\in\mathbb{Z}^+\quad\forall i \in 1,\ldots, n$$ $$b_1, b_2\in\{0,1\}$$ $$S_1,S_2\ge0$$

$M$ is a pre-chosen integer $n+1$.

Constraint Program Formulation (Not LP)

Let $Q_{i}$ be a integer variable to denote if a Queen of a certain column is placed in row $i$ (since we know all columns will have a Queen), and let $n$ denote the board size of a $n\times n$ board. Then, the formulation will go as follows:

Queens cannot be placed in the same rows:

$$Q_{i} \ne Q_{j}\quad\forall i,j\in{1,2,\ldots, n}\quad\text{where }i\ne j$$

Queens diagonals must be respected:

$$|Q_{i} - Q_{j}| \ne |i - j| \quad\forall i,j\in{1,2,\ldots, n}\quad\text{where }i\ne j$$

Variable Restrictions: $$1\le Q_{i}\le n\quad\forall i \in 1,\ldots, n$$ $$Q_{i}\in\mathbb{Z}^+\quad\forall i \in 1,\ldots, n$$