# N queens

using Convex, GLPK, LinearAlgebra, SparseArrays, Test
aux(str) = joinpath(@__DIR__, "aux_files", str) # path to auxiliary files
include(aux("antidiag.jl"))

n = 8
8

We encode the locations of the queens with a matrix of binary random variables.

x = Variable((n, n), BinVar)
Variable
size: (8, 8)
sign: real
vexity: affine
id: 104…157

Now we impose the constraints: at most one queen on any anti-diagonal, at most one queen on any diagonal, and we must have exactly one queen per row and per column.

# At most one queen on any anti-diagonal
constraints = Constraint[sum(antidiag(x, k)) <= 1 for k in -n+2:n-2]
# At most one queen on any diagonal
append!(constraints, [sum(diag(x, k)) <= 1 for k in -n+2:n-2])
# Exactly one queen per row and one queen per column
append!(constraints, [sum(x, dims = 1) == 1, sum(x, dims = 2) == 1])
p = satisfy(constraints)
solve!(p, GLPK.Optimizer)
Problem statistics
problem is DCP         : true
number of variables    : 1 (64 scalar elements)
number of constraints  : 28 (42 scalar elements)
number of coefficients : 60
number of atoms        : 86

Solution summary
termination status : OPTIMAL
primal status      : FEASIBLE_POINT
dual status        : NO_SOLUTION

Expression graph
satisfy
└─ nothing
subject to
├─ ≤ constraint (affine)
│  └─ + (affine; real)
│     ├─ sum (affine; real)
│     │  └─ …
│     └─ [-1;;]
├─ ≤ constraint (affine)
│  └─ + (affine; real)
│     ├─ sum (affine; real)
│     │  └─ …
│     └─ [-1;;]
├─ ≤ constraint (affine)
│  └─ + (affine; real)
│     ├─ sum (affine; real)
│     │  └─ …
│     └─ [-1;;]
⋮


Let us test the results:

for k in -n+2:n-2
@test evaluate(sum(antidiag(x, k))) <= 1
@test evaluate(sum(diag(x, k))) <= 1
end
@test all(evaluate(sum(x, dims = 1)) .≈ 1)
@test all(evaluate(sum(x, dims = 2)) .≈ 1)
Test Passed