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.