Packages
fixpoint
0.21.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/hakank/minesweeper.ex
#
# Minesweeper in Elixir.
#
# From gecode/examples/minesweeper.cc:
# """
# A specification is a square matrix of characters. Alphanumeric
# characters represent the number of mines adjacent to that field.
# Dots represent fields with an unknown number of mines adjacent to
# it (or an actual mine).
# """
#
# E.g.
# "..2.3."
# "2....."
# "..24.3"
# "1.34.."
# ".....3"
# ".3.3.."
# """
#
# Also see:
# * http://www.janko.at/Raetsel/Minesweeper/index.htm
#
# * http://en.wikipedia.org/wiki/Minesweeper_(computer_game)
#
# * Ian Stewart on Minesweeper:
# http://www.claymath.org/Popular_Lectures/Minesweeper/
#
# * Richard Kaye's Minesweeper Pages
# http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
#
# * Some Minesweeper Configurations
# http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf
#
#
# This program was created by Hakan Kjellerstrand, hakank@gmail.com
# See also my Elixir page: http://www.hakank.org/elxir/
#
## Boris Okner: modified to sync with the latest API,
## change naming and result handling.
##
defmodule CPSolver.Examples.Hakank.Minesweeper do
import Hakank.CPUtils
alias CPSolver.IntVariable
alias CPSolver.Constraint.Sum
# alias CPSolver.Constraint.Equal
# alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
alias CPSolver.Model
# alias CPSolver.Objective
# import CPSolver.Constraint.Factory
# import CPSolver.Variable.View.Factory
# Problem from Gecode/examples/minesweeper.cc problem 0
#
# Solution:
# 1 0 0 0 0 1
# 0 1 0 1 1 0
# 0 0 0 0 1 0
# 0 0 0 0 1 0
# 0 1 1 1 0 0
# 1 0 0 0 1 1
@instance_dir "data/minesweeper"
def problem(0) do
# unknown value
u = -1
[
[u, u, 2, u, 3, u],
[2, u, u, u, u, u],
[u, u, 2, 4, u, 3],
[1, u, 3, 4, u, u],
[u, u, u, u, u, 3],
[u, 3, u, 3, u, u]
]
end
#
# print_instance(p,rows,cols)
#
# Pretty print the problem instance `p`.
#
defp print_instance(p, rows, cols) do
IO.puts("Problem instance:")
for i <- 0..(rows - 1) do
for j <- 0..(cols - 1) do
v = mat_at(p, i, j)
if v >= 0 do
:io.format("~1w", [v])
else
:io.format("~1w", [~c"_"])
end
end
IO.puts("")
end
IO.puts("")
end
def read_instance(file) do
{:ok, contents} = File.read(file)
[_, _ | p] =
contents
|> String.split("\n")
|> Enum.filter(fn line -> !String.starts_with?(line, "#") end)
|> Enum.map(fn s ->
String.split(s, "", trim: true)
|> Enum.map(fn c ->
if c != "." do
String.to_integer(c)
else
-1
end
end)
end)
p
end
def run(file \\ "") do
p =
if file == "" do
problem(0)
else
read_instance(file)
end
minesweeper(p)
end
# Test all instances in data/minesweeper/minesweeper*.txt
def run2() do
# skipping = %{Path.join(@instance_dir,"minesweeper_kaye_splitter.txt") => true}
for file <- Path.wildcard(Path.join(@instance_dir, "minesweeper*.txt")) do
IO.puts("Solving file #{file}")
# if Map.has_key?(skipping, file) do
# IO.puts("Skipping this instance since it has too many solutions.\n")
# else
minesweeper(read_instance(file))
# end
end
end
# Running minesweeper_kaye_splitter.txt
# which has a huge number of solutions.
def run3() do
minesweeper(read_instance(Path.join(@instance_dir, "minesweeper_kaye_splitter.txt")))
end
@doc """
minesweeper(p)
Solves the Minesweeper instance `p`.
"""
def minesweeper(p) do
rows = length(p)
cols = length(Enum.at(p, 0))
print_instance(p, rows, cols)
x =
for i <- 0..(rows - 1) do
for j <- 0..(cols - 1) do
v = mat_at(p, i, j)
if v >= 0 do
IntVariable.new(0, name: "x[#{i},#{j}]")
else
IntVariable.new(0..1, name: "x[#{i},#{j}]")
end
end
end
constraints =
for i <- 0..(rows - 1), j <- 0..(cols - 1), v = mat_at(p, i, j), v >= 0 do
Sum.new(
v,
for a <- -1..1, b <- -1..1, (i + a) in 0..(rows - 1), (j + b) in 0..(cols - 1) do
mat_at(x, i + a, j + b)
end
)
end
model =
Model.new(
x |> List.flatten(),
constraints
)
Logger.configure(level: :info)
opts = [
search: {:first_fail, :indomain_min},
timeout: :timer.hours(1),
stop_on: {:max_solutions, 10}
]
{:ok, res} =
CPSolver.solve(
model,
opts
)
IO.inspect(res.statistics)
res.solutions
|> Enum.map(fn s -> Enum.take(s, rows * cols) |> print_matrix(rows, cols) end)
nil
end
end