Sudoku solver using backtracking, in Ruby

Question

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

Answer 1

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.

• FloatingRock: 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
• FloatingRock: The options -= [BLANK] is actually necessary, since get_block can return blanks.
• Marc Rohloff: 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]
• FloatingRock: Good point on the BLANK business -- should've looked closer, you're right!
• FloatingRock: That nil business is weird indeed -- I'll investigate and post a question to SO separately.