# Sudoku solver using backtracking, in Ruby

I wrote the below Sudoku solver, using Backtracking. Would love to hear your comments on the approach, and how I can improve readability/performance:

BLANK = '.'

def sudoku(board)
# find first '.'
for i in 0...board.length
for j in 0...board[i].length
next unless board[i][j] == BLANK

options = get_options(board, i, j)
return nil if options.empty? # validity check failed, kill branch

# put options on board individually, and recurse
proposed = board.dup
options.each do |v|
proposed[i][j] = v
return proposed if sudoku(proposed)
proposed[i][j] = BLANK
end

# none of the options worked
return nil
end
end

# base case: the whole board has numbers
board
end

def get_options(board, row, col)
# returns the list of potential options for a particular cell based
# on the game rules:
# - no repeated numbers in each row
# - no repeated numbers in a column
# - no repeated numbers in a block

options = [*"1".."9"] # all options
len = board.length

# remove the options that exist in the same row
options -= board[row].chars.uniq

# remove the options that exist in the same column
column = len.times.collect {|row| board[row][col]}
options -= column.uniq

# remove the options that exist in the same block
block = get_block(board, row, col)
options -= block.uniq

# remove blanks and return
options -= [BLANK]
end

def get_block(board, row, col)
# returns the entire block that the row/col falls in
row_start = 3 * (row / 3)
col_start = 3 * (col / 3)
block = []

for i in 0..2
for j in 0..2
block << board[row_start + i][col_start + j]
end
end
block
end

board =
["53..7....",
"6..195...",
".98....6.",
"8...6...3",
"4..8.3..1",
"7...2...6",
".6....28.",
"...419..5",
"....8..79"]

puts sudoku(board).inspect


It seems fine to me, I don't know if there is a way to solve this problem that performs better. Some minor things:

• The Ruby std-lib has a matrix class which might help. It also might help to extract the board into its own class with methods like dup, get_row, get_column, get_block, is_blank?, is_complete?

• You don't need to set proposed[i][j] = BLANK on each iteration since you are working on a duplicate of the board.

• In get_options You don't need to call uniq, it should be impossible to get into a state with multiple entries in a row, column or block. Similarly you shouldn't need to remove BLANK as there is no way to get a blank entry in the options array.

• Strangely, when I remove the proposed[i][j] = BLANK line as you suggest, I get nil, even though I'm working on a duplicate string. Any idea why? Demo here May 12, 2017 at 10:31
• The options -= [BLANK] is actually necessary, since get_block can return blanks. May 12, 2017 at 10:33
• I'm not sure why you are getting nil but options -= get_block will not contain a BLANK even if get_block does. i.e. [1,2] - [1,BLANK] == [2] May 12, 2017 at 14:54
• Good point on the BLANK business -- should've looked closer, you're right! May 12, 2017 at 17:08
• That nil business is weird indeed -- I'll investigate and post a question to SO separately. May 12, 2017 at 17:10