Minesweeper

  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
 48 # See also my Gecode/R page: http://www.hakank.org/gecode_r
 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