# Ruby sudoku solver using backtracking (interview)

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

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

@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


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.