1. Problem Statement (Simple Explanation):
You’re given a 9×9 Sudoku board (char[9][9]), partially filled.
You must determine if the board is valid according to Sudoku rules for the filled cells only:
Each row must contain digits 1-9 without repetition.
Each column must contain digits 1-9 without repetition.
Each of the nine 3×3 sub-boxes must contain digits 1-9 without repetition.
Notes:
Empty cells are denoted by '.' and can be ignored.
A valid board might not be solvable; you only validate current filled cells.
2. Examples:
Example 1 (Valid):
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Example 2 (Invalid):
Same as Example 1 but top-left '5' changed to '8':
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Two 8s in the top-left 3×3 sub-box → invalid.
Output: false
3. Approach – Track Seen Digits in Rows, Columns, and Boxes:
We need to check three constraints simultaneously:
For each row r, digits 1..9 appear at most once.
For each column c, digits 1..9 appear at most once.
For each 3×3 box b, digits 1..9 appear at most once.
We can use boolean arrays or sets.
Indexing 3×3 boxes:
For a cell at row r, column c:
boxIndex = (r / 3) * 3 + (c / 3)
This gives box indices 0..8:
Rows 0–2, Cols 0–2 → box 0
Rows 0–2, Cols 3–5 → box 1
...
Rows 3–5, Cols 0–2 → box 3
Etc.
Data Structures:
Use 3 boolean matrices:
rows[9][9] – rows[r][d] is true if digit d+1 seen in row r.
cols[9][9] – cols[c][d] is true if digit d+1 seen in column c.
boxes[9][9] – boxes[b][d] is true if digit d+1 seen in box b.
Where d = board[r][c] - '1' (0-based index for digits 1..9).
Algorithm (Step-by-Step):
Initialize rows, cols, boxes to all false.
Loop over all cells r = 0..8, c = 0..8:
If board[r][c] == '.', continue.
Compute:
val = board[r][c] - '1' (0 to 8)
boxIndex = (r / 3) * 3 + (c / 3)
If rows[r][val] or cols[c][val] or boxes[boxIndex][val] is already true:
Return false (duplicate digit in row / column / box).
Otherwise:
Set rows[r][val] = cols[c][val] = boxes[boxIndex][val] = true.
If we finish the loops without conflict, return true.
Pseudo-code:
Complexity:
Board has fixed size 9×9 = 81.
Time: O(1) in practice (81 operations).
Space: O(1) (3×9×9 booleans).
Asymptotically, O(N2) for N×N Sudoku, but constant for N=9.
4. Java code:
5. C code:
6. C++ code:
7. Python code:
8. JavaScript code:
Comments
Post a Comment