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_hakank.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 SurvoPuzzle do
# import Enum # Conflicts with CPSolver.Constraint.Factory.sum
# import CPUtils
alias CPSolver.IntVariable
alias CPSolver.Constraint.Sum
alias CPSolver.Constraint.AllDifferent
alias CPSolver.Model
def print_solution(x, rows, cols, rowsums, colsums) do
for i <- 0..(rows - 1) do
for j <- 0..(cols - 1) do
:io.format("~3w", [Enum.at(x, i * cols + j)])
end
:io.format(" = ~3w ~n", [Enum.at(rowsums, i)])
end
for j <- 0..(cols - 1) do
:io.format("~3w", [Enum.at(colsums, j)])
end
:io.format("~n~n", [])
end
#
# From http://en.wikipedia.org/wiki/Survo_Puzzle, first example
#
# Solutions should be
#
# 12 6 2 10 = 30
# 8 1 5 4 = 18
# 7 9 3 11 = 30
# 27 16 10 25
#
# I.e 12 6 2 10 8 1 5 4 7 9 3 11
#
def puzzle(1) do
rowsums = [30, 18, 30]
colsums = [27, 16, 10, 25]
# 0 is unknown -> to be decided
# 0 means unknown
problem = [[0, 6, 0, 0], [8, 0, 0, 0], [0, 0, 3, 0]]
[rowsums, colsums, problem]
end
#
# From http://en.wikipedia.org/wiki/Survo_Puzzle, second example
# difficulty 0
def puzzle(2) do
rowsums = [9, 12]
colsums = [9, 7, 5]
problem = [[0, 0, 3], [0, 6, 0]]
[rowsums, colsums, problem]
end
# http://en.wikipedia.org/wiki/Survo_Puzzle, third example
# difficulty 150 ("open puzzle", i.e. no hints}
# It's an unique solution.
# (817 propagations with Gecode/fz, and 33 failures, 88 commits}
# r = 3;
# c = 4;
# rowsums = [24,15,39];
# colsums = [21,10,18,29];
# matrix = array2d(1..r, 1..c,
# [
# 0, 0, 0, 0,
# 0, 0, 0, 0,
# 0, 0, 0, 0
# ]};
# Note: this version has no hints
def puzzle(3) do
rowsums = [24, 15, 39]
colsums = [21, 10, 18, 29]
problem = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
[rowsums, colsums, problem]
end
# same as above but with hints: difficulty 0
# (15 propagations with Gecode/fz, no failures, no commits]
# matrix = array2d(1..r, 1..c,
# [
# 7, 0, 5, 0,
# 0, 1, 0, 8,
# 0, 0, 11, 0
# ]];
def puzzle(4) do
rowsums = [24, 15, 39]
colsums = [21, 10, 18, 29]
problem = [[7, 0, 5, 0], [0, 1, 0, 8], [0, 0, 11, 0]]
[rowsums, colsums, problem]
end
# http://www.survo.fi/puzzles/280708.txt, third puzzle
# Survo puzzle 128/2008 (1700] #364-35846
#
# A B C D E F
# 1 * * * * * * 30
# 2 * * 18 * * * 86
# 3 * * * * * * 55
# 22 11 42 32 27 37
#
# Solution:
# 4 1 10 5 3 7 = 30
# 12 8 18 16 15 17 = 86
# 6 2 14 11 9 13 = 55
# 22 11 42 32 27 37
#
def puzzle(5) do
rowsums = [30, 86, 55]
colsums = [22, 11, 42, 32, 27, 37]
problem = [[0, 0, 0, 0, 0, 0], [0, 0, 18, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
[rowsums, colsums, problem]
end
#
# http://en.wikipedia.org/wiki/Survo_Puzzle, under "Swapping method"
# (open puzzle]
#
# Solution:
# 15 16 12 8 = 51
# 14 11 7 4 = 36
# 13 10 6 3 = 32
# 9 5 1 2 = 17
# 51 42 26 17
def puzzle(6) do
rowsums = [51, 36, 32, 17]
colsums = [51, 42, 26, 17]
problem = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
[rowsums, colsums, problem]
end
def main() do
for p <- 1..6 do
IO.puts("\nPuzzle ##{p}")
[rowsums, colsums, problem] = puzzle(p)
survo_puzzle(rowsums, colsums, problem)
end
end
def survo_puzzle(rowsums, colsums, problem) do
rows = length(rowsums)
cols = length(colsums)
dom = 1..(rows * cols)
# Decision variables
x =
for i <- 0..(rows - 1) do
for j <- 0..(cols - 1) do
v = CPUtils.mat_at(problem, i, j)
if v > 0 do
# > 0: this is a hing
IntVariable.new(v, name: "x[#{i},#{j}]")
else
# 0: unknown
IntVariable.new(dom, name: "x[#{i},#{j}]")
end
end
end
x_flatten = x |> List.flatten()
#
# Constraints
#
all_different_constraint = AllDifferent.new(x_flatten)
# Row constraints
row_constraints =
for {s, row} <- Enum.zip(rowsums, x) do
Sum.new(s, row)
end
# Column constraints
col_constraints =
for {s, col} <- Enum.zip(colsums, CPUtils.transpose(x)) do
Sum.new(s, col)
end
constraints = [all_different_constraint] ++ row_constraints ++ col_constraints
model =
Model.new(
x_flatten,
constraints
)
Logger.configure(level: :info)
{:ok, result} =
CPSolver.solve_sync(model,
search: {:first_fail, :indomain_min},
# stop_on: {:max_solutions, 1},
timeout: 30_000,
space_threads: 12
)
# IO.inspect(result.solutions)
# IO.inspect(Enum.map(result.solutions, fn sol -> Enum.zip(result.variables, sol) end))
IO.inspect(result.statistics)
result.solutions
|> Enum.map(fn s -> s |> Enum.take(rows * cols) end)
|> Enum.map(fn s -> print_solution(s, rows, cols, rowsums, colsums) end)
# result.statistics
end
end