N-queens minimum and knights and bishops: Difference between revisions
N-queens minimum and knights and bishops (view source)
Revision as of 07:06, 27 April 2022
, 2 years agojulia example
m (→{{header|J}}) |
(julia example) |
||
Line 456:
└──────────┘
</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}}==
| |||