Packages
fixpoint
0.21.0
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/examples/queens.ex
defmodule CPSolver.Examples.Queens do
alias CPSolver.Constraint
alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
alias CPSolver.Constraint.Less
alias CPSolver.IntVariable
alias CPSolver.Model
import CPSolver.Variable.View.Factory
require Logger
@queen_symbol "\u2655"
def solve(n, solver_opts \\ []) when is_integer(n) do
{:ok, _solver} =
CPSolver.solve_async(model(n), solver_opts)
end
def model(n, symmetry_breaking_mode \\ nil) do
range = 1..n
## Queen positions
q = Enum.map(range, fn i -> IntVariable.new(range, name: "row #{i}") end)
indexed_q = Enum.with_index(q, 1)
diagonal_down = Enum.map(indexed_q, fn {var, idx} -> linear(var, 1, -idx) end)
diagonal_up = Enum.map(indexed_q, fn {var, idx} -> linear(var, 1, idx) end)
constraints =
[
Constraint.new(AllDifferent, diagonal_down),
Constraint.new(AllDifferent, diagonal_up),
Constraint.new(AllDifferent, q)
]
# constraint alldifferent(q);
# constraint alldifferent(i in 1..n)(q[i] + i);
# constraint alldifferent(i in 1..n)(q[i] - i);
## left diagonal
Model.new(
Enum.map(inside_out_order(n), fn pos -> Enum.at(q, pos - 1) end),
constraints ++ symmetry_breaking_constraints(q, symmetry_breaking_mode)
)
end
def solve_and_print(nqueens, opts \\ [timeout: 1000]) do
Logger.configure(level: :info)
timeout = Keyword.get(opts, :timeout)
{:ok, result} =
CPSolver.solve(model(nqueens, :half_symmetry),
search: {:input_order, :indomain_random},
stop_on: {:max_solutions, 1},
timeout: timeout
)
case result.solutions do
[] ->
"No solutions found within #{timeout} milliseconds"
[s | _rest] ->
print_board(inside_out_to_normal(s))
|> tap(fn _ -> check_solution(s) && Logger.notice("Solution checked!") end)
end
{:ok, result}
end
def print_board(queens) do
n = length(queens)
("\n" <>
Enum.join(
for i <- 1..n do
Enum.join(
for j <- 1..n do
if Enum.at(queens, i - 1) == j,
do: IO.ANSI.red() <> @queen_symbol,
else: IO.ANSI.light_blue() <> "."
end,
" "
)
end,
"\n"
) <> "\n")
|> IO.puts()
end
def check_solution(queens) do
n = length(queens)
queens = inside_out_to_normal(queens)
Enum.all?(0..(n - 2), fn i ->
Enum.all?((i + 1)..(n - 1), fn j ->
# queens q[i] and q[i] not on ...
## ... the same line
## ... the same left or right diagonal
(Enum.at(queens, i) != Enum.at(queens, j))
|> tap(fn res ->
!res && Logger.error("Queens #{i + 1} and #{j + 1} : same-line violation")
end) &&
(abs(Enum.at(queens, i) - Enum.at(queens, j)) != j - i)
|> tap(fn res ->
!res && Logger.error("Queens #{i + 1} and #{j + 1} : same-diagonal violation")
end)
end)
end)
end
defp symmetry_breaking_constraints([q1, q2 | _] = _vars, :half_symmetry) do
[Less.new(q1, q2)]
end
defp symmetry_breaking_constraints(_vars, _not_implemented) do
[]
end
def inside_out_order(n) do
{_sign, order} =
Enum.reduce(1..n, {1, [div(n, 2)]}, fn n, {direction_acc, acc} ->
{-direction_acc, [hd(acc) + direction_acc * n | acc]}
end)
if rem(n, 2) == 1 do
[n | tl(tl(order))]
else
tl(order)
end
|> Enum.reverse()
end
def inside_out_to_normal(queens) do
Enum.map(Enum.zip(inside_out_order(length(queens)), queens) |> Enum.sort(), fn {_, p} -> p end)
end
end