Ruby sudoku solver using backtracking (interview)

Question

I was required to implement the code to a spec file I was provided in Ruby. I was rejected with the message "The quality of your code isn't sufficient for this position". Can you please tell me what can be improved in order to achieve higher quality?

game_board_spec.rb (file provided)

require './game'
require './game_board'

describe GameBoard do
  it "should correctly solve the board" do
    @game = Game.new
    # Each '0' is a blank cell
    @game.load_board 0, 0, 8, 3, 4, 2, 9, 0, 0,
                     0, 0, 9, 0, 0, 0, 7, 0, 0,
                     4, 0, 0, 0, 0, 0, 0, 0, 3,
                     0, 0, 6, 4, 7, 3, 2, 0, 0,
                     0, 3, 0, 0, 0, 0, 0, 1, 0,
                     0, 0, 2, 8, 5, 1, 6, 0, 0,
                     7, 0, 0, 0, 0, 0, 0, 0, 8,
                     0, 0, 4, 0, 0, 0, 1, 0, 0,
                     0, 0, 3, 6, 9, 7, 5, 0, 0

    @solved_board = GameBoard.new 6, 7, 8, 3, 4, 2, 9, 5, 1,
                                  3, 2, 9, 1, 8, 5, 7, 6, 4,
                                  4, 5, 1, 7, 6, 9, 8, 2, 3,
                                  5, 1, 6, 4, 7, 3, 2, 8, 9,
                                  8, 3, 7, 9, 2, 6, 4, 1, 5,
                                  9, 4, 2, 8, 5, 1, 6, 3, 7,
                                  7, 6, 5, 2, 1, 4, 3, 9, 8,
                                  2, 9, 4, 5, 3, 8, 1, 7, 6,
                                  1, 8, 3, 6, 9, 7, 5, 4, 2
    @game.solve.should == @solved_board
  end

  it "should correctly solve the board" do
    @game = Game.new
    # Each '0' is a blank cell
    @game.load_board 0, 0, 4, 0, 0, 0, 5, 0, 0,
                     0, 7, 0, 2, 0, 0, 3, 6, 0,
                     8, 0, 0, 0, 0, 1, 0, 0, 0,
                     6, 2, 9, 0, 0, 0, 0, 3, 0,
                     0, 0, 0, 0, 6, 0, 0, 0, 0,
                     0, 4, 0, 0, 0, 0, 6, 1, 8,
                     0, 0, 0, 7, 0, 0, 0, 0, 6,
                     0, 1, 3, 0, 0, 4, 0, 2, 0,
                     0, 0, 2, 0, 0, 0, 4, 0, 0
    @solved_board = GameBoard.new 2, 3, 4, 9, 7, 6, 5, 8, 1,
                                  9, 7, 1, 2, 8, 5, 3, 6, 4,
                                  8, 5, 6, 4, 3, 1, 2, 9, 7,
                                  6, 2, 9, 1, 4, 8, 7, 3, 5,
                                  1, 8, 5, 3, 6, 7, 9, 4, 2,
                                  3, 4, 7, 5, 9, 2, 6, 1, 8,
                                  4, 9, 8, 7, 2, 3, 1, 5, 6,
                                  7, 1, 3, 6, 5, 4, 8, 2, 9,
                                  5, 6, 2, 8, 1, 9, 4, 7, 3

    @game.solve.should == @solved_board
  end
end

My Solution:

game_board.rb

require 'matrix'

class GameBoard

  attr_accessor :board

  def initialize(*params)
    @board = Matrix[ *params.each_slice(9).to_a ]
  end

  def ==(game_board)
    return false unless game_board.respond_to? 'board'
    self.board == game_board.board
  end

end

game.rb

require './game_board'

class Game
  attr_reader :game_board
  attr_reader :number_set

  def initialize
    @number_set = [*(0..9)]
  end

  def load_board(*params)
    @game_board = GameBoard.new(*params)
  end

  def solve
    solve_game(game_board.board)
    game_board
  end

private
  def solve_game(board)
    if is_solved?(board)
      game_board.board = board
      return true
    end

    for i in 0..8   #traverse rows
      available_row_choices = number_set - board.row(i).to_a
      for j in 0..8 #traverse columns
        if board[i,j] == 0
          available_col_choices = number_set - board.column(j).to_a
          available_pos_choices = available_row_choices &
                                  available_col_choices &
                                  available_block_choices(board, [i,j])
          available_pos_choices.each do |choice|
            updated_board = update_board(board, [i,j], choice)
            return true if solve_game(updated_board)
          end
          return false
        end #unless
      end # for j
    end # for i
  end # solve_game

  def update_board(board, position, value)
    tmp_board = board.to_a
    tmp_board[position.first][position.last] = value
    Matrix[ *tmp_board ]
  end

  def available_block_choices(board, position)
    block = get_block(board, position)
    number_set - block.to_a.flatten.select{|e| e != 0}
  end

  def get_block(board, position)
    index_i = (position.first / 3) * 3
    index_j = (position.last  / 3) * 3
    board.minor(index_i..(index_i+2), index_j..(index_j+2))
  end

  def is_solved?(board)
    board.find_index(0).nil?
  end
end # class

Answer 1

I'm sorry to hear that you didn't get the position. I'm not sure what position you were applying for but this code is certainly as good as most code I get from candidates. I can make some comments but I'm nit picking, I would consider this code fine in production where people have jobs to do and don't have the time to make everything perfect.

• Maybe add a spec for a failing or unsolvable board (either because the board is invalid or not enough values were provided)

• I would prefer to see a constant for the board size.

• This is slightly personal, but I don't like passing [x,y] as an array and then using first and last to get the values. I would prefer to see a struct, hash or something similar.

• You continually refer to gameboard.board, I wouldn't make the internal @board public. Instead I would move some if not most logic from Game to GameBoard including get_block, available_block_choices, is_solved? and update_board. I would actually make the first two private and add available_pos_choices and empty? methods so the main code might look like:

  board.each_with_index do |val, row, col|
    next unless board.empty?(i,j)
    available_choices = board.available_choices(row, col)
    available_choices.each do |choice|
      updated_board = board.update(row, col, choice)
      return true if solve_game(updated_board)
    end
    return false
  end # each
  

• If a choice is available in a row and column (which is almost guaranteed) then there will be duplicate elements in this code below

    available_pos_choices = available_row_choices &
                            available_col_choices &
                            available_block_choices(board, [i,j])
  

• For update_board you should probably use the Matrix.clone method.

• The select here number_set - block.to_a.flatten.select{|e| e != 0} seems redundant. At least you didn't exclude zero in other places.