N ферзей

Это руководство было изначально предоставлено Мэтью Хелмом (Matthew Helm) и Матье Танно (Mathieu Tanneau).

Задача об N ферзях заключается в расстановке N ферзей на шахматной доске размером N x N таким образом, чтобы ни один из ферзей не мог атаковать другого. В шахматах ферзь может двигаться по вертикали, горизонтали и диагонали, поэтому в любом ряду, в любом столбце и на любой диагонали может быть не более одного ферзя.

Обратите внимание, что благодаря грамотному расположению ни один из ферзей на рисунке не может атаковать другого.

using JuMP
import HiGHS
import LinearAlgebra

N ферзей

N = 8

model = Model(HiGHS.Optimizer)
set_silent(model)

Далее давайте создадим шахматную доску размером N x N из двоичных значений. Значение 0 будет представлять пустое место на доске, а 1 — место, занятое одним из ферзей:

@variable(model, x[1:N, 1:N], Bin);

Теперь можно добавить ограничения:

В ряду или столбце должен быть ровно один ферзь:

for i in 1:N
    @constraint(model, sum(x[i, :]) == 1)
    @constraint(model, sum(x[:, i]) == 1)
end

На любой диагонали может быть только один ферзь:

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

Теперь можно запустить модель и посмотреть, удастся ли ей найти допустимое решение:

optimize!(model)
@assert is_solved_and_feasible(model)

Посмотрим, какое решение нашла модель:

solution = round.(Int, value.(x))

8×8 Matrix{Int64}:
 0  0  0  0  1  0  0  0
 0  0  1  0  0  0  0  0
 0  0  0  0  0  0  0  1
 0  0  0  1  0  0  0  0
 0  0  0  0  0  0  1  0
 1  0  0  0  0  0  0  0
 0  0  0  0  0  1  0  0
 0  1  0  0  0  0  0  0