*(Update: The Game.rb and GameTest.rb files were refactored and can be found here: Game.rb, GameTest.rb)*

Over on the XP list, a topic was brought up about types of examples one can use in a Test-Driven Development class. That led to a discussion about a Sudoku Solver.

Sudoku is a game with a 9×9 grid which one has to fill each row, column and square with 1-9 without repeats. (See Daily Sudoku for an example).

Let’s get down to business. The first case we want to solve is a simple puzzle with only one cell not filled. So we start with a class GameTest.rb which looks like:

`require 'test/unit'`

require 'Game'

class GameTest < Test::Unit::TestCase
def setup

@expected_solution = [

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

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

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

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

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

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

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

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

9,6,4, 1,7,8, 2,3,5]

end

def test_solve_simple_game

simple_game = [

0,4,5, 9,8,7, 6,2,1,

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

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

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

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

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

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

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

9,6,4, 1,7,8, 2,3,5]

game = Game.new(simple_game)

game.solve()

assert(game.is_solved?)

assert_equal(@expected_solution, game.board)

end

end

And a Game.rb of

`class Game`

attr_reader :board

def initialize(game_board)

@board = game_board

end

```
```def solve

@board[0] = 3

end

`def is_solved?`

return true

end

end

Which gets our test to pass. So let’s write another one to get us past this:

`def test_solve_simple_game2`

simple_game2 = [

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

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

8,7,0, 3,2,1, 5,4,9,

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

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

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

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

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

9,6,4, 1,7,8, 2,3,5]

game = Game.new(simple_game2)

game.solve()

assert(game.is_solved?)

assert_equal(@expected_solution, game.board)

end

Ok. So my thought process is that we loop through the cells in the game. When we find an unsolved cell (with value 0), we find out the possible values for the row, column and square that cell is in. I had tried this last night, and ended up with a whole bunch of classes, and some really messy code. I’m going to let simpleness reign as best I can this time. Let’s see if I can!

So, since I want to have squares, rows and columns, I want to build those. I’m going to comment out the above test and get the squares and such working first. The square test is easy enough:

`def test_get_square`

game = Game.new(@expected_solution)

exp_sq = [3,4,5,1,9,2,8,7,6]

assert_equal(exp_sq, game.get_square(1))

exp_sq = [9,8,7,6,5,4,3,2,1]

assert_equal(exp_sq, game.get_square(2))

exp_sq = [6,2,1,3,8,7,5,4,9]

assert_equal(exp_sq, game.get_square(3))

exp_sq = [5,2,9,4,3,1,6,8,7]

assert_equal(exp_sq, game.get_square(4))

exp_sq = [8,1,6,7,9,2,5,4,3]

assert_equal(exp_sq, game.get_square(5))

exp_sq = [4,7,3,8,5,6,1,9,2]

assert_equal(exp_sq, game.get_square(6))

exp_sq = [2,5,3,7,1,8,9,6,4]

assert_equal(exp_sq, game.get_square(7))

exp_sq = [4,6,9,2,3,5,1,7,8]

assert_equal(exp_sq, game.get_square(8))

exp_sq = [7,1,8,9,6,4,2,3,5]

assert_equal(exp_sq, game.get_square(9))

end

Ok, so let’s look at this. To get a square, we need to pick out the 9 cells from the array which make it up. In other words, square 1, the upper left-most square, would use cells [0,1,2,9,10,11,18,19,20] from the array. After thinking how I could express this as an algorithm, I realized it would just be easier to do:

`def initialize(game_board)`

@board = game_board

```
``` sq1 = [0,1,2,9,10,11,18,19,20]

sq2 = [3,4,5,12,13,14,21,22,23]

sq3 = [6,7,8,15,16,17,24,25,26]

sq4 = [27,28,29,36,37,38,45,46,47]

sq5 = [30,31,32,39,40,41,48,49,50]

sq6 = [33,34,35,42,43,44,51,52,53]

sq7 = [54,55,56,63,64,65,72,73,74]

sq8 = [57,58,59,66,67,68,75,76,77]

sq9 = [60,61,62,69,70,71,78,79,80]

@squares = [sq1,sq2,sq3,sq4,sq5,sq6,sq7,sq8,sq9]

`end`

and then implement the `get_square`

