# Sudoku

## 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: http://en.wikipedia.org/wiki/Soduko
6
7 # The sudoku we want to solve (0 represents that the square is empty).
8 sudoku = Matrix[
9   [0,0,0, 2,0,5, 0,0,0],
10   [0,9,0, 0,0,0, 7,3,0],
11   [0,0,2, 0,0,9, 0,6,0],
12
13   [2,0,0, 0,0,0, 4,0,9],
14   [0,0,0, 0,7,0, 0,0,0],
15   [6,0,9, 0,0,0, 0,0,1],
16
17   [0,8,0, 4,0,0, 1,0,0],
18   [0,6,3, 0,0,0, 0,8,0],
19   [0,0,0, 6,0,8, 0,0,0]]
20
21 solution = Gecode.solve do
22   # Verify that the input is of a valid size.
23   n = sudoku.row_size
24   sub_matrix_size = Math.sqrt(n).round
25   unless sudoku.square? and sub_matrix_size**2 == n
26     raise ArgumentError, 'Incorrect value matrix size.'
27   end
28   sub_count = sub_matrix_size
29
30   # Create the squares and initialize them.
31   squares_is_an int_var_matrix(n, n, 1..n)
32   sudoku.row_size.times do |i|
33     sudoku.column_size.times do |j|
34       squares[i,j].must == sudoku[i,j] unless sudoku[i,j] == 0
35     end
36   end
37
38   # Constraints.
39   n.times do |i|
40     # All rows must contain distinct numbers.
41     squares.row(i).must_be.distinct(:strength => :domain)
42     # All columns must contain distinct numbers.
43     squares.column(i).must_be.distinct(:strength => :domain)
44     # All sub-matrices must contain distinct numbers.
45     squares.minor(
46       (i % sub_count) * sub_matrix_size,
47       sub_matrix_size,
48       (i / sub_count) * sub_matrix_size,
49       sub_matrix_size).must_be.distinct(:strength => :domain)
50   end
51
52   # Branching, we use first-fail heuristic.
53   branch_on squares, :variable => :smallest_size, :value => :min
54 end.squares.values
55
56 # Output the solved sudoku in a grid.
57 puts solution.enum_slice(sudoku.row_size).map{ |slice| slice.join(' ') }.join(\$/)
```

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