# Minesweeper

## Problem

Minesweeper is a logic puzzle where the goal is to deduce the location of mines in a minefield. The player is given a specification where each square is either unknown, or is known to not contain a mine and have a specified number of mines adjacent to it.

## Code

1 require 'rubygems'
2 require 'gecoder'
3 require 'enumerator'
4
5 #
6 # Minesweeper in Gecode/R
7 #
8 # From gecode/examples/minesweeper.cc:
9 # """
10 # A specification is a square matrix of characters. Alphanumeric
11 # characters represent the number of mines adjacent to that field.
12 # Dots represent fields with an unknown number of mines adjacent to
13 # it (or an actual mine).
14 # """
15 #
16 # E.g.
17 #      "..2.3."
18 #      "2....."
19 #      "..24.3"
20 #      "1.34.."
21 #      ".....3"
22 #      ".3.3.."
23 # """
24 #
25 # Also see
26 #
27 # http://www.janko.at/Raetsel/Minesweeper/index.htm
28 #
29 # http://en.wikipedia.org/wiki/Minesweeper_(computer_game)
30 #
31 # Ian Stewart on Minesweeper: http://www.claymath.org/Popular_Lectures/Minesweeper/
32 #
33 # Richard Kaye's Minesweeper Pages
34 # http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
35 # Some Minesweeper Configurations
36 # http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf
37 #
38 # Compare with my other Minesweeper models:
39 #
40 # - MiniZinc: http://www.hakank.org/minizinc/minesweeper.mzn
41 #
42 # - Choco: http://www.hakank.org/choco/MineSweeper.java
43 #
44 # - JaCoP: http://www.hakank.org/JaCoP/MineSweeper.java
45 #
46 #
47 # Model created by Hakan Kjellerstrand, hakank@bonetmail.com
49 #
50 # Slight modifications made by Andreas Launila to keep the example in
51 # line with the other example models.
52 class Minesweeper
53   include Gecode::Mixin
54
55   # The provided +game+ should be a matrix encoding the problem in the
56   # following way:
57   #   -1 for the unknowns,
58   #  >= 0 for number of mines in the neighbourhood
59   def initialize(game)
60     # Boolean variables representing whether each square has a mine or
61     # not.
62     mines_is_an bool_var_matrix(game.row_size, game.column_size)
63
64     # Place the constraints.
65     game.row_size.times do |i|
66       game.column_size.times do |j|
67         # The sum of all the number of mines in the neighbourhood of this cell
68         # must agree with the problem specification.
69         if game[i,j] >= 0 then
70           neighbourhood = mines.minor([i-1,0].max..(i+1), [j-1,0].max..(j+1))
71           neighbourhood.to_a.flatten.sum.must == game[i,j]
72         end
73
74         # A square can not contain a mine if the number of neighbouring
75         # mines is known.
76         if game[i,j] >= 0 then
77           mines[i,j].must_be.false
78         end
79       end
80     end
81
82     branch_on mines, :variable => :largest_degree, :value => :max
83   end
84 end
85
86 class Array
87   # A helper for summing the contents of an array.
88   def sum
89     inject{ |sum, x| sum + x }
90   end
91 end
92
93 # Problem from Gecode/examples/minesweeper.cc  problem 2
94 X = -1 # unknowns
95 game = Matrix[
96   [1,X,X,2,X,2,X,2,X,X],
97   [X,3,2,X,X,X,4,X,X,1],
98   [X,X,X,1,3,X,X,X,4,X],
99   [3,X,1,X,X,X,3,X,X,X],
100   [X,2,1,X,1,X,X,3,X,2],
101   [X,3,X,2,X,X,2,X,1,X],
102   [2,X,X,3,2,X,X,2,X,X],
103   [X,3,X,X,X,3,2,X,X,3],
104   [X,X,3,X,3,3,X,X,X,X],
105   [X,2,X,2,X,X,X,2,2,X]
106 ]
107
108 minesweeper = Minesweeper.new(game)
109 # Find all of the solutions.
110 num_solutions = 0
111 minesweeper.each_solution do |s|
112   num_solutions += 1
113   puts "\nSolution ##{num_solutions}\n";
114   # Print the solution.
115   s.mines.values.enum_slice(s.mines.column_size).each do |row|
116     puts row.map{ |filled| filled ? "X " : ". " }.join
117   end
118 end
119
120 puts "\nNumber of solutions: #{num_solutions}"
121

## Output

Solution #1
. . . . X . . . . .
X . . X . X . X X .
X X . . . X . X . .
. . . . . . . . X .
X . . . . . X . X .
. . X . X . . . . .
. X . . . . X . . .
X . . . X . . . X .
. X . X . . X . X X
. . X . . X . . . .

Number of solutions: 1