The n-Queens Problem

Prerequisites

The mathematical Model

Sets: \begin{array}{l} B = \text{The chess board of size }n\times n\newline \end{array}

Parameters: $$n = \text{number of columns and rows of the quadratic board B}$$

Variables: $$y_{ij} = \begin{cases} 1, \text{ if you place a queen at position }(i,j)\text{ on board }B\newline 0, \text{ else} \end{cases}$$

Objective: $$min 0^T y \qquad \text{(the objective function is irrelevant since we only want the constraints to hold)}$$

Restrictions: \begin{array}{l} \sum\limits_{i=1}^{n} y_{i,j} = 1 & \forall i \in \text{{1,..,n}} & \text{(exactly one queen in each row)}\newline \sum\limits_{j=1}^{n} y_{i,j} \le 1 & \forall j \in \text{{1,..,n}} & \text{(only one queen in each column)}\newline \sum\limits_{j:j,i+j\in\text{{1,..,n}}} y_{i+j,j} \le 1 & \forall i \in \text{{-n+1,..,n-1}} & \text{(right diagonals)}\newline \sum\limits_{j:j,i-j\in\text{{1,..,n}}} y_{i-j,j} \le 1 & \forall i \in \text{{-n+1,..,n-1}} & \text{(left diagonals)} \end{array}

The n-Queens Problem