Survo Puzzle

  1 require 'rubygems'
  2 require 'gecoder'
  3 require 'enumerator'
  4 
  5 # Survo Puzzle in Gecode/R
  6 #
  7 # http://en.wikipedia.org/wiki/Survo_Puzzle
  8 # """
  9 # Survo puzzle is a kind of logic puzzle presented (in April 2006) and studied 
 10 # by Seppo Mustonen. The name of the puzzle is associated to Mustonen's 
 11 # Survo system which is a general environment for statistical computing and 
 12 # related areas.
 13 # 
 14 # In a Survo puzzle the task is to fill an m * n table by integers 1,2,...,m*n so 
 15 # that each of these numbers appears only once and their row and column sums are 
 16 # equal to integers given on the bottom and the right side of the table. 
 17 # Often some of the integers are given readily in the table in order to 
 18 # guarantee uniqueness of the solution and/or for making the task easier.
 19 # """
 20 # 
 21 # See also
 22 # http://www.survo.fi/english/index.html
 23 # http://www.survo.fi/puzzles/index.html
 24 #
 25 # References:
 26 # Mustonen, S. (2006b). "On certain cross sum puzzles", http://www.survo.fi/papers/puzzles.pdf 
 27 # Mustonen, S. (2007b). "Enumeration of uniquely solvable open Survo puzzles.", http://www.survo.fi/papers/enum_survo_puzzles.pdf 
 28 # Kimmo Vehkalahti: "Some comments on magic squares and Survo puzzles", http://www.helsinki.fi/~kvehkala/Kimmo_Vehkalahti_Windsor.pdf
 29 # R code: http://koti.mbnet.fi/tuimala/tiedostot/survo.R
 30 #
 31 # Compare with my other Survo Puzzle models
 32 #
 33 # - MiniZinc: http://www.hakank.org/minizinc/survo_puzzle.mzn
 34 # - JaCoP: http://www.hakank.org/JaCoP/SurvoPuzzle.java
 35 # - Choco: http://www.hakank.org/choco/SurvoPuzzle.java
 36 #
 37 # Model created by Hakan Kjellerstrand, hakank@bonetmail.com
 38 # See also my Gecode/R page: http://www.hakank.org/gecode_r
 39 #
 40 # Slight modifications made by Andreas Launila to keep the example in
 41 # line with the other example models.
 42 class SurvoPuzzle
 43   include Gecode::Mixin
 44   
 45   # The +clues+ are given as an m*n matrix where 0 represents that the
 46   # cell has no clue. The row sums and column sums are specified by the
 47   # +rowsums+ array of length m, and the +colsums+ array of length n
 48   # respectively.
 49   def initialize(clues, rowsums, colsums)
 50     r = rowsums.length # Number of rows 
 51     c = colsums.length # Number of columns
 52 
 53     # Integer variables representing each cell in the m*n table.
 54     cells_is_an int_var_matrix(r, c, 1..r*c)
 55 
 56     # Add the constraints.
 57     # Each number must appear only once.
 58     cells.must_be.distinct
 59 
 60     # The row sums must be satisfied.
 61     cells.row_vectors.each_with_index do |row, i| 
 62       row.sum.must == rowsums[i]
 63     end
 64 
 65     # The column sums must be satisfied.
 66     cells.column_vectors.each_with_index do |column, i| 
 67       column.sum.must == colsums[i] 
 68     end
 69 
 70     # The clues must be satisfied.
 71     cells.row_size.times do |i| 
 72       cells.column_size.times do |j|
 73         cells[i,j].must == clues[i,j] if clues[i,j] > 0
 74       end
 75     end
 76 
 77     branch_on cells, :variable => :smallest_size, :value => :min
 78   end
 79 end
 80 
 81 class Vector
 82   # A helper for summing the contents of a vector.
 83   def sum
 84     inject{ |sum, element| sum + element }
 85   end
 86 end
 87 
 88 # Default problem:
 89 # Survo puzzle 126/2008 (25) #363-33148
 90 # From http://www.survo.fi/puzzles/280708.txt
 91 rowsums = [32,79,60]
 92 colsums = [24,22,43,35,39,8]
 93 clues = Matrix[
 94          [ 0, 4, 0, 0, 0, 0,32],
 95          [12, 0, 0,16,17, 0,79],
 96          [ 0, 0,15, 0, 0, 2,60],
 97         ]
 98 
 99 survo_puzzle = SurvoPuzzle.new(clues, rowsums, colsums)
100 num_solutions = 0
101 survo_puzzle.each_solution do |s| 
102   num_solutions += 1
103   puts "\nSolution ##{num_solutions}";
104   # Print the solution.
105   s.cells.values.enum_slice(s.cells.column_size).each_with_index do |row,i|
106     row.each{ |element| printf('%3d ', element) }
107     printf ' = %3d ', rowsums[i]
108     puts
109   end
110   colsums.size.times{ printf('%2s= ', '') }
111   puts 
112   colsums.each{ |element| printf('%3d ', element) }
113 end
114 
115 puts "\nNumber of solutions: #{num_solutions}"
116