The n-Queens Problem
Prerequisites
- Please look at Getting Started first for the most basic functions and the setup of OPTANO.Modeling
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
- Step 1: Create Business objects for your Model
- Step 2: Create your Model Class
- Step 3: Retrieve the Solution of your Model