Sudoku, the popular puzzle game known for its grid of numbers, presents a fascinating challenge not only for players but also for developers tasked with validating its correctness. In this comprehensive guide, we’ll explore how to leverage the power of Ruby to determine whether a given 9×9 Sudoku board adheres to the rules of the game. By the end, you’ll have a thorough understanding of the algorithms and techniques needed to ensure the integrity of Sudoku boards programmatically.
Understanding Sudoku Rules
Before diving into the implementation details, let’s recap the rules of Sudoku:
- Each row must contain all digits from 1 to 9 without repetition.
- Each column must contain all digits from 1 to 9 without repetition.
- Each of the nine 3×3 sub-grids (also known as “boxes”) must contain all digits from 1 to 9 without repetition.
With these rules in mind, our goal is to devise algorithms that efficiently validate whether a given Sudoku board meets these criteria.
Approach 1: Brute Force Method
The simplest approach to validating a Sudoku board is to use a brute force method. This involves iterating through each row, column, and sub-grid and checking for duplicate digits. While straightforward, this approach can be computationally expensive, especially for large Sudoku boards.
def valid_sudoku(board)
# Check rows
return false unless valid_rows?(board)
# Check columns
return false unless valid_columns?(board)
# Check sub-grids
return false unless valid_subgrids?(board)
true
end
def valid_rows?(board)
# Implementation to check rows
end
def valid_columns?(board)
# Implementation to check columns
end
def valid_subgrids?(board)
# Implementation to check sub-grids
end
Approach 2: Set-based Method
A more efficient approach is to use sets to keep track of digits encountered in each row, column, and sub-grid. By maintaining sets for each category, we can quickly determine whether any duplicates exist.
def valid_sudoku(board)
rows = Array.new(9) { Set.new }
cols = Array.new(9) { Set.new }
subgrids = Array.new(3) { Array.new(3) { Set.new } }
board.each_with_index do |row, i|
row.each_with_index do |num, j|
next if num == '.'
return false if rows[i].include?(num) || cols[j].include?(num) || subgrids[i/3][j/3].include?(num)
rows[i].add(num)
cols[j].add(num)
subgrids[i/3][j/3].add(num)
end
end
true
end
