Computes the n-th element of the OEIS sequence A075324

A075324.jl

using JuMP
using Gurobi
#using HiGHS
using LinearAlgebra

"""
Computes the n-th element of the OEIS sequence A075324
- Uses the free academic license of the commerical MILP solver Gurobi, must be externally installed
- HiGHS is a single-threaded open source alternative which is shipped with the Julia package

Alexis Langlois-Rémillard, Christoph Müßig, and Érika Róldan, Complexity of Chess Domination Problems, arXiv:2211.05651 [math.CO], 2022.
"""
function A075324(N::Int64)
    model = Model(Gurobi.Optimizer)
    # model = Model(HiGHS.Optimizer)
    @variable(model, x[1:N, 1:N], Bin)

    # duplicate constraints are ignored by the solver
    for i in 1 : N
        for j in 1 : N
            @constraint(model, sum(x[i, :]) <= 1)  # one queen per line
            @constraint(model, sum(x[:, i]) <= 1)  # one queen per column
            @constraint(model, sum(LinearAlgebra.diag(x, j - i)) <= 1)  # one queen per diagonal
            @constraint(model, sum(LinearAlgebra.diag(reverse(x; dims = 1), i + j - N - 1)) <= 1)

            # every tile guarded by at least one queen
            @constraint(model, sum(union(x[i, :], x[:, j], LinearAlgebra.diag(x, j - i), LinearAlgebra.diag(reverse(x; dims = 1), i + j - N - 1))) >= 1)
        end
    end

    @objective(model, Min, sum(x))
    
    optimize!(model)

    return Int(sum(round.(value.(x)))), round.(value.(x))
end

"""
N = 26
- 14 Queens placed on (x, y): (15, 24) (25, 6) (9, 2) (23, 12) (11, 14) (13, 8) (1, 18) (5, 10) (3, 26) (7, 20) (17, 16) (8, 5) (19, 4) (21, 22)
N = 27
- 15 Queens placed on (x, y): (12, 1) (8, 2) (18, 3) (17, 5) (26, 8) (5, 11) (23, 14) (2, 17) (11, 20) (25, 22) (20, 23) (1, 24) (3, 25) (14, 26) (27, 27)
N = 28
- 15 Queens placed on (x, y): (10, 2) (20, 4) (26, 6) (12, 8) (4, 10) (14, 12) (2, 14) (15, 15) (28, 16) (24, 18) (18, 20) (6, 22) (16, 24) (22, 26) (8, 28)
N = 29
- 16 Queens placed on (x, y): (26, 2) (5, 3) (20, 4) (10, 6) (4, 8) (8, 10) (18, 12) (22, 14) (28, 16) (2, 18) (12, 20) (1, 21) (16, 22) (24, 24) (14, 26) (6, 28)
N = 30
- 16 Queens placed on (x, y): (1, 1) (21, 3) (11, 5) (26, 6) (5, 7) (19, 9) (27, 11) (17, 13) (29, 15) (3, 17) (7, 19) (13, 21) (25, 23) (15, 25) (9, 27) (23, 29)
N = 31
- 17 Queens placed on (x, y): (25, 1) (8, 2) (18, 4) (31, 6) (6, 8) (20, 9) (22, 10) (30, 12) (14, 14) (2, 16) (28, 18) (16, 20) (12, 22) (26, 24) (4, 26) (10, 28) (24, 30)
"""