Valid Sudoku

To solve this coding challenge, we need to verify the validity of a partially filled 9x9 Sudoku board based on specific rules. The rules are:
  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must similarly contain the digits 1-9 without repetition.
  3. Each of the nine 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
    4. We'll iterate over the board and use a set to keep track of the digits we have already encountered in the rows, columns, and sub-boxes. If a digit is encountered more than once in the same row, column, or sub-box, the board is invalid.

    Explanation

    Steps
  4. Initialization : We'll initialize an empty set to track the digits.
  5. Iteration : We'll iterate through each cell in the board using two nested loops.
  6. Check for Digit : If the cell is empty (denoted by '.'), we skip it.
  7. Validation :
    • Row Validation : Check if the current digit has already been seen in the current row.
    • Column Validation : Check if the current digit has already been seen in the current column.
    • Sub-box Validation : Check if the current digit has already been seen in the current 3x3 sub-box.
  8. Adding to Set : If the digit hasn't been seen in the corresponding row, column, and sub-box, add it to our set.
  9. Return Result : If we detect any duplication, return False immediately. If the loop completes without finding duplicates, return True.
    10. Pseudocode
                                                
# Function to validate a Sudoku board
function is_valid_sudoku(board):
# A set to keep track of seen digits in rows, columns, and sub-boxes
seen_digits = set()

# Iterate through each row
for row in range(9):
# Iterate through each column
for col in range(9):
# Get the value at the current cell
current_digit = board[row][col]

# If the cell is not empty
if current_digit != '.':
# Check if we've encountered this digit in the current row
if (row, current_digit) in seen_digits:
return False  # Invalid board due to repetition in row

# Check if we've encountered this digit in the current column
if (current_digit, col) in seen_digits:
return False  # Invalid board due to repetition in column

# Check if we've encountered this digit in the current 3x3 sub-box
box_index = (row // 3, col // 3)
if (box_index, current_digit) in seen_digits:
return False  # Invalid board due to repetition in sub-box

# Track the current digit in the respective row, column, and sub-box
seen_digits.add((row, current_digit))  # Add to row tracker
seen_digits.add((current_digit, col))  # Add to column tracker
seen_digits.add((box_index, current_digit))  # Add to sub-box tracker

# If no conflicts were found, the board is valid
return True

    Detailed Step-by-Step Explanation of the Pseudocode

  10. Initialization :
    • We initialize an empty set
      seen_digits
      to track the digits we encounter along with their row, column, and sub-box information. This helps us ensure no digit repeats in these units.
  11. Iteration Through the Board :
    • Using two nested loops, we traverse each row (
      row
      loop) and within each row, each column (
      col
      loop). This ensures we check each cell individually.
  12. Skip Empty Cells :
    • If the current cell contains a period (
      .
      ), it means the cell is empty, and we skip further checks for that cell.
  13. Duplicate Check in Row :
    • For each digit in a non-empty cell, we check whether this digit has already appeared in the current row by checking if the tuple
      (row, current_digit)
      is in
      seen_digits
      .
  14. Duplicate Check in Column :
    • Similarly, we check for duplicates in the column by verifying if the tuple
      (current_digit, col)
      is in
      seen_digits
      .
  15. Duplicate Check in Sub-box :
    • We compute the sub-box index using integer division (
      row // 3, col // 3
      ) and check if the tuple
      (box_index, current_digit)
      is in
      seen_digits
      .
  16. Add Digit to Set :
    • If the digit is not found in any of the three checks above, it means it’s the first occurrence of this digit in the respective row, column, and sub-box. Therefore, we add the tuples to
      seen_digits
      to track it.
  17. Validation Result :
    • If any of the checks for duplicates fails, we return
      False
      . If the loops complete without finding any duplicates, we return
      True
      , indicating the board is valid.
Using this approach ensures that we correctly validate the partially filled Sudoku board against the rules of Sudoku.