Valid Sudoku Lecture

Introduction

• Goal: Determine if a given 9x9 Sudoku board is valid based on certain rules.
• Date of Recording: 4th of July
• Background Noise: Potential firework noises

Problem Statement

• A 9x9 Sudoku board must be checked for validity based on three rules:
  1. Each row must contain digits 1-9 without repetition.
  2. Each column must contain digits 1-9 without repetition.
  3. Each 3x3 sub-box must contain digits 1-9 without repetition.
• Only filled cells need to be validated; empty cells (represented by '.') are ignored.
• Example contradiction for clarification:
  • A row missing '9' implies '9' must go in the empty spot.
  • A column missing '1' implies '1' must go in the empty spot.
  • Both conditions cannot be met simultaneously.
  • Considered valid since no filled cells contradict.

Algorithm Overview

• Basic Idea: Traverse the board and use hash sets to track seen numbers for rows, columns, and sub-boxes.
• **Steps:
  1. Traverse each row and ensure no duplicates using hash sets.
  2. Traverse each column and ensure no duplicates using hash sets.
  3. Traverse each 3x3 sub-box and ensure no duplicates using hash sets.

Detailed Explanation

1. Rows and Columns: Easy Check with Hash Sets

   • Create a unique hash set for each row and each column.
   • Add seen numbers to the hash set and check for duplicates.
   • Time Complexity: O(9^2) or O(N²), where N=9.

2. 3x3 Sub-boxes: Index Calculation for Hash Set Storage

   • Identify sub-box by deriving row and column index using integer division by 3.
   • Example: Cell (4, 4) belongs to sub-box indexed (1, 1).
   • Verify boundaries with edge cases (e.g., cell (8, 8) maps to sub-box (2, 2)).

3. Hash Map Construction:

   • Use a hash set for each sub-box keyed by row and column divided by 3.
   • Traverse the board, populate the hash sets, and check for duplicates.

Conclusion

• Time Complexity: O(9^2) due to single traversal through the 9x9 grid.
• Space Complexity: O(9^2) for storing seen numbers in hash sets and hash maps.
• Code Readability: Simplified using row/column division by 3 for sub-box indexing.

Code Walkthrough

• Implement using hash maps for rows, columns, and sub-boxes with key-value pairs.
• Check for duplicates at each step and update hash sets accordingly.
• Return false if duplicates detected, else true if board is valid.
• Example code implementation provided to ensure clarity and efficiency.

End of Lecture Notes on Valid Sudoku