Sudoku checker

Given a sudoku board, check if it is a valid solution.

Solution

• Check each row, column and region for validity.
• Use a hash map to test each number's uniqueness

Code

def is_valid_sudoku(board)
  row_count = board[0].size
  col_count = board.size
  region_size = Math.sqrt(row_count) # or col_count

  ## Check rows
  (0...row_count).each do |i|
    return false if has_duplicate(board, i, i+1, 0, col_count)
  end

  ## Check columns
  (0...col_count).each do |j|
    return false if has_duplicate(board, 0, row_count, j, j+1)
  end

  ## Check regions
  i = 0
  while i < row_count
    j = 0
    while  j < col_count
      return false if has_duplicate(board, i, i + region_size, j, j + region_size)
      j += region_size
    end
    i += region_size
  end
end

## Check each of the elements in the described range
## First row is a[0][0]...a[0][8]
## First col is a[0][0]...a[8][0]
## First region is a[0][0]..a[2][2]
def has_duplicate(board, row_start, row_end, col_start, col_end)
  sudoku_hash = {}
  (row_start...row_end).each do |i|
    (col_start...col_end).each do |j|
      element = board[i][j]
      if element == 0 || sudoku_hash[element] == 1
        return true
      else
        sudoku_hash[element] = 1
      end
    end
  end
end

Complexity

• Time: We're visiting each element a maxof 3 times (row traversal, col traversal and region traversal)
• O(n + n + n) = O(n)
• Space: We're maintaining a hash of size n, therefore O(n)