# Sudoku with Sets

## Problem

The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes contains the digits from 1 to 9. The puzzle setter provides a partially completed grid. – Wikipedia

## Code

```  1 require 'rubygems'
2 require 'gecoder'
3 require 'enumerator'
4
5 # Solves the sudoku problem using sets. The model used is a fairly direct
6 # translation of the corresponding Gecode example:
7 # http://www.gecode.org/gecode-doc-latest/sudoku-set_8cc-source.html .
8 class SudokuSet
9   include Gecode::Mixin
10
11   # Takes a 9x9 matrix of values in the initial sudoku, 0 if the square is
12   # empty.
13   def initialize(predefined_values)
14     # Verify that the input is of a valid size.
15     @size = n = predefined_values.row_size
16     block_size = Math.sqrt(n).round
17     unless predefined_values.square? and block_size**2 == n
18       raise ArgumentError, 'Incorrect value matrix size.'
19     end
20     sub_count = block_size
21
22     # Create one set per assignable number (i.e. 1..9). Each set contains the
23     # position of all squares that the number is located in. The squares are
24     # given numbers from 1 to 81. Each set therefore has an empty lower bound
25     # (since we have no guarantees where a number will end up) and 1..81 as
26     # upper bound (as it may potentially occurr in any square). We know that
27     # each assignable number must occurr 9 times in a solved sudoku, so we
28     # set the cardinality to 9..9 .
29     sets_is_an set_var_array(n, [], 1..n*n, n..n)
30     predefined_values.row_size.times do |i|
31       predefined_values.column_size.times do |j|
32         unless predefined_values[i,j].zero?
33           # We add the constraint that the square position must occurr in the
34           # set corresponding to the predefined value.
35           sets[predefined_values[i,j] - 1].must_be.superset_of [i*n + j+1]
36         end
37       end
38     end
39
40     # Build arrays containing the square positions of each row and column.
41     rows = []
42     columns = []
43     n.times do |i|
44       rows << ((i*n + 1)..(i*n + n))
45       columns << (0...n).map{ |e| e*n + 1 + i }
46     end
47
48     # Build arrays containing the square positions of each block.
49     blocks = []
50     # The square numbers of the first block.
51     first_block = (0...block_size).map do |e|
52       ((n*e+1)..(n*e+block_size)).to_a
53     end.flatten
54     block_size.times do |i|
55       block_size.times do |j|
56         blocks << first_block.map{ |e| e + (j*n*block_size)+(i*block_size) }
57       end
58     end
59
60     # All sets must be pairwise disjoint since two numbers can't be assigned to
61     # the same square.
62     n.times do |i|
63       (i + 1).upto(n - 1) do |j|
64         sets[i].must_be.disjoint_with sets[j]
65       end
66     end
67
68     # The sets must intersect in exactly one element with each row column and
69     # block. I.e. an assignable number must be assigned exactly once in each
70     # row, column and block.
71     sets.each do |set|
72       rows.each do |row|
73         set.intersection(row).size.must == 1
74       end
75       columns.each do |column|
76         set.intersection(column).size.must == 1
77       end
78       blocks.each do |block|
79         set.intersection(block).size.must == 1
80       end
81     end
82
83     # Branching.
84     branch_on sets, :variable => :none, :value => :min
85   end
86
87   # Outputs the assigned numbers in a grid.
88   def to_s
89     squares = []
90     sets.values.each_with_index do |positions, i|
91       positions.each{ |square_position| squares[square_position - 1] = i + 1 }
92     end
93     squares.enum_slice(@size).map{ |slice| slice.join(' ') }.join("\n")
94   end
95 end
96
97 predefined_squares = Matrix[
98   [0,0,0, 2,0,5, 0,0,0],
99   [0,9,0, 0,0,0, 7,3,0],
100   [0,0,2, 0,0,9, 0,6,0],
101
102   [2,0,0, 0,0,0, 4,0,9],
103   [0,0,0, 0,7,0, 0,0,0],
104   [6,0,9, 0,0,0, 0,0,1],
105
106   [0,8,0, 4,0,0, 1,0,0],
107   [0,6,3, 0,0,0, 0,8,0],
108   [0,0,0, 6,0,8, 0,0,0]]
109 puts SudokuSet.new(predefined_squares).solve!.to_s
```

## Output

```3 7 8 2 6 5 9 1 4
5 9 6 8 1 4 7 3 2
1 4 2 7 3 9 5 6 8
2 1 7 3 8 6 4 5 9
8 5 4 9 7 1 6 2 3
6 3 9 5 4 2 8 7 1
7 8 5 4 2 3 1 9 6
4 6 3 1 9 7 2 8 5
9 2 1 6 5 8 3 4 7
```

### Notes

We use a somewhat different viewpoint than when using integer variables to solve sudokus. Here we view the problem as a number of values that have to be assigned squares rather than as a number of squares that have to be assigned values. This is an example of two viewpoints can be linked using the channel constraint.