Packages
fixpoint
0.20.2
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/hakank/coins_grid.ex
#
# Coins grid problem in Elixir.
#
# Problem from
# Tony Hurlimann: "A coin puzzle - SVOR-contest 2007"
# http://www.svor.ch/competitions/competition2007/AsroContestSolution.pdf
# """
# In a quadratic grid (or a larger chessboard) with 31x31 cells, one
# should place coins in such a way that the following conditions are
# fulfilled:
# 1. In each row exactly 14 coins must be placed.
# 2. In each column exactly 14 coins must be placed.
# 3. The sum of the quadratic horizontal distance from the main
# diagonal of all cells containing a coin must be as small as possible.
# 4. In each cell at most one coin can be placed.
#
# The description says to place 14x31 = 434 coins on the chessboard
# each row containing 14 coins and each column also containing 14 coins.
# """
#
# Note: This problem is quite/very hard for (plain) CP solvers. A MIP solver solves
# the 14,31 problem in millis.
#
#
# Cf the MiniZinc model http://hakank.org/minizinc/coins_grid.mzn
#
#
# This program was created by Hakan Kjellerstrand, hakank@gmail.com
# See also my Elixir page: http://www.hakank.org/elxir/
#
## Boris Okner: modified to sync with the latest API,
## change naming and result handling.
##
defmodule CPSolver.Examples.Hakank.CoinsGrid do
alias Hakank.CPUtils
alias CPSolver.IntVariable
alias CPSolver.Constraint.Sum
# alias CPSolver.Constraint.Equal
# alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
alias CPSolver.Model
alias CPSolver.Objective
# import CPSolver.Constraint.Factory
import CPSolver.Variable.View.Factory
require Logger
def run(opts \\ []) do
run(31, 14, opts)
end
def run_7_3(opts) do
run(7, 3, opts)
end
def run(n, c, opts \\ []) do
Logger.configure(level: :info)
opts =
Keyword.merge(
default_opts()
|> Keyword.put(:solution_handler,
fn solution -> print_solution(solution, n, false)
end),
opts
)
Logger.info("Started with n = #{n}, c = #{c}")
# 7
##n =
# 31
# 3
##c =
## 14
rs = 0..(n - 1)
x =
for i <- rs do
for j <- rs do
IntVariable.new(0..1, name: "x[#{i},#{j}]")
end
end
x_flatten = List.flatten(x)
# To be minimized
z = IntVariable.new(0..(n * n * n), name: "z")
# quadratic horizontal distance
# MiniZinc: z = sum(i,j in 1..n) ( x[i,j]*(abs(i-j))*(abs(i-j)) )
sum_constraint =
Sum.new(
z,
for i <- rs, j <- rs do
mul(CPUtils.mat_at(x, i, j), abs(i - j) ** 2)
end
)
# MiniZinc: forall(i in 1..n) ( sum(j in 1..n) (x[i,j]) = c )
row_constraints =
for row <- x do
Sum.new(c, row)
end
# MiniZinc: forall(j in 1..n) ( sum(i in 1..n) (x[i,j]) = c )
col_constraints =
for col <- CPUtils.transpose(x) do
Sum.new(c, col)
end
# |> List.flatten
constraints = [sum_constraint] ++ row_constraints ++ col_constraints
# constraints = row_constraints ++ col_constraints
model =
Model.new(
[z | x_flatten],
constraints,
# minimize z
objective: Objective.minimize(z)
)
{:ok, res} =
CPSolver.solve(
model,
opts)
IO.inspect(res.statistics)
best_solution = List.last(res.solutions)
if best_solution do
print_solution(best_solution, n, true)
else
Logger.info("No solutions found")
end
end
defp print_solution(solution, n, print_matrix?) do
solution = Enum.map(solution,
fn {_name, value} ->
value
value when is_integer(value) -> value
end)
coins = hd(solution)
matrix = tl(solution) |> Enum.take(n * n)
Logger.info("coins: #{coins}")
print_matrix? &&
Enum.chunk_every(matrix, n)
|> Enum.map(fn row -> Enum.join(row, " ") end)
|> Enum.join("\n")
|> then(fn matrix_str ->
IO.puts("\nmatrix:\n" <> matrix_str <> "\n")
end)
end
defp default_opts() do
[
n: 31, c: 14,
search: {:first_fail, :indomain_max},
#search: {:input_order, :indomain_max},
# search: {:most_constrained, :indomain_max},
# search: {:dom_deg, :indomain_max},
# search: {:first_fail, :indomain_min},
# search: {:max_regret, :indomain_max},
#search: {:first_fail, :indomain_random},
space_threads: 8,
timeout: :timer.hours(1),
# stop_on: {:max_solutions, 1},
]
end
end