3
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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