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: 108…652

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

This page was generated using Literate.jl.