# Survo Puzzle

## Problem

Survo puzzle is a kind of logic puzzle presented (in April 2006) and studied by Seppo Mustonen. The name of the puzzle is associated to Mustonen’s Survo system which is a general environment for statistical computing and related areas.

In a Survo puzzle the task is to fill an m * n table by integers 1,2,...,m*n so that each of these numbers appears only once and their row and column sums are equal to integers given on the bottom and the right side of the table. Often some of the integers are given readily in the table in order to guarantee uniqueness of the solution and/or for making the task easier. - Wikipedia

## Code

```  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 #
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
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
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
```

## Output

```Solution #1
3   4  10   6   8   1  =  32
12  11  18  16  17   5  =  79
9   7  15  13  14   2  =  60
=   =   =   =   =   =
24  22  43  35  39   8
Number of solutions: 1
```