Packages
fixpoint
0.6.4
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/sudoku.ex
defmodule CPSolver.Examples.Sudoku do
alias CPSolver.Constraint.AllDifferent
alias CPSolver.IntVariable
require Logger
## Sudoku puzzle is a list of n rows, each one has n elements.
## If puzzle[i, j] = 0, the cell (i,j) is not filled.
##
## 4x4 example:
##
## puzzle4x4 = [[1, 0, 0, 0], [2, 3, 1, 0], [0, 0, 0, 2], [0, 2, 0, 0]]
##
## 9x9 examples:
## "4...39.2..56............6.4......9..5..1..2...9..27.3..37............8.69.8.1...." - 1 solution (hard!)
## "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4." - 1 solution
## "8..6..9.5.............2.31...7318.6.24.....73...........279.1..5...8..36..3......" - 5 solutions
##
# +-------+-------+-------+
# | 4 . . | . 3 9 | . 2 . |
# | . 5 6 | . . . | . . . |
# | . . . | . . . | 6 . 4 |
# +-------+-------+-------+
# | . . . | . . . | 9 . . |
# | 5 . . | 1 . . | 2 . . |
# | . 9 . | . 2 7 | . 3 . |
# +-------+-------+-------+
# | . 3 7 | . . . | . . . |
# | . . . | . . . | 8 . 6 |
# | 9 . 8 | . 1 . | . . . |
# +-------+-------+-------+
## puzzle9x9 =
#
## We use AllDifferent constraint here.
##
def puzzles() do
%{
hard9x9:
"..6....9....5.17..2..9..3...7..3..5..2..9..6..4..8..2...1..3..4..52.7....3....8..",
hard9x9_2:
"4...39.2..56............6.4......9..5..1..2...9..27.3..37............8.69.8.1....",
s9x9_1: "85...24..72......9..4.........1.7..23.5...9...4...........8..7..17..........36.4.",
s9x9_5: "8..6..9.5.............2.31...7318.6.24.....73...........279.1..5...8..36..3......",
s4x4: [[1, 0, 0, 0], [2, 3, 1, 0], [0, 0, 0, 2], [0, 2, 0, 0]]
}
|> Map.new(fn {name, puzzle} -> {name, normalize(puzzle)} end)
end
def solve(puzzle, solver_opts \\ []) do
puzzle
|> model()
|> CPSolver.solve(solver_opts)
end
defp normalize(puzzle) when is_binary(puzzle) do
sudoku_string_to_grid(puzzle)
end
defp normalize(puzzle) when is_list(puzzle) do
puzzle
end
def model(puzzle) when is_list(puzzle) do
dimension = length(puzzle)
## Check if puzzle is valid
sq_root = :math.sqrt(dimension)
square = floor(sq_root)
if cols = length(hd(puzzle)) != dimension || sq_root != square do
throw({:puzzle_not_valid, %{rows: dimension, cols: cols, square: square}})
end
numbers = 1..dimension
## Variables
cells =
Enum.map(0..(dimension - 1), fn i ->
Enum.map(0..(dimension - 1), fn j ->
cell = Enum.at(puzzle, i) |> Enum.at(j)
cell_name = [i + 1, j + 1]
if cell in numbers do
## Cell is filled
IntVariable.new(cell, name: cell_name)
else
IntVariable.new(numbers, name: cell_name)
end
end)
end)
# Each row has different numbers
row_constraints =
Enum.map(cells, fn row -> {AllDifferent, row} end)
# Each column has different numbers
column_constraints =
Enum.zip_with(cells, &Function.identity/1)
|> Enum.map(fn column -> {AllDifferent, column} end)
subsquare_constraints =
group_by_subsquares(cells) |> Enum.map(fn square_vars -> {AllDifferent, square_vars} end)
%{
variables: cells |> List.flatten(),
constraints: row_constraints ++ column_constraints ++ subsquare_constraints
}
end
def model(puzzle) when is_binary(puzzle) do
puzzle
|> normalize()
|> model()
end
def solve_and_print(puzzle, opts \\ []) do
Logger.configure(level: :info)
opts = Keyword.merge(default_opts(), opts)
IO.puts("Sudoku:")
IO.puts(print_grid(puzzle))
{:ok, result} =
CPSolver.solve_sync(
model(puzzle),
opts
)
case result.solutions do
[] ->
"No solutions found within #{opts[:timeout]} milliseconds"
[s | _rest] ->
print_grid(s)
|> tap(fn _ -> check_solution(s) && Logger.notice("Solution checked!") end)
end
{:ok, result}
end
def check_solution(solution) do
## We assume it's 1-dimensional list
dim = :math.sqrt(length(solution)) |> floor()
grid = Enum.chunk_every(solution, dim)
transposed = Enum.zip_with(grid, &Function.identity/1)
squares = group_by_subsquares(grid)
checker_fun = fn line -> Enum.sort(line) == Enum.to_list(1..dim) end
Enum.all?([grid, transposed, squares], fn arrangement ->
Enum.all?(arrangement, checker_fun)
end)
end
defp group_by_subsquares(cells) do
square = :math.sqrt(length(cells)) |> floor
for i <- 0..(square - 1), j <- 0..(square - 1) do
for k <- (i * square)..(i * square + square - 1),
l <- (j * square)..(j * square + square - 1) do
Enum.at(cells, k) |> Enum.at(l)
end
end
end
def print_grid(cells) when is_binary(cells) do
cells
|> sudoku_string_to_grid()
|> print_grid()
end
def print_grid(cells) when is_list(cells) do
{dim, grid} =
if is_list(hd(cells)) do
{length(cells), cells}
else
dim = :math.sqrt(length(cells)) |> floor
{dim, Enum.chunk_every(cells, dim)}
end
square_dim = :math.sqrt(dim) |> floor()
gridline =
"+" <>
String.duplicate(String.duplicate("-", 2 * square_dim + 1) <> "+", square_dim) <> "\n"
gridcol = "| "
([
"\n"
| for i <- 0..(dim - 1) do
[if(rem(i, square_dim) == 0, do: gridline, else: "")] ++
for j <- 0..(dim - 1) do
"#{if rem(j, square_dim) == 0, do: gridcol, else: ""}" <>
"#{print_cell(Enum.at(Enum.at(grid, i), j))} "
end ++ ["#{gridcol}\n"]
end
] ++ [gridline])
|> IO.puts()
end
defp print_cell(0) do
"."
end
defp print_cell(cell) do
to_string(cell)
end
defp default_opts() do
[timeout: 2_500, stop_on: {:max_solutions, 1}]
end
def sudoku_string_to_grid(sudoku_str) do
dim = :math.sqrt(String.length(sudoku_str)) |> floor()
str0 = String.replace(sudoku_str, ".", "0")
for i <- 0..(dim - 1) do
for j <- 0..(dim - 1) do
String.to_integer(String.at(str0, i * dim + j))
end
end
end
end