Test-Driving a Sudoku Solver in Ruby

(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 9x9 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|
    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.