N-queens minimum and knights and bishops: Difference between revisions
Content added Content deleted
m (→{{header|J}}) |
(julia example) |
||
Line 456: | Line 456: | ||
└──────────┘ |
└──────────┘ |
||
</lang> |
</lang> |
||
=={{header|Julia}}== |
|||
Uses the HiGH optimizer for Queens and Bishops and the slower Cbc optimizer for Knights for Cbc's complementarity support. |
|||
<lang ruby>""" Rosetta code task N-queens_minimum_and_knights_and_bishops """ |
|||
import HiGHS |
|||
import Cbc |
|||
using JuMP |
|||
using LinearAlgebra |
|||
""" Print a matrix of zeros and ones using a char ch for 1, a period for 0. """ |
|||
function smatrix(x, n, ch) |
|||
s = "" |
|||
for i in 1:n, j in 1:n |
|||
s *= lpad(x[i, j] == 1 ? "$ch" : ".", 2) * (j == n ? "\n" : "") |
|||
end |
|||
return s |
|||
end |
|||
""" N-queens minimum, oeis.org/A075458 """ |
|||
function queensminimum(N, char = "Q") |
|||
if N < 4 |
|||
a = zeros(Int, N, N) |
|||
a[N ÷ 2 + 1, N ÷ 2 + 1] = 1 |
|||
return 1, smatrix(a, N, char) |
|||
end |
|||
model = Model(HiGHS.Optimizer) |
|||
@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(diag(x, i)) <= 1) |
|||
@constraint(model, sum(diag(reverse(x, dims = 1), i)) <= 1) |
|||
end |
|||
for i in 1:N, j in 1:N |
|||
@constraint(model, sum(x[i, :]) + sum(x[:, j]) + sum(diag(x, j - i)) + |
|||
sum(diag(rotl90(x), N - j - i + 1)) >= 1) |
|||
end |
|||
set_silent(model) |
|||
@objective(model, Min, sum(x)) |
|||
optimize!(model) |
|||
solution = round.(Int, value.(x)) |
|||
minresult = sum(solution) |
|||
return minresult, smatrix(solution, N, char) |
|||
end |
|||
""" N-bishops minimum, same as N """ |
|||
function bishopsminimum(N, char = "B") |
|||
N == 1 && return 1, "$char" |
|||
N == 2 && return 2, "$char .\n$char .\n" |
|||
model = Model(HiGHS.Optimizer) |
|||
@variable(model, x[1:N, 1:N], Bin) |
|||
for i in 1:N, j in 1:N |
|||
@constraint(model, sum(diag(x, j - i)) + sum(diag(rotl90(x), N - j - i + 1)) >= 1) |
|||
end |
|||
set_silent(model) |
|||
@objective(model, Min, sum(x)) |
|||
optimize!(model) |
|||
solution = round.(Int, value.(x)) |
|||
minresult = sum(solution) |
|||
return minresult, smatrix(solution, N, char) |
|||
end |
|||
""" N-knights minimum, oeis.org/A342576 """ |
|||
function knightsminimum(N, char = "N") |
|||
N < 2 && return 1, "$char" |
|||
knightdeltas = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)] |
|||
model = Model(Cbc.Optimizer) |
|||
# to simplify the constraints, embed the board of size N inside a board of size n + 4 |
|||
@variable(model, x[1:N+4, 1:N+4], Bin) |
|||
@constraint(model, x[:, 1:2] .== 0) |
|||
@constraint(model, x[1:2, :] .== 0) |
|||
@constraint(model, x[:, N+3:N+4] .== 0) |
|||
@constraint(model, x[N+3:N+4, :] .== 0) |
|||
for i in 3:N+2, j in 3:N+2 |
|||
@constraint(model, x[i, j] + sum(x[i + d[1], j + d[2]] for d in knightdeltas) >= 1) |
|||
@constraint(model, x[i, j] => {sum(x[i + d[1], j + d[2]] for d in knightdeltas) == 0}) |
|||
end |
|||
set_silent(model) |
|||
@objective(model, Min, sum(x)) |
|||
optimize!(model) |
|||
solution = round.(Int, value.(x)) |
|||
minresult = sum(solution) |
|||
return minresult, smatrix(solution[3:N+2, 3:N+2], N, char) |
|||
end |
|||
const examples = fill("", 3) |
|||
println(" Squares Queens Bishops Knights") |
|||
@time for N in 1:10 |
|||
print(lpad(N^2, 10)) |
|||
i, examples[1] = queensminimum(N) |
|||
print(lpad(i, 10)) |
|||
i, examples[2] = bishopsminimum(N) |
|||
print(lpad(i, 10)) |
|||
i, examples[3] = knightsminimum(N) |
|||
println(lpad(i, 10)) |
|||
end |
|||
println("\nExamples for N = 10:\n\nQueens:\n", examples[1], "\nBishops:\n", examples[2], |
|||
"\nKnights:\n", examples[3]) |
|||
</lang> {{out}} |
|||
<pre> |
|||
Squares Queens Bishops Knights |
|||
1 1 1 1 |
|||
4 1 2 4 |
|||
9 1 3 4 |
|||
16 3 4 4 |
|||
25 3 5 5 |
|||
36 4 6 8 |
|||
49 4 7 13 |
|||
64 5 8 14 |
|||
81 5 9 14 |
|||
100 5 10 16 |
|||
64.108607 seconds (35.53 M allocations: 1.898 GiB, 2.26% gc time, 71.05% compilation time) |
|||
Examples for N = 10: |
|||
Queens: |
|||
. . . . . . . . . . |
|||
. . Q . . . . . . . |
|||
. . . . . . . . . . |
|||
. . . . . . . . Q . |
|||
. . . . . . . . . . |
|||
. . . . Q . . . . . |
|||
. . . . . . . . . . |
|||
Q . . . . . . . . . |
|||
. . . . . . . . . . |
|||
. . . . . . Q . . . |
|||
Bishops: |
|||
. . . . . . . . . . |
|||
. . . . . B . . . . |
|||
. . . . . B . . . . |
|||
. B . . . . . . . . |
|||
. B . . . . B . . . |
|||
. . . . . . B . . . |
|||
. . B . . . B . . . |
|||
. . . . . . B . . . |
|||
. B . . . . . . . . |
|||
. . . . . . . . . . |
|||
Knights: |
|||
. . . . . . . . . . |
|||
. . N N . . . . . . |
|||
. . N N . . . N N . |
|||
. . . . . . . N N . |
|||
. . . . . . . . . . |
|||
. . . . . . . . . . |
|||
. N N . . . . . . . |
|||
. N N . . . N N . . |
|||
. . . . . . N N . . |
|||
. . . . . . . . . . |
|||
</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |