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

      # none of the options worked
      return nil

  # base case: the whole board has numbers

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]

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]

board = 

puts sudoku(board).inspect

1 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.

  • \$\begingroup\$ 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 \$\endgroup\$ May 12, 2017 at 10:31
  • \$\begingroup\$ The options -= [BLANK] is actually necessary, since get_block can return blanks. \$\endgroup\$ May 12, 2017 at 10:33
  • \$\begingroup\$ 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] \$\endgroup\$ May 12, 2017 at 14:54
  • \$\begingroup\$ Good point on the BLANK business -- should've looked closer, you're right! \$\endgroup\$ May 12, 2017 at 17:08
  • \$\begingroup\$ That nil business is weird indeed -- I'll investigate and post a question to SO separately. \$\endgroup\$ May 12, 2017 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.