Packages
fixpoint
0.8.28
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/quasigroup_completion.ex
#
# Quasigroup Completion in Elixir.
#
# See
# Carla P. Gomes and David Shmoys:
# "Completing Quasigroups or Latin Squares: Structured Graph Coloring Problem"
#
# See also
# Ivars Peterson "Completing Latin Squares"
# http://www.maa.org/mathland/mathtrek_5_8_00.html
# """
# Using only the numbers 1, 2, 3, and 4, arrange four sets of these
# numbers into a four-by-four array so that no column or row contains
# the same two numbers. The result is known as a Latin square.
# ...
# The so-called quasigroup completion problem concerns a table that is
# correctly but only partially filled in. The question is whether the
# remaining blanks in the table can be filled in to obtain a complete
# Latin square (or a proper quasigroup multiplication table).
# """
#
#
# This program was created by Hakan Kjellerstrand, hakank@gmail.com
# See also my Elixir page: http://www.hakank.org/elxir/
#
defmodule QuasigroupCompletion do
alias CPSolver.IntVariable
# alias CPSolver.Constraint.Sum
# alias CPSolver.Constraint.Equal
# alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
alias CPSolver.Model
#
# Example from Ruben Martins and Inès Lynce
# Breaking Local Symmetries in Quasigroup Completion Problems, page 3
# The solution is unique:
# 1 3 2 5 4
# 2 5 4 1 3
# 4 1 3 2 5
# 5 4 1 3 2
# 3 2 5 4 1
#
def puzzle(1) do
# 0 are the unknowns
[[1, 0, 0, 0, 4], [0, 5, 0, 0, 0], [4, 0, 0, 2, 0], [0, 4, 0, 0, 0], [0, 0, 5, 0, 1]]
end
#
# Example from Gomes & Shmoys, page 3.
# Solution:
# 4 1 2 3
# 2 3 4 1
# 1 4 3 2
# 3 2 1 4
#
def puzzle(2) do
[[0, 1, 2, 3], [2, 0, 4, 1], [1, 4, 0, 2], [3, 0, 1, 0]]
end
# Example from Gomes & Shmoys, page 7
# Two solutions.
#
def puzzle(3) do
[[0, 1, 0, 0], [0, 0, 2, 0], [0, 3, 0, 0], [0, 0, 0, 4]]
end
#
# Example from Global Constraint Catalogue
# http://www.emn.fr/x-info/sdemasse/gccat/sec2.7.108.html
#
# 12 solutions.
#
def puzzle(4) do
[[1, 0, 0, 0], [0, 0, 0, 3], [3, 0, 0, 0], [0, 0, 0, 1]]
end
#
# Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
# (n = 10]
# Pattern #1.
# There are _many_ solutions to this problem.
#
def puzzle(5) do
[
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 2, 0, 0, 0, 0],
[1, 0, 0, 0, 2, 0, 0, 0, 0, 0],
[0, 0, 0, 2, 1, 0, 0, 0, 0, 0],
[0, 0, 2, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 2, 0],
[0, 0, 0, 0, 0, 0, 0, 2, 0, 0]
]
end
#
# Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
# (n = 10]
# Pattern #2.
# There are many solutions to this problem.
#
def puzzle(6) do
[
[0, 0, 1, 2, 3, 4, 0, 0, 0, 0],
[0, 1, 2, 3, 0, 0, 4, 0, 0, 0],
[1, 2, 3, 0, 0, 0, 0, 4, 0, 0],
[2, 3, 0, 0, 0, 0, 0, 0, 4, 0],
[3, 0, 0, 0, 0, 0, 0, 0, 0, 4],
[5, 6, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 5, 6, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 5, 6, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 5, 6, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 5, 6, 0, 0, 0, 0]
]
end
#
# Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
# (n = 10]
# Pattern #3.
# Coding:
# dark red = 1
# light blue = 2
# dark blue = 3
# light red = 4
# brown = 5
# green = 6
# pink = 7
# grey = 8
# black = 9
# yellow = 10
# There are 40944 solutions for this pattern.
#
# This takes 9.5s, about to solve and print all solutions.
#
def puzzle(7) do
[
[0, 0, 1, 5, 2, 6, 7, 8, 0, 0],
[0, 1, 5, 2, 0, 0, 6, 7, 8, 0],
[1, 5, 2, 0, 0, 0, 0, 6, 7, 8],
[5, 2, 0, 0, 0, 0, 0, 0, 6, 7],
[2, 0, 0, 0, 0, 0, 0, 0, 0, 6],
[4, 10, 0, 0, 0, 0, 0, 0, 3, 9],
[0, 4, 10, 0, 0, 0, 0, 3, 9, 0],
[0, 0, 4, 10, 0, 0, 3, 9, 0, 0],
[0, 0, 0, 4, 10, 3, 9, 0, 0, 0],
[0, 0, 0, 0, 4, 9, 0, 0, 0, 0]
]
end
#
# Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
# (n = 10]
# Pattern #4.
# dark red = 1
# light blue = 2
# dark blue = 3
# light red = 4
# Note: There are no solutions to this problem.
#
def puzzle(8) do
[
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[2, 1, 0, 0, 0, 0, 0, 0, 0, 4],
[3, 2, 1, 0, 0, 0, 0, 0, 4, 0],
[0, 3, 2, 1, 0, 0, 0, 4, 0, 0],
[0, 0, 3, 2, 1, 0, 4, 0, 0, 0],
[0, 0, 0, 3, 2, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 3, 2, 1, 0, 0, 0],
[0, 0, 0, 4, 0, 3, 2, 1, 0, 0],
[0, 0, 4, 0, 0, 0, 3, 2, 1, 0],
[0, 4, 0, 0, 0, 0, 0, 3, 2, 1]
]
end
#
# Problem from http://www.cs.cornell.edu/gomes/QUASIdemo.html
# (n = 10]
# Pattern #5
# Note: There are no solutions to this problem.
#
def puzzle(9) do
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
end
#
#
#
def main() do
# Problem 5..7 yields a huge number of solutions.
# Let's just pick the first.
1..7
|> Enum.map(fn p ->
IO.puts("Running problem #{p}")
cond do
p in 5..7 -> quasigroup_completion(puzzle(p), 1)
true -> quasigroup_completion(puzzle(p))
end
end)
end
#
# Problem5
# Generating all 40944 solutions takes a long time
#
def main2() do
quasigroup_completion(puzzle(5))
end
#
# Running problem 8 (no solution)
# Takes long time in current Fixpoint version
def main3() do
quasigroup_completion(puzzle(8))
end
#
# Running problem 9 (no solution)
# Takes long time in current Fixpoint version
def main4() do
quasigroup_completion(puzzle(9))
end
@doc """
quasigroup_completion(mat,num_sols \\ :infinity)
Solves the Quasigroup completion problem for the matrix `mat`.
`num_sols` are the required number of solutions, defaults to :infinity.
"""
def quasigroup_completion(mat, _num_sols \\ :infinity) do
n = length(mat)
dom = 1..n
#
# Decision variables
#
x =
for i <- 0..(n - 1) do
for j <- 0..(n - 1) do
v = CPUtils.mat_at(mat, i, j)
if v > 0 do
# > 0: this is a hint
IntVariable.new(v, name: "x[#{i},#{j}]")
else
# 0: unknown
IntVariable.new(dom, name: "x[#{i},#{j}]")
end
end
end
x_flatten = List.flatten(x)
#
# Constraints
#
constraints = CPUtils.latin_square(x)
model =
Model.new(
x_flatten,
constraints
)
Logger.configure(level: :info)
{:ok, result} =
CPSolver.solve_sync(model,
search: {:input_order, :indomain_random},
# search: {:first_fail, :indomain_min},
# search: {:first_fail, :indomain_random},
# search: {:input_order, :indomain_max},
stop_on: {:max_solutions, 1},
timeout: :timer.hours(8),
space_threads: 4
)
IO.inspect(result.statistics)
result.solutions
# |> Enum.map(fn s -> print_matrix(s,n,n,"~3w") end)
# IO.inspect(result.statistics)
end
end