# 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 GLPK
import LinearAlgebra
```

N-Queens

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

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

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 Array{VariableRef,2}: 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 = 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)`

We can now review the solution that our model found:

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

8×8 Array{Int64,2}: 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 1 0 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 0

*This page was generated using Literate.jl.*