# N-Queens

**Originally Contributed by**: Matthew Helm (with help from @mtanneau on Julia Discourse)

The N-Queens problem involves placing N queens on an N x N chessboard such that none of the queens attacks another. In chess, a queen can move vertically, horizontally, and diagonally so there cannot be more than one queen on any given row, column, or diagonal.

*Note that none of the queens above are able to attack any other as a result of their careful placement.*

```
using JuMP
import HiGHS
import LinearAlgebra
```

N-Queens

```
N = 8
model = Model(HiGHS.Optimizer)
```

```
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: HiGHS
```

Next, let's create an N x N chessboard of binary values. 0 will represent an empty space on the board and 1 will represent a space occupied by one of our queens:

`@variable(model, x[1:N, 1:N], Bin)`

```
8×8 Matrix{VariableRef}:
x[1,1] x[1,2] x[1,3] x[1,4] x[1,5] x[1,6] x[1,7] x[1,8]
x[2,1] x[2,2] x[2,3] x[2,4] x[2,5] x[2,6] x[2,7] x[2,8]
x[3,1] x[3,2] x[3,3] x[3,4] x[3,5] x[3,6] x[3,7] x[3,8]
x[4,1] x[4,2] x[4,3] x[4,4] x[4,5] x[4,6] x[4,7] x[4,8]
x[5,1] x[5,2] x[5,3] x[5,4] x[5,5] x[5,6] x[5,7] x[5,8]
x[6,1] x[6,2] x[6,3] x[6,4] x[6,5] x[6,6] x[6,7] x[6,8]
x[7,1] x[7,2] x[7,3] x[7,4] x[7,5] x[7,6] x[7,7] x[7,8]
x[8,1] x[8,2] x[8,3] x[8,4] x[8,5] x[8,6] x[8,7] x[8,8]
```

Now we can add our constraints:

There must be exactly one queen in a given row/column

```
for i in 1:N
@constraint(model, sum(x[i, :]) == 1)
@constraint(model, sum(x[:, i]) == 1)
end
```

There can only be one queen on any given diagonal

```
for i in -(N - 1):(N-1)
@constraint(model, sum(LinearAlgebra.diag(x, i)) <= 1)
@constraint(model, sum(LinearAlgebra.diag(reverse(x, dims = 1), i)) <= 1)
end
```

That's it! We are ready to put our model to work and see if it is able to find a feasible solution:

`optimize!(model)`

```
Presolving model
42 rows, 64 cols, 252 nonzeros
42 rows, 64 cols, 270 nonzeros
Objective function is integral with scale 1
Solving MIP model with:
42 rows
64 cols (64 binary, 0 integer, 0 implied int., 0 continuous)
270 nonzeros
( 0.0s) Starting symmetry detection
( 0.0s) Found 1 full orbitope(s) acting on 64 columns
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
0 0 0 0.00% 0 inf inf 0 0 4 29 0.0s
Solving report
Status Optimal
Primal bound 0
Dual bound 0
Gap 0% (tolerance: 0.01%)
Solution status feasible
0 (objective)
0 (bound viol.)
8.82206753991e-15 (int. viol.)
0 (row viol.)
Timing 0.04 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 142 (total)
0 (strong br.)
90 (separation)
23 (heuristics)
```

We can now review the solution that our model found:

`solution = round.(Int, value.(x))`

```
8×8 Matrix{Int64}:
0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
```

This tutorial was generated using Literate.jl. View the source `.jl`

file on GitHub.