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 &lt;&lt; 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.