Packages
fixpoint
0.8.30
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/
#
defmodule Minesweeper do
import CPUtils
alias CPSolver.IntVariable
alias CPSolver.Constraint.Sum
# alias CPSolver.Constraint.AllDifferent.FWC, as: AllDifferent
alias CPSolver.Model
# alias CPSolver.Objective
# 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
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 main(file \\ "") do
p =
if file == "" do
problem(0)
else
read_instance(file)
end
minesweeper(p)
end
# Test all instances in lib/minesweeper*.txt
def main2() do
skipping = %{"lib/minesweeper_kaye_splitter.txt" => true}
for file <- Path.wildcard("lib/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 lib/minesweeper_kaye_splitter.txt
# which has a huge number of solutions.
def main3() do
minesweeper(read_instance("lib/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 = CPUtils.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 |> List.flatten()
)
Logger.configure(level: :info)
opts = [
search: {:first_fail, :indomain_min},
space_threads: 12,
timeout: :infinity,
stop_on: {:max_solutions, 2}
]
{:ok, res} =
CPSolver.solve_sync(
model,
opts
)
IO.inspect(res.statistics)
res.solutions
|> Enum.map(fn s -> Enum.take(s, rows * cols) |> CPUtils.print_matrix(rows, cols) end)
nil
end
end