# Modelling Sudoku

The following walks through the points of the modelling introduction and applies them to the popular sudoku problem.

The tutorial will lead up to the code in the sudoku example.

## Understand the Problem

In the case of sudoku we just need to know the following:

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

This gives us some insight into what we need to express in our model.

## Select the View

A sudoku seems natural to represent as a 9×9 grid where each cell can be assigned a value in 1..9. In terms of code it’s expressed as

```@squares = int_var_matrix(9, 9, 1..9)
```

### Be Aware of Multiple Views

There are however other ways to view the problem. For instance we could instead choose to use 9 set variables, one for each assignable value. Each set would then contain a square iff the corresponding value is assigned to the square. Meaning that the first set would contain the squares to which 1 is assigned, the second set would contain the squares to which 2 is assigned and so on. The squares could be represented as number ranging from 1 to 81. This view is shown in the sudoku example with sets.

### Be Economic

We could also choose to use 81*9 boolean variables, i.e. a matrix of boolean arrays, where a matrix cell has one boolean variable for each assignable number. While valid, the view would require us to add the constraint that only one boolean variable may be true in each cell. Hence it’s less economic than a matrix of integer variables.

## Express the Constraints

We select the integer variable view. The first thing we notice is that we no longer need to worry about

The objective is to fill a 9×9 grid … contains the digits from 1 to 9.

because our choice of view already takes care of that.

We are left with the following constraints that still need to be expressed:

1. Each column must contain the digits from 1 to 9.
2. Each row must contain the digits from 1 to 9.
3. Each of the nine 3×3 boxes must contain the digits from 1 to 9.
4. The puzzle setter provides a partially completed grid.

Another way to phrase the first three constraints is that the digits in each row, column and 3×3 boxes must be distinct.

The distinct constraint is a perfect match, so all we need to do to express the first three constraints is to place a distinct constraint on each row, column and 3×3 box of our variable matrix. Expressed in code it becomes:

```9.times do |i|
# All rows must contain distinct numbers.
@squares.row(i).must_be.distinct
# All columns must contain distinct numbers.
@squares.column(i).must_be.distinct
# All 3x3 boxes must contain distinct numbers.
@squares.minor((i % 3) * 3, 3, (i / 3) * 3, 3).must_be.distinct
end
```

That leaves us with the fourth constraint. We want to constrain specific squares (i.e. integer variables) to only take a specified value, hence an integer domain constraint would seem ideal (or alternatively creating each variable individually with modified domains). In code we express it as:

```predefined_values.row_size.times do |i|
predefined_values.column_size.times do |j|
unless predefined_values[i,j].zero?
@squares[i,j].must == predefined_values[i,j]
end
end
end
```

Where `predefined_values` is a matrix with the partially completed grid ( containing 0 where nothing is assigned).

## Select Branching Strategy

We select the first fail heuristic. In code it’s expressed as

```branch_on @squares, :variable => :smallest_size, :value => :min
```

It works well because it tries to assign squares as quickly as possible, hence forcing fails earlier in the search tree.

## Tweak the Performance

There’s not an awfully lot to do for sudoku.

One implied constraint for sudoku is a constraint linking the squares and the rows. It’s not necessary, but it will make the search faster.

### Change Propagation Strengths

Using a different propagation strength for the distinct constraints is worth trying.

### Break Symmetries

Part of being a sudoku is that there must be exactly one solution, hence there are no symmetires.

## The Result

Combining the code from above with a small to_s method we get the following (without any error check or anything).

```require 'rubygems'
require 'gecoder'
require 'enumerator'

class Sudoku
include Gecode::Mixin

def initialize(predefined_values)
# Create the squares.
@squares = int_var_matrix(9, 9, 1..9)

# Distinctness constraint.
9.times do |i|
# All rows must contain distinct numbers.
@squares.row(i).must_be.distinct
# All columns must contain distinct numbers.
@squares.column(i).must_be.distinct
# All 3x3 boxes must contain distinct numbers.
@squares.minor((i % 3) * 3, 3, (i / 3) * 3, 3).must_be.distinct
end

# Place the constraints from the predefined squares on them.
predefined_values.row_size.times do |i|
predefined_values.column_size.times do |j|
unless predefined_values[i,j].zero?
@squares[i,j].must == predefined_values[i,j]
end
end
end

branch_on @squares, :variable => :smallest_size, :value => :min
end

# Display the solved sudoku in a grid.
def to_s
@squares.values.enum_slice(9).map{ |slice| slice.join(' ') }.join("\n")
end
end
```

We try it out

```given_squares = Matrix[
[0,0,0, 2,0,5, 0,0,0],
[0,9,0, 0,0,0, 7,3,0],
[0,0,2, 0,0,9, 0,6,0],

[2,0,0, 0,0,0, 4,0,9],
[0,0,0, 0,7,0, 0,0,0],
[6,0,9, 0,0,0, 0,0,1],

[0,8,0, 4,0,0, 1,0,0],
[0,6,3, 0,0,0, 0,8,0],
[0,0,0, 6,0,8, 0,0,0]]
puts Sudoku.new(given_squares).solve!.to_s
```

and get the following.

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

Success!