like

`def get_square(sq)`

@squares[sq-1].collect{|i|@board[i]}

end

Sweet. That’s much better than what last night’s solution was. Best of all, our test passes! Let’s move on to rows:

`def test_rows`

game_board = [

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

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

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

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

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

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

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

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

9,6,4, 1,7,8, 2,3,5]

` (0..80).each do |i|`

val = game_board[i]

game_board[i] = 0

game = Game.new(game_board)

pv = game.get_poss_row_vals(i)

assert_equal(1, pv.length)

assert_equal([val], pv)

game_board[i] = val

assert_equal(@expected_solution, game_board)

end

end

Which loops through each cell, changes the value to 0, and asserts that the value is in the possible values list for the row. We make it pass by doing:

`def get_poss_row_vals(cell_index)`

if(cell_index < 9)

cell_index = 0

else

cell_index = (cell_index / 9 * 9)

end

```
```

` row_cells = Array.new(9) {|i| cell_index+i}`

used_vals = row_cells.collect{|i| @board[i]}

return @all_vals - used_vals

end

Which returns all of the non-used values for the given row by collecting all of the current values and then doing an Array Difference from an array of 1-9. We do similar tests for columns and squares:

` def test_cols`

game_board = [

3,4,5, 9,8,7, 6,2,1, #0-8

1,9,2, 6,5,4, 3,8,7, #9-17

8,7,6, 3,2,1, 5,4,9, #18-26

```
``` 5,2,9, 8,1,6, 4,7,3, #27-35

4,3,1, 7,9,2, 8,5,6, #36-44

6,8,7, 5,4,3, 1,9,2, #45-53

2,5,3, 4,6,9, 7,1,8, #54-62

7,1,8, 2,3,5, 9,6,4, #63-71

9,6,4, 1,7,8, 2,3,5] #72-80

(0..80).each do |i|

&nbs

p; val = game_board[i]

game_board[i] = 0

game = Game.new(game_board)

pv = game.get_poss_col_vals(i)

assert_equal(1, pv.length)

assert_equal([val], pv)

game_board[i] = val

assert_equal(@expected_solution, game_board)

end

end

def test_squares

game_board = [

3,4,5, 9,8,7, 6,2,1, #0-8

1,9,2, 6,5,4, 3,8,7, #9-17

8,7,6, 3,2,1, 5,4,9, #18-26

5,2,9, 8,1,6, 4,7,3, #27-35

4,3,1, 7,9,2, 8,5,6, #36-44

6,8,7, 5,4,3, 1,9,2, #45-53

2,5,3, 4,6,9, 7,1,8, #54-62

7,1,8, 2,3,5, 9,6,4, #63-71

9,6,4, 1,7,8, 2,3,5] #72-80

` (0..80).each do |i|`

val = game_board[i]

game_board[i] = 0

game = Game.new(game_board)

pv = game.get_poss_sqr_vals(i)

assert_equal(1, pv.length)

assert_equal([val], pv)

game_board[i] = val

assert_equal(@expected_solution, game_board)

end

end

and make them pass:

`def get_poss_col_vals(cell_index)`

cell_index = cell_index - (cell_index/9*9) unless cell_index < 9

col_cells = Array.new(9){|i| cell_index + (9*i)}

used_vals = col_cells.collect{|i| @board[i]}

return @all_vals - used_vals

end

```
```

`def get_poss_sqr_vals(cell_index)`

square = nil

@squares.each {|sq| square = sq unless !sq.member?(cell_index)}

used_vals = square.collect{|i| @board[i]}

return @all_vals - used_vals

end

Ok, now, let’s tackle that puzzle test. I uncomment it (which it fails), and work on the solve method. As I mentioned above, I want to go through each cell and get the possible values for the row, column and square it is in. So I modify the solve method to look like:

`def solve`

@board.each_index do |cell_index|

if @board[cell_index] == 0

sqr_pv = get_poss_sqr_vals(cell_index)

row_pv = get_poss_row_vals(cell_index)

col_pv = get_poss_col_vals(cell_index)

pv = sqr_pv & row_pv & col_pv

if(pv.length == 1)

@board[cell_index] = pv[0]

end

end

end

end

and `is_solved`

to

`def is_solved?`

