# 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

Tip