Packages
fixpoint
0.8.33
0.22.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/coin_puzzle.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/
#
defmodule CoinsGrid do
# import CPUtils
alias CPSolver.IntVariable
alias CPSolver.Constraint.Sum
# alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
alias CPSolver.Model
alias CPSolver.Objective
import CPSolver.Variable.View.Factory
def main(n, c) do
# 31
#n = 4
# 2
# 14
#c = 2
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
|> List.flatten()
)
# 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(
x_flatten ++ [z],
constraints,
# minimize z
objective: Objective.minimize(z)
)
Logger.configure(level: :info)
opts = [
search: {:input_order, :indomain_random},
space_threads: 4,
timeout: :timer.seconds(300),
#stop_on: {:max_solutions, 2}
]
{:ok, res} =
CPSolver.solve_sync(
model,
opts
)
res.solutions
|> Enum.map(fn s ->
IO.puts("z: #{Enum.at(s, n * n)}")
Enum.take(s, n * n) |> CPUtils.print_matrix(n, n)
end)
IO.inspect(res.statistics)
IO.inspect(res.solutions)
IO.inspect(res)
end
end