return !@board.member?(0)

end

Which let’s our test pass! Let’s try a little more complex version:

`def test_solve_complex_game`

complex_game = [

0,4,5, 9,8,7, 6,2,1,

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

8,7,0, 3,2,1, 5,4,9,

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

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

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

2,0,3, 4,6,9, 7,1,8,

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

9,6,4, 1,7,8, 2,3,5]

` game = Game.new(complex_game)`

game.solve()

assert(game.is_solved?)

assert_equal(@expected_solution, game.board)

end

which also passes. Sweet! Let’s try a harder version – the full puzzle:

`def test_real_game`

real_game = [

3,0,5, 0,8,0, 6,2,0,

0,0,0, 0,0,0, 0,0,0,

0,0,0, 3,2,1, 0,4,9,

```
``` 5,2,9, 8,0,0, 4,0,0,

0,0,0, 0,0,0, 0,0,0,

0,0,7, 0,0,3, 1,9,2,

` 2,5,0, 4,6,9, 0,0,0,`

0,0,0, 0,0,0, 0,0,0,

0,6,4, 0,7,0, 2,0,5]

game = Game.new(real_game)

game.solve()

assert(game.is_solved?)

assert_equal(@expected_solution, game.board)

end

Which doesn’t pass. Bummer. But I see something. The way I envisoned solve to work was to keep looping so that it could take into account cells that had already been solved. I wrap it in a `100.times do end`

, but I’m still only getting a partial solve. Let’s pull what we do have out into a test:

`def test_get_pv`

partial_solved_game = [

3,0,5, 0,8,0, 6,2,0,

0,0,0, 0,0,0, 0,0,0,

0,0,0, 3,2,1, 0,4,9,

```
``` 5,2,9, 8,1,0, 4,0,0,

0,0,0, 0,0,0, 0,0,0,

0,0,7, 0,0,3, 1,9,2,

` 2,5,0, 4,6,9, 0,0,0,`

0,0,0, 0,0,0, 0,0,0,

9,6,4, 1,7,8, 2,3,5]

game = Game.new(partial_solved_game)

assert_equal([1,3,4,6,7,8], game.get_poss_col_vals(35))

assert_equal([3,6,7], game.get_poss_row_vals(35))

assert_equal([3,5,6,7,8], game.get_poss_sqr_vals(35))

end

Aha! So, cell 35 (3 col, 1st row of the 3rd square in the second row) should be 3 – but only because the other two cells in the row *can’t* be 3. So I guess we need to take those into account. I add some additional asserts to the above test to pull out what I want:

` assert_equal([6,7], game.get_pv_for_row(35))`

assert_equal([1,3,4,6,7,8], game.get_pv_for_col(35))

assert_equal([3,5,6,7,8], game.get_pv_for_sqr(35))

Which is saying that I want all of the possible values for the cells row, column and square of the current cell that *aren’t* the current cell. The thought is that I can then take the possible values, do a diff between them and this list, and if only one is remaining, that cell is solved. First things first, let’s get this test to pass:

`def get_pv_for_sqr(cell_index)`

square = nil

@squares.each {|sq| square = sq unless !sq.member?(cell_index)}

pos_vals = Array.new

square.each do |i|

cell = @board[i]

if cell == 0 && i != cell_index

sqr_pv = get_poss_sqr_vals(i)

row_pv = get_poss_row_vals(i)

col_pv = get_poss_col_vals(i)

pv = sqr_pv & row_pv & col_pv

pos_vals = pos_vals | pv

end

end

return pos_vals.sort

end

```
```def get_pv_for_row(cell_index)

if(cell_index < 9)

index = 0

else

index = (cell_index / 9 * 9)

end

pos_vals = Array.new

row_cells = Array.new(9) {|i| index+i}

row_cells.each do |i|

cell = @board[i]

if cell == 0 && i != cell_index

sqr_pv = get_poss_sqr_vals(i)

row_pv = get_poss_row_vals(i)

col_pv = get_poss_col_vals(i)

pv = sqr_pv & row_pv & col_pv

pos_vals = pos_vals | pv

end** end**

return pos_vals.sort

end

**
**

`def get_pv_for_col(cell_index)`

if cell_index < 9

index = cell_index

else

index = cell_index - (cell_index/9*9)

