Packages
fixpoint
0.8.27
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/survo.ex
#
# Survo puzzle in Elixir.
#
# http://en.wikipedia.org/wiki/Survo_Puzzle
# """
# Survo puzzle is a kind of logic puzzle presented (in April 2006) and studied
# by Seppo Mustonen. The name of the puzzle is associated to Mustonen's
# Survo system which is a general environment for statistical computing and
# related areas.
# In a Survo puzzle the task is to fill an m * n table by integers 1,2,...,m*n so
# that each of these numbers appears only once and their row and column sums are
# equal to integers given on the bottom and the right side of the table.
# Often some of the integers are given readily in the table in order to
# guarantee uniqueness of the solution and/or for making the task easier.
# """
#
# See also
# http://www.survo.fi/english/index.html
# http://www.survo.fi/puzzles/index.html
#
#
# This program was created by Hakan Kjellerstrand, hakank@gmail.com
# See also my Elixir page: http://www.hakank.org/elxir/
#
defmodule CPSolver.Examples.SurvoPuzzle do
alias CPSolver.IntVariable
alias CPSolver.Constraint.Sum
alias CPSolver.Constraint.AllDifferent
alias CPSolver.Model
@doc """
mat_at(m,i,j)
Returns the value (`i`,`j`) of the 2d matrix `mat`.
##Examples##
iex> [[1,2,3],[4,5,6],[7,8,9]] |> mat_at(1,2)
6
"""
def mat_at(m, i, j) do
m |> Enum.at(i) |> Enum.at(j)
end
@doc """
transpose(m)
Returns a transposed version of `m`.
##Example##
iex> [[1,2,3],[4,5,6],[7,8,9]] |> transpose
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]
"""
def transpose(m) do
Enum.zip_with(m, &Function.identity/1)
end
def puzzle(1) do
rowsums = [30, 18, 30]
colsums = [27, 16, 10, 25]
# 0 is unknown -> to be decided
problem = [[0, 6, 0, 0], [8, 0, 0, 0], [0, 0, 3, 0]]
[rowsums, colsums, problem]
end
def main() do
[rowsums, colsums, problem] = puzzle(1)
rows = length(rowsums)
cols = length(colsums)
dom = 1..(rows * cols)
# Decision variables
x_matrix =
for i <- 0..(rows - 1) do
for j <- 0..(cols - 1) do
v = mat_at(problem, i, j)
if v > 0 do
IntVariable.new(v, name: "x[#{i},#{j}]")
else
IntVariable.new(dom, name: "x[#{i},#{j}]")
end
end
end
# Row constraints
row_constraints =
for {s, row} <- Enum.zip(rowsums, x_matrix) do
Sum.new(s, row)
end
# Column constraints
col_constraints =
for {s, row} <- Enum.zip(colsums, transpose(x_matrix)) do
Sum.new(s, row)
end
x = List.flatten(x_matrix)
constraints = [AllDifferent.new(x) | row_constraints ++ col_constraints]
model =
Model.new(
x,
constraints
)
{:ok, _result} =
CPSolver.solve_sync(model,
search: {:input_order, :indomain_random},
# stop_on: {:max_solutions, 1},
timeout: :infinity,
space_threads: 12
)
end
def check_solution(solution, row_sums, col_sums) do
table_content =
Enum.take(solution, length(row_sums) * length(col_sums))
table = Enum.chunk_every(table_content, length(col_sums))
row_sums_correct? =
table
|> Enum.zip(row_sums)
|> Enum.all?(fn {row, sum} -> sum == Enum.sum(row) end)
col_sums_correct? =
table
|> transpose()
|> Enum.zip(col_sums)
|> Enum.all?(fn {col, sum} -> sum == Enum.sum(col) end)
all_different? =
length(row_sums) * length(col_sums) == MapSet.new(table_content) |> MapSet.size()
col_sums_correct? && row_sums_correct? && all_different?
end
end