end

pos_vals = Array.new

col_cells = Array.new(9){|i| index + (9*i)}

col_cells.each do |i|

cell = @board[i]

if cell == 0 && i != cell_index

sqr_pv = get_poss_sqr_vals(i)

row_pv = get_poss_row_vals(i)

col_pv = get_poss_col_vals(i)

pv = sqr_pv & row_pv & col_pv

pos_vals = pos_vals | pv

end

end

return pos_vals.sort

end

So, now I modify the solve method to take these into account:

`def solve`

100.times do |i|

@board.each_index do |cell_index|

if @board[cell_index] == 0

sqr_pv = get_poss_sqr_vals(cell_index)

row_pv = get_poss_row_vals(cell_index)

col_pv = get_poss_col_vals(cell_index)

pv = sqr_pv & row_pv & col_pv

if(pv.length == 1)

@board[cell_index] = pv[0]

elsif pv.length > 1

oc_sqr_pv = get_pv_for_sqr(cell_index)

oc_row_pv = get_pv_for_row(cell_index)

oc_col_pv = get_pv_for_col(cell_index)

oc_pv = oc_sqr_pv & oc_row_pv & oc_col_pv

pv = pv - oc_pv

if(pv.length == 1)

@board[cell_index] = pv[0]

end

end

end

end

end

end

Which other than being in dire need of some extract methods, let’s our tests pass. Just to see, I grab another easy puzzle of Daily Sudoku:

`def test_real_game2`

real_game = [

0,3,0,0,9,0,0,0,0,

5,0,6,0,0,1,0,0,9,

2,0,0,0,8,0,0,6,0,

0,4,3,0,0,7,0,0,0,

6,2,0,9,0,8,0,7,5,

0,0,0,1,0,0,3,2,0,

0,7,0,0,1,0,0,0,4,

9,0,0,7,0,0,1,0,2,

0,0,0,0,6,0,0,9,0]

```
``` sln = [

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

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

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

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

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

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

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

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

1,5,4,2,6,3,8,9,7]

` game = Game.new(real_game)`

game.solve()

assert(game.is_solved?)

assert_equal(sln, game.board)

end

Which also passes! Now for the moment of truth, a Very Hard Sudoku:

`def test_real_hard_game`

real_hard_game = [

1,0,0, 0,0,0, 0,0,0,

0,3,0, 6,5,0, 0,0,2,

0,0,8, 0,0,2, 9,0,0,

```
``` 0,8,0, 0,0,9, 1,6,0,

0,0,0, 1,0,7, 0,0,0,

0,7,1, 8,0,0, 0,5,0,

0,0,5, 4,0,0, 2,0,0,

9,0,0, 0,7,6, 0,8,0,

0,0,0, 0,0,0, 0,0,3]

sln = [

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

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

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

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

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

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

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

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

8,4,7,2,1,5,6,9,3]

` game = Game.new(real_hard_game)`

game.solve()

assert(game.is_solved?)

assert_equal(sln, game.board)

end

And it…Doesn’t pass! Hmm. I guess I’m going to have to do some more research to see if there’s additional logic, or if this particular puzzle requires a subjective move. But, I’m pretty happy with what I’ve gotten so far, and if I have a chance to come back to look at the harder puzzles, I’ll post it here.

We’ve done this a few times, now, always in Java. My experience has been that focusing on a full puzzle too soon is less productive that working our way out – from cells, through constraints (row / column / block), to boards. It’s too much work to get a board test to pass – too long in red – for me. And when we took a strictly inside-out approach, it went very smoothly, very quickly. So that’s my advice.

Also – do you want some help with solution strategies? You’ll need quite a few more to be able to solve the really hard puzzles.

Hi Carl,

Thanks for the comment. Surprisingly, the full puzzle test didn’t stay red for all that long once the row, column and square tests were out of the way. Although, since the hard puzzle tests don’t work, I guess at least one is red. ;)

I’d love to hear some other solution strategies. It seems close with this one, but I bet I’m missing something.

sudoku.sourceforge.net has a neat solver applet.

They also have an outline of their strategy which has gone through a few iterations.

ah .. I should have read your post when I created http://www.sudoku-solver.net .. anyway nice job..

awesome job. love sudoku, its very addicting