272. Sudoku Solver
🔗 LeetCode Problem: 37. Sudoku Solver
📊 Difficulty: Hard
🏷️ Topics: Array, Backtracking, Matrix
Problem Statement
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Example 1:
Input: board =
[["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:
[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
Constraints:
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or '.'
- It is guaranteed that the input board has only one solution.
🌟 ELI5: The Simple Idea!
Think of filling a Sudoku puzzle step by step:
You have a 9×9 grid with some numbers filled in.
You need to fill the empty cells (marked with '.').
Rules:
1. Each row must have 1-9 (no repeats)
2. Each column must have 1-9 (no repeats)
3. Each 3×3 box must have 1-9 (no repeats)
Strategy:
1. Find an empty cell
2. Try placing 1, 2, 3, ... 9
3. For each number, check if it's valid (doesn't violate rules)
4. If valid, place it and move to next empty cell
5. If stuck (no valid number), BACKTRACK - undo and try different number
6. Repeat until board is complete!
Example - Filling one cell:
Board:
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
Empty cell at (0,2):
Try 1? Check row 0: has 5,3,7 → 1 valid ✓
Check col 2: has 8 → 1 valid ✓
Check box 0: has 5,3,6,9,8 → 1 valid ✓
Place 1? Try it, move forward!
If later we get stuck:
Backtrack, remove 1, try 2, 3, ... etc.
🎨 Visual Understanding
The 9×9 Grid Structure
Grid indices (row, col):
0 1 2 3 4 5 6 7 8
0 [5] [3] [.] [.] [7] [.] [.] [.] [.]
1 [6] [.] [.] [1] [9] [5] [.] [.] [.]
2 [.] [9] [8] [.] [.] [.] [.] [6] [.]
3 [8] [.] [.] [.] [6] [.] [.] [.] [3]
4 [4] [.] [.] [8] [.] [3] [.] [.] [1]
5 [7] [.] [.] [.] [2] [.] [.] [.] [6]
6 [.] [6] [.] [.] [.] [.] [2] [8] [.]
7 [.] [.] [.] [4] [1] [9] [.] [.] [5]
8 [.] [.] [.] [.] [8] [.] [.] [7] [9]
The 9 Sub-Boxes (3×3 each)
Box numbering:
Box 0 | Box 1 | Box 2
------+-------+------
Box 3 | Box 4 | Box 5
------+-------+------
Box 6 | Box 7 | Box 8
Box 0 (top-left): Box 4 (center):
5 3 . 8 . 3
6 . . . . .
. 9 8 . 2 .
Box index calculation:
boxIndex = (row / 3) * 3 + (col / 3)
Example: cell (4,5) → box = (4/3)*3 + (5/3) = 1*3 + 1 = 4 ✓
🎯 CRITICAL CONCEPT: Box Starting Position Calculation
This is the MOST CONFUSING part of Sudoku! Let me break it down step by step:
The Grid Layout with Coordinates
The 9×9 grid is divided into 9 boxes of 3×3:
Col: 0 1 2 | 3 4 5 | 6 7 8
Row 0: [0][0][0] [1][1][1] [2][2][2] ← Box numbers in each cell
Row 1: [0][0][0] [1][1][1] [2][2][2]
Row 2: [0][0][0] [1][1][1] [2][2][2]
----+---------+---------+---------
Row 3: [3][3][3] [4][4][4] [5][5][5]
Row 4: [3][3][3] [4][4][4] [5][5][5]
Row 5: [3][3][3] [4][4][4] [5][5][5]
----+---------+---------+---------
Row 6: [6][6][6] [7][7][7] [8][8][8]
Row 7: [6][6][6] [7][7][7] [8][8][8]
Row 8: [6][6][6] [7][7][7] [8][8][8]
Notice the pattern:
Rows 0-2: Boxes 0, 1, 2
Rows 3-5: Boxes 3, 4, 5
Rows 6-8: Boxes 6, 7, 8
Understanding the Box Calculation - Step by Step
Question: Given a cell at (row, col), which 3×3 box does it belong to?
Example 1: Cell at (4, 5)
Step 1: Which BOX ROW GROUP?
Row 4 is in which group of 3?
Rows 0-2: Group 0
Rows 3-5: Group 1 ← Row 4 is here!
Rows 6-8: Group 2
Formula: row / 3 = 4 / 3 = 1 (integer division)
→ Box row group = 1
Step 2: Which BOX COLUMN GROUP?
Col 5 is in which group of 3?
Cols 0-2: Group 0
Cols 3-5: Group 1 ← Col 5 is here!
Cols 6-8: Group 2
Formula: col / 3 = 5 / 3 = 1 (integer division)
→ Box col group = 1
Step 3: What's the STARTING POSITION of this box?
Box row group 1 starts at row: 1 × 3 = 3
Box col group 1 starts at col: 1 × 3 = 3
→ Box starts at (3, 3)
The 3×3 box is:
Col: 3 4 5
Row 3: [ ][ ][ ]
Row 4: [ ][X][ ] ← Our cell (4,5)
Row 5: [ ][ ][ ]
Visual Walkthrough:
Step-by-step for cell (4, 5):
1. row / 3 = 4 / 3 = 1
"Cell is in box row group 1"
Visualize:
Group 0: rows 0,1,2
Group 1: rows 3,4,5 ← HERE!
Group 2: rows 6,7,8
2. col / 3 = 5 / 3 = 1
"Cell is in box column group 1"
Visualize:
Group 0: cols 0,1,2
Group 1: cols 3,4,5 ← HERE!
Group 2: cols 6,7,8
3. Convert group to starting position:
boxRow = 1 × 3 = 3 (group 1 starts at row 3)
boxCol = 1 × 3 = 3 (group 1 starts at col 3)
Full board visualization:
0 1 2 | 3 4 5 | 6 7 8
0 [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
1 [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
2 [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
-----------+---------+---------
3 [ ][ ][ ] [S][·][·] [ ][ ][ ] S = Starting position (3,3)
4 [ ][ ][ ] [·][X][·] [ ][ ][ ] X = Our cell (4,5)
5 [ ][ ][ ] [·][·][·] [ ][ ][ ] · = Other cells in box
-----------+---------+---------
6 [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
7 [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
8 [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
4. Loop through the 3×3 box:
for (r = 3; r < 3+3; r++) // rows 3,4,5
for (c = 3; c < 3+3; c++) // cols 3,4,5
Check board[r][c]
More Examples to Solidify Understanding
Example 2: Cell at (0, 0)
Step 1: row / 3 = 0 / 3 = 0 → Box row group 0
Step 2: col / 3 = 0 / 3 = 0 → Box col group 0
Step 3: boxRow = 0 × 3 = 0, boxCol = 0 × 3 = 0
Starting position: (0, 0)
The box:
Col: 0 1 2
Row 0: [X][ ][ ] ← Our cell
Row 1: [ ][ ][ ]
Row 2: [ ][ ][ ]
Loop: r = 0 to 2, c = 0 to 2 ✓
Example 3: Cell at (8, 7)
Step 1: row / 3 = 8 / 3 = 2 → Box row group 2
Step 2: col / 3 = 7 / 3 = 2 → Box col group 2
Step 3: boxRow = 2 × 3 = 6, boxCol = 2 × 3 = 6
Starting position: (6, 6)
The box:
Col: 6 7 8
Row 6: [ ][ ][ ]
Row 7: [ ][X][ ] ← Our cell (8,7) is in this box
Row 8: [ ][ ][ ]
Loop: r = 6 to 8, c = 6 to 8 ✓
Example 4: Cell at (1, 4)
Step 1: row / 3 = 1 / 3 = 0 → Box row group 0
Step 2: col / 3 = 4 / 3 = 1 → Box col group 1
Step 3: boxRow = 0 × 3 = 0, boxCol = 1 × 3 = 3
Starting position: (0, 3)
The box:
Col: 3 4 5
Row 0: [ ][ ][ ]
Row 1: [ ][X][ ] ← Our cell
Row 2: [ ][ ][ ]
Loop: r = 0 to 2, c = 3 to 5 ✓
Why This Formula Works - The Pattern
The KEY insight:
1. Division by 3 tells us WHICH group (0, 1, or 2)
row / 3 → which horizontal band of boxes
col / 3 → which vertical band of boxes
2. Multiply by 3 to get STARTING index
group 0 → starts at 0
group 1 → starts at 3
group 2 → starts at 6
Pattern: group × 3 = starting index
3. Then loop +3 from starting position
Starting at 0 → check 0,1,2
Starting at 3 → check 3,4,5
Starting at 6 → check 6,7,8
Visual Pattern:
Group 0: 0 × 3 = 0 → check indices 0,1,2
Group 1: 1 × 3 = 3 → check indices 3,4,5
Group 2: 2 × 3 = 6 → check indices 6,7,8
Common Confusion - Why NOT Just row/3 and col/3?
❌ WRONG: Why can't we just use row/3 and col/3 directly?
If cell is at (4, 5):
row / 3 = 1
col / 3 = 1
If we loop: for (r = 1; r < 1+3; r++)
→ r goes from 1 to 3 (checks rows 1,2,3)
But cell (4,5) is in rows 3,4,5! ✗
We'd be checking the WRONG box!
✓ CORRECT: Multiply by 3 first!
boxRow = (row / 3) × 3 = 1 × 3 = 3
boxCol = (col / 3) × 3 = 1 × 3 = 3
Loop: for (r = 3; r < 3+3; r++)
→ r goes from 3 to 5 (checks rows 3,4,5) ✓
Now checking the CORRECT box!
Memory Aid - The "Divide, Multiply, Add" Pattern
Think of it as a 3-step process:
1. DIVIDE by 3: Find which group (0, 1, or 2)
row / 3 = which box row group
col / 3 = which box col group
2. MULTIPLY by 3: Convert group to starting index
(row / 3) × 3 = starting row of box
(col / 3) × 3 = starting col of box
3. ADD 3: Loop through 3×3 box
for (r = start; r < start + 3; r++)
for (c = start; c < start + 3; c++)
Mnemonic: "Divide to find, Multiply to start, Add to finish!"
Complete Visual Example
Cell at (7, 2) - Where is its 3×3 box?
Full board:
Col: 0 1 2 | 3 4 5 | 6 7 8
Row 0: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 1: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 2: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
----+---------+---------+---------
Row 3: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 4: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
Row 5: [ ][ ][ ] [ ][ ][ ] [ ][ ][ ]
----+---------+---------+---------
Row 6: [S][·][·] [ ][ ][ ] [ ][ ][ ] ← Box starts here
Row 7: [·][·][X] [ ][ ][ ] [ ][ ][ ] ← Our cell
Row 8: [·][·][·] [ ][ ][ ] [ ][ ][ ]
Calculation:
row / 3 = 7 / 3 = 2 (group 2)
col / 3 = 2 / 3 = 0 (group 0)
boxRow = 2 × 3 = 6
boxCol = 0 × 3 = 0
Loop: r from 6 to 8, c from 0 to 2
Checks box in bottom-left corner! ✓
Constraint Checking Visual
When placing '4' at cell (0,2):
ROW CHECK (row 0):
[5][3][4][ ][ ][ ][ ][ ][ ]
↑ ↑ ↑
Check: Does row 0 already have 4?
5, 3 → No 4 found ✓
COLUMN CHECK (col 2):
[4] (0,2) ← Placing here
[ ] (1,2)
[8] (2,2)
[ ] (3,2)
[ ] (4,2)
[ ] (5,2)
[ ] (6,2)
[ ] (7,2)
[ ] (8,2)
Check: Does col 2 already have 4?
Only 8 → No 4 found ✓
BOX CHECK (box 0):
5 3 4 ← Placing here
6 . .
. 9 8
Check: Does box 0 already have 4?
5,3,6,9,8 → No 4 found ✓
All checks pass → 4 is VALID! ✓
🎨 How Tracking Works - Visual Step by Step
Complete State Tracking - Simplified Example
Simplified 4×4 Sudoku for clarity (same logic applies to 9×9):
Initial Board:
1 . | . 4
. 3 | 4 .
----+----
. 4 | 2 .
4 . | . 1
Goal: Fill all '.' cells
═══════════════════════════════════════════════════════════════
STEP 1: Find first empty cell (0,1)
═══════════════════════════════════════════════════════════════
Board state:
1 [?] | . 4
. 3 | 4 .
-----+-----
. 4 | 2 .
4 . | . 1
Position: (0,1)
Try values: 1, 2, 3, 4
Try 1:
Row 0 check: has 1 ✗ (invalid)
Try 2:
Row 0 check: no 2 ✓
Col 1 check: no 2 ✓
Box 0 check: no 2 ✓
→ Place 2! ✓
Board after placing 2:
1 [2] | . 4
. 3 | 4 .
-----+-----
. 4 | 2 .
4 . | . 1
Move to next empty cell!
═══════════════════════════════════════════════════════════════
STEP 2: Next empty cell (0,2)
═══════════════════════════════════════════════════════════════
Board state:
1 2 | [?] 4
. 3 | 4 .
----+------
. 4 | 2 .
4 . | . 1
Position: (0,2)
Try values: 1, 2, 3, 4
Try 1:
Row 0: has 1 ✗
Try 2:
Row 0: has 2 ✗
Try 3:
Row 0: no 3 ✓
Col 2: no 3 ✓
Box 1: has 4, checking 3... no 3 ✓
→ Place 3! ✓
Board after placing 3:
1 2 | [3] 4
. 3 | 4 .
----+------
. 4 | 2 .
4 . | . 1
Continue...
═══════════════════════════════════════════════════════════════
EXAMPLE OF BACKTRACKING - When Stuck
═══════════════════════════════════════════════════════════════
Suppose we reach this state:
1 2 | 3 4
2 3 | 4 1
----+----
3 4 | 2 [?]
4 1 | . 2
Position: (2,3)
Try values: 1, 2, 3, 4
Try 1:
Row 2: no 1 ✓
Col 3: has 4,1,2 → no 1... wait, check again
Col 3: 4,1,?,2 → has 1 ✗
Try 2:
Row 2: has 2 ✗
Try 3:
Row 2: has 3 ✗
Try 4:
Row 2: has 4 ✗
ALL VALUES TRIED, NONE VALID! 😱
BACKTRACK! ⬅️
Go back to previous cell (2,2)
Remove the value we placed there
Try next value
This is the essence of backtracking!
Real 9×9 Tracking - First Few Steps
Initial board (first 3 rows):
0 1 2 | 3 4 5 | 6 7 8
0 [5] [3] [.] [.] [7] [.] [.] [.] [.]
1 [6] [.] [.] [1] [9] [5] [.] [.] [.]
2 [.] [9] [8] [.] [.] [.] [.] [6] [.]
═══════════════════════════════════════════════════════════════
Cell (0,2): First empty cell
═══════════════════════════════════════════════════════════════
Try 1:
Row 0: [5,3,_,_,7,_,_,_,_] → no 1 ✓
Col 2: [_,_,8,_,_,_,_,_,_] → no 1 ✓
Box 0: [5,3,_,6,_,_,_,9,8] → no 1 ✓
Valid? Seems OK, but let's check more...
Actually, let me try 4:
Row 0: [5,3,_,_,7,_,_,_,_] → no 4 ✓
Col 2: [_,_,8,_,_,_,_,_,_] → no 4 ✓
Box 0: [5,3,_,6,_,_,_,9,8] → no 4 ✓
Valid? YES ✓
Place 4:
Board:
0 1 2 | 3 4 5 | 6 7 8
0 [5] [3] [4] [.] [7] [.] [.] [.] [.]
1 [6] [.] [.] [1] [9] [5] [.] [.] [.]
2 [.] [9] [8] [.] [.] [.] [.] [6] [.]
═══════════════════════════════════════════════════════════════
Cell (0,3): Next empty cell
═══════════════════════════════════════════════════════════════
Try 1:
Row 0: [5,3,4,_,7,_,_,_,_] → no 1 ✓
Col 3: [_,1,_,_,8,_,_,4,_] → has 1 ✗
Invalid!
Try 2:
Row 0: [5,3,4,_,7,_,_,_,_] → no 2 ✓
Col 3: [_,1,_,_,8,_,_,4,_] → no 2 ✓
Box 1: [_,7,_,1,9,5,_,_,_] → no 2 ✓
Valid? YES ✓
Place 2:
Board:
0 1 2 | 3 4 5 | 6 7 8
0 [5] [3] [4] [2] [7] [.] [.] [.] [.]
1 [6] [.] [.] [1] [9] [5] [.] [.] [.]
2 [.] [9] [8] [.] [.] [.] [.] [6] [.]
... and so on until all cells filled!
Backtracking in Action
Suppose at some point we have:
Board state with cell (5,7) being filled
Try 1: Invalid (row conflict)
Try 2: Invalid (col conflict)
Try 3: Invalid (box conflict)
Try 4: Invalid (row conflict)
Try 5: Invalid (col conflict)
Try 6: Invalid (box conflict)
Try 7: Invalid (row conflict)
Try 8: Invalid (col conflict)
Try 9: Invalid (box conflict)
ALL 9 VALUES FAILED! 😱
BACKTRACK STEPS:
1. Mark cell (5,7) as empty again: board[5][7] = '.'
2. Return false to caller
3. Caller is working on cell (5,6)
4. Caller tries next value at (5,6)
5. If all values at (5,6) fail, backtrack further!
Backtracking chain:
Cell (5,7) fails → Backtrack to (5,6)
Cell (5,6) exhausted → Backtrack to (5,5)
Cell (5,5) tries next value → Move forward again
Keep backtracking until find valid path!
Visual Flow Chart
┌─────────────────────────────────────────┐
│ Start: Find next empty cell │
└──────────────┬──────────────────────────┘
│
↓
┌──────────────────────────────────────────┐
│ Found empty cell? │
├──────────────┬───────────────────────────┤
│ NO │ YES │
│ → SOLVED! ✓ │ → Try values 1-9 │
└──────────────┴───────────────────────────┘
│
↓
┌──────────────────────────────┐
│ For value = 1 to 9: │
└──────────────┬───────────────┘
│
↓
┌──────────────────────────────┐
│ Is value valid? │
│ (Check row, col, box) │
├──────────────┬───────────────┤
│ NO │ YES │
│ → Try next │ → Place value │
└──────────────┴───────┬───────┘
│
↓
┌──────────────────┐
│ Recurse to next │
│ empty cell │
├─────────┬────────┤
│ Success │ Failed │
│ → Done! │ → Undo │
└─────────┴────┬───┘
│
↓
┌──────────────┐
│ BACKTRACK: │
│ Remove value │
│ Try next │
└──────────────┘
🎨 Understanding Box Calculation - The Tricky Part!
Why Box Calculation is Confusing
The formula: boxRow = (row / 3) * 3
What does this even mean? 🤔
Let's break it down step by step!
Visual Understanding - The 9 Boxes
The 9×9 Sudoku board is divided into 9 boxes (3×3 each):
Columns: 0 1 2 | 3 4 5 | 6 7 8
Rows:
0 ┌────────┬────────┬────────┐
1 │ Box 0 │ Box 1 │ Box 2 │
2 ├────────┼────────┼────────┤
3 │ Box 3 │ Box 4 │ Box 5 │
4 ├────────┼────────┼────────┤
5 │ Box 6 │ Box 7 │ Box 8 │
6 └────────┴────────┴────────┘
7
8
Box boundaries:
Box 0: rows [0,1,2], cols [0,1,2]
Box 1: rows [0,1,2], cols [3,4,5]
Box 2: rows [0,1,2], cols [6,7,8]
Box 3: rows [3,4,5], cols [0,1,2]
Box 4: rows [3,4,5], cols [3,4,5] ← Center box
Box 5: rows [3,4,5], cols [6,7,8]
Box 6: rows [6,7,8], cols [0,1,2]
Box 7: rows [6,7,8], cols [3,4,5]
Box 8: rows [6,7,8], cols [6,7,8]
Step-by-Step: Finding Box Start
GOAL: Given any cell (row, col), find the TOP-LEFT corner of its box
Example 1: Cell (4, 5) - Which box? Where does box start?
Step 1: Which BOX ROW GROUP? (0-2, 3-5, or 6-8?)
row = 4
row / 3 = 4 / 3 = 1 (integer division)
Meaning: Row 4 is in BOX ROW GROUP 1
Box row groups:
Group 0: rows 0,1,2 (rows 0-2)
Group 1: rows 3,4,5 (rows 3-5) ← Row 4 is here!
Group 2: rows 6,7,8 (rows 6-8)
Step 2: Where does BOX ROW GROUP 1 START?
Group 1 starts at row: 1 × 3 = 3
Why multiply by 3?
Group 0 starts at: 0 × 3 = 0 ✓
Group 1 starts at: 1 × 3 = 3 ✓
Group 2 starts at: 2 × 3 = 6 ✓
So: boxRow = (4 / 3) × 3 = 1 × 3 = 3
Step 3: Which BOX COLUMN GROUP? (0-2, 3-5, or 6-8?)
col = 5
col / 3 = 5 / 3 = 1 (integer division)
Meaning: Col 5 is in BOX COL GROUP 1
Box col groups:
Group 0: cols 0,1,2 (cols 0-2)
Group 1: cols 3,4,5 (cols 3-5) ← Col 5 is here!
Group 2: cols 6,7,8 (cols 6-8)
Step 4: Where does BOX COL GROUP 1 START?
Group 1 starts at col: 1 × 3 = 3
So: boxCol = (5 / 3) × 3 = 1 × 3 = 3
RESULT:
Cell (4, 5) belongs to box starting at (3, 3)
This is Box 4 (the center box)!
Visual:
0 1 2 | 3 4 5 | 6 7 8
0 . . . | . . . | . . .
1 . . . | . . . | . . .
2 . . . | . . . | . . .
--------+---------+--------
3 . . . |⬆️ . . | . . . ← boxRow = 3
4 . . . | . X . | . . . ← Cell (4,5)
5 . . . | . . . | . . .
--------+---------+--------
6 . . . | . . . | . . .
⬆️
boxCol = 3
More Examples with Visuals
Example 2: Cell (0, 0) - Top-left corner
Step 1: row / 3 = 0 / 3 = 0
Step 2: boxRow = 0 × 3 = 0
Step 3: col / 3 = 0 / 3 = 0
Step 4: boxCol = 0 × 3 = 0
Box starts at: (0, 0) ← Top-left of Box 0 ✓
0 1 2 | 3 4 5 | 6 7 8
0 ⬆️ . . | . . . | . . .
1 . . . | . . . | . . .
2 . . . | . . . | . . .
─────────────────────────────────────────────────
Example 3: Cell (8, 8) - Bottom-right corner
Step 1: row / 3 = 8 / 3 = 2
Step 2: boxRow = 2 × 3 = 6
Step 3: col / 3 = 8 / 3 = 2
Step 4: boxCol = 2 × 3 = 6
Box starts at: (6, 6) ← Top-left of Box 8 ✓
0 1 2 | 3 4 5 | 6 7 8
6 . . . | . . . |⬆️ . .
7 . . . | . . . | . . .
8 . . . | . . . | . . X ← Cell (8,8)
─────────────────────────────────────────────────
Example 4: Cell (3, 7) - Middle-right area
Step 1: row / 3 = 3 / 3 = 1
Step 2: boxRow = 1 × 3 = 3
Step 3: col / 3 = 7 / 3 = 2
Step 4: boxCol = 2 × 3 = 6
Box starts at: (3, 6) ← Top-left of Box 5 ✓
0 1 2 | 3 4 5 | 6 7 8
3 . . . | . . . |⬆️ X . ← Cell (3,7)
4 . . . | . . . | . . .
5 . . . | . . . | . . .
The Pattern - All Possible Starting Positions
There are only 9 possible box starting positions:
Box Row Groups × Box Col Groups = 3 × 3 = 9 boxes
┌─────────┬─────────────────────────────────┐
│ Box │ Starts at (boxRow, boxCol) │
├─────────┼─────────────────────────────────┤
│ Box 0 │ (0, 0) - top-left │
│ Box 1 │ (0, 3) - top-center │
│ Box 2 │ (0, 6) - top-right │
│ Box 3 │ (3, 0) - middle-left │
│ Box 4 │ (3, 3) - CENTER │
│ Box 5 │ (3, 6) - middle-right │
│ Box 6 │ (6, 0) - bottom-left │
│ Box 7 │ (6, 3) - bottom-center │
│ Box 8 │ (6, 6) - bottom-right │
└─────────┴─────────────────────────────────┘
Notice the pattern:
Row starts: 0, 0, 0, 3, 3, 3, 6, 6, 6
Col starts: 0, 3, 6, 0, 3, 6, 0, 3, 6
Always multiples of 3!
How the Loop Works
Once we have box starting position (boxRow, boxCol):
for (int r = boxRow; r < boxRow + 3; r++) {
for (int c = boxCol; c < boxCol + 3; c++) {
// Check board[r][c]
}
}
This checks ALL 9 cells in the 3×3 box!
Example: Box starting at (3, 3)
r goes from 3 to 5 (3, 4, 5)
c goes from 3 to 5 (3, 4, 5)
Checks cells:
(3,3) (3,4) (3,5)
(4,3) (4,4) (4,5)
(5,3) (5,4) (5,5)
All 9 cells in Box 4! ✓
Visual:
0 1 2 | 3 4 5 | 6 7 8
3 . . . | X X X | . . . ← r=3
4 . . . | X X X | . . . ← r=4
5 . . . | X X X | . . . ← r=5
↑ ↑ ↑
c=3 c=4 c=5
Complete Mental Model
Think of it as:
"Which 3×3 box am I in?" → Find starting corner → Check all 9 cells
Division by 3:
0,1,2 → 0 (group 0)
3,4,5 → 1 (group 1)
6,7,8 → 2 (group 2)
Multiply by 3:
Group 0 → starts at 0
Group 1 → starts at 3
Group 2 → starts at 6
Formula compactly expresses:
"Find which group (0,1,2), then find where that group starts (0,3,6)"
(row / 3) * 3 = rowGroup × 3 = rowGroupStart
Alternative Way to Think About It
Another way to understand the formula:
boxRow = (row / 3) * 3
Can be rewritten as:
boxRow = row - (row % 3)
Examples:
row=0: 0 - (0%3) = 0 - 0 = 0 ✓
row=1: 1 - (1%3) = 1 - 1 = 0 ✓
row=2: 2 - (2%3) = 2 - 2 = 0 ✓
row=3: 3 - (3%3) = 3 - 0 = 3 ✓
row=4: 4 - (4%3) = 4 - 1 = 3 ✓
row=5: 5 - (5%3) = 5 - 2 = 3 ✓
row=6: 6 - (6%3) = 6 - 0 = 6 ✓
row=7: 7 - (7%3) = 7 - 1 = 6 ✓
row=8: 8 - (8%3) = 8 - 2 = 6 ✓
This "rounds down to nearest multiple of 3"
Which gives us the box starting position!
🎯 Approach: Backtracking ⭐⭐⭐
The Only Solution
Algorithm:
1. Find next empty cell (marked with '.')
2. If no empty cell → Solved! Return true
3. For each digit 1-9:
a. Check if digit is valid (row, col, box)
b. If valid:
- Place digit
- Recursively solve rest
- If solved → return true
- Else → remove digit (backtrack)
4. If all digits 1-9 fail → return false
Implementation
/**
* Backtracking solution for Sudoku
* Time: O(9^(n×n)) worst case, but pruning makes it much faster
* Space: O(n×n) - Recursion depth
*/
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
// Find next empty cell
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
// Try digits 1-9
for (char digit = '1'; digit <= '9'; digit++) {
if (isValid(board, row, col, digit)) {
// Place digit
board[row][col] = digit;
// Recursively solve rest
if (solve(board)) {
return true; // Solved!
}
// Backtrack - remove digit
board[row][col] = '.';
}
}
// All digits 1-9 failed
return false;
}
}
}
// No empty cell found - solved!
return true;
}
private boolean isValid(char[][] board, int row, int col, char digit) {
// Check row
for (int c = 0; c < 9; c++) {
if (board[row][c] == digit) {
return false;
}
}
// Check column
for (int r = 0; r < 9; r++) {
if (board[r][col] == digit) {
return false;
}
}
// Check 3×3 box
int boxRow = (row / 3) * 3;
int boxCol = (col / 3) * 3;
for (int r = boxRow; r < boxRow + 3; r++) {
for (int c = boxCol; c < boxCol + 3; c++) {
if (board[r][c] == digit) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
Solution sol = new Solution();
char[][] board = {
{'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'}
};
sol.solveSudoku(board);
// Print solved board
for (char[] row : board) {
System.out.println(Arrays.toString(row));
}
}
}
⏰ Time: O(9^(n×n)) worst case, but typically much faster with pruning
💾 Space: O(n×n) - Recursion depth (number of empty cells)
🔄 Is Backtracking the Only Way?
Quick Answer: Backtracking is THE Standard Solution
For Sudoku Solver:
✓ Backtracking: Standard, expected, works for all cases
✓ Constraint Propagation: Advanced optimization
✗ Brute Force: Too slow (9^81 possibilities!)
✗ Dynamic Programming: Not applicable
Bottom Line: Backtracking is the standard solution!
Why Other Approaches Don't Apply
Brute Force (Try All Combinations):
❌ COMPLETELY IMPRACTICAL
For 9×9 Sudoku with ~50 empty cells:
9^50 = 5 × 10^47 combinations!
Even at 1 billion checks per second:
Would take 10^30 years! 🤯
Universe age: ~10^10 years
Backtracking prunes early → Practical!
Dynamic Programming:
❌ NOT APPLICABLE
Why DP doesn't work:
1. No optimal substructure
2. No overlapping subproblems
3. Constraints are global (entire board)
4. Each state depends on ALL previous placements
This is a CONSTRAINT SATISFACTION problem,
not an OPTIMIZATION problem.
Advanced: Constraint Propagation:
✓ OPTIMIZATION (Not replacement!)
Techniques:
- Naked Singles: If cell has only one valid digit → place it
- Hidden Singles: If digit has only one valid cell in row/col/box → place it
- Pointing Pairs: Advanced eliminations
Used in combination with backtracking:
1. Apply constraint propagation first
2. Reduces search space
3. Then use backtracking for remaining cells
Still uses backtracking at core!
Mentioned only for completeness - not expected in interviews!
What Interviewers Expect
Standard Question:
Interviewer: "Solve this Sudoku"
Expected: Backtracking with validation
Follow-up Questions:
1. "How do you validate?"
Answer: "Check row, column, and 3×3 box for duplicate"
2. "Can you optimize?"
Answer: "Yes - instead of finding empty cells during recursion,
precompute list of empty cells. Saves time."
3. "What's the time complexity?"
Answer: "Worst case O(9^m) where m = empty cells.
But pruning makes it much faster in practice."
4. "Is there a better approach?"
Answer: "For interviews, backtracking is standard.
Advanced solvers use constraint propagation,
but that's beyond interview scope."
Interview Strategy
STEP 1: Recognize it's backtracking
"This is a constraint satisfaction problem.
I'll use backtracking to try values and backtrack when stuck."
STEP 2: Explain validation
"For each empty cell, I'll try digits 1-9.
For each digit, I'll validate:
- Row doesn't have it
- Column doesn't have it
- 3×3 box doesn't have it"
STEP 3: Explain backtracking
"If valid, place digit and recurse.
If recursion succeeds, we're done.
If it fails, remove digit and try next."
STEP 4: Code it up
- solve() function with backtracking
- isValid() function for constraint checking
⚠️ Common Mistakes
Mistake 1: Not backtracking (not removing digit)
// ❌ WRONG - Digit stays placed even when path fails!
if (isValid(board, row, col, digit)) {
board[row][col] = digit;
if (solve(board)) return true;
// Forgot to remove!
}
// ✓ CORRECT - Remove digit after failed attempt
if (isValid(board, row, col, digit)) {
board[row][col] = digit;
if (solve(board)) return true;
board[row][col] = '.'; // Backtrack!
}
Mistake 2: Wrong box calculation
// ❌ WRONG - Incorrect box boundaries
int boxRow = row / 3;
int boxCol = col / 3;
for (int r = boxRow; r < boxRow + 3; r++) {
// This checks wrong cells!
}
// ✓ CORRECT - Multiply by 3 to get starting position
int boxRow = (row / 3) * 3;
int boxCol = (col / 3) * 3;
for (int r = boxRow; r < boxRow + 3; r++) {
for (int c = boxCol; c < boxCol + 3; c++) {
// Now checking correct 3×3 box
}
}
Mistake 3: Modifying board in isValid
// ❌ WRONG - Validation should not modify board!
private boolean isValid(char[][] board, int row, int col, char digit) {
board[row][col] = digit; // Modifying!
// Check...
board[row][col] = '.';
return valid;
}
// ✓ CORRECT - Only check, don't modify
private boolean isValid(char[][] board, int row, int col, char digit) {
// Check row, col, box
// Don't modify board!
return valid;
}
Mistake 4: Not returning true when solved
// ❌ WRONG - Keeps searching even after solution found!
if (solve(board)) {
// Continue to next iteration!
}
// ✓ CORRECT - Return immediately when solved
if (solve(board)) {
return true; // Solved! Stop searching!
}
Mistake 5: Checking board[row][col] in validation
// ❌ WRONG - Checks cell being filled!
private boolean isValid(char[][] board, int row, int col, char digit) {
for (int c = 0; c < 9; c++) {
if (board[row][c] == digit) { // Checks (row, col) too!
return false;
}
}
}
// ✓ CORRECT - Skip the cell being filled
private boolean isValid(char[][] board, int row, int col, char digit) {
for (int c = 0; c < 9; c++) {
if (c != col && board[row][c] == digit) { // Skip (row, col)
return false;
}
}
}
// OR: Check before placing (like in our main solution)
🎯 Pattern Recognition
Problem Type: Constraint Satisfaction
Core Pattern: Backtracking with Validation
When to Apply:
✓ Must satisfy multiple constraints
✓ Need to fill cells/slots with values
✓ Constraints are interdependent
✓ Guaranteed unique solution
Recognition Keywords:
- "solve a puzzle"
- "satisfy rules/constraints"
- "valid placement"
- "fill the grid"
Similar Problems:
- N-Queens (LC 51) - Place queens without conflicts
- Valid Sudoku (LC 36) - Just validate, don't solve
- Sudoku Solver variants - Different grid sizes
Key Components:
┌────────────────────────────────────────────┐
│ Backtracking: Try values, undo if fail │
│ Validation: Check row, col, box │
│ Base case: No empty cells → solved! │
│ Try all: Loop through 1-9 │
│ Prune: Skip invalid early │
│ Time: O(9^m), Space: O(m) (m=empty cells) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is backtracking with constraint checking"
Step 2: "Find empty cell, try 1-9, validate each"
Step 3: "If valid, place and recurse. If stuck, backtrack"
Key Points to Mention:
- Three constraints: row, column, 3×3 box
- Try each digit 1-9 for empty cell
- Validate before placing
- Backtrack if path fails
- Modify board in-place
Walk Through:
"For this board:
Find first empty at (0,2)
Try 1: Check row 0, col 2, box 0 → Valid? Try it
Recurse to next empty...
If later fails → Come back, remove 1
Try 2: Check constraints → Valid? Try it
Recurse...
Continue until board complete or backtrack when stuck"
Validation Explanation:
"For placing digit at (row, col):
ROW: Check if digit in board[row][0..8]
COL: Check if digit in board[0..8][col]
BOX: Calculate box start: (row/3)*3, (col/3)*3
Check 3×3 region from box start
If all three pass → Valid!"
Complexity:
"Time: O(9^m) where m = empty cells
Each cell: try 9 digits
m cells: 9^m possibilities
But pruning makes it much faster!
Space: O(m) recursion depth
Each level: one empty cell
Depth = number of empty cells"
Optimizations (if asked):
"1. Precompute empty cells list
2. Try digits with fewest conflicts first
3. Use bitsets for faster validation
But basic backtracking is sufficient!"
📝 Quick Revision Notes
🎯 Core Concept:
Sudoku Solver: Use backtracking to fill empty cells. For each empty cell, try digits 1-9. For each digit, validate (check row, col, 3×3 box). If valid, place digit and recurse. If recursion fails, backtrack (remove digit, try next). Continue until board complete. Box calculation: (row/3)*3, (col/3)*3.
⚡ Quick Implementation:
public class Solution {
public void solveSudoku(char[][] a) {
backtracking(a);
}
private boolean backtracking(char[][] a) {
// step 1: start looping through each cell looking for empty cell.
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
// step 2: empty cell found
if (a[i][j] == '.') {
// step 3: try each digit for that empty cell if it fits
for (char k = '1'; k <= '9'; k++) {
// step 4: can we place 'c' at (i, j)?
if (isValid(a, i, j, k)) {
// step 5: if we can place 'c' at (i, j), update the character
// in the board and solve for remaining empty cells
a[i][j] = k;
// step 6: solve for remaining.
// if solved for remaining, return true from here only
// and no need to try anything else.
if (backtracking(a)) {
return true;
}
// step 7: if above try failed, backtracking with new digit
a[i][j] = '.';
}
}
// step 8: you tried all digits and nothing worked for this cell
return false;
}
}
}
// step 9: there are no more empty cells.
// Sudoku is successfully solved, so returns true
return true;
}
private boolean isValid(char[][] a, int row, int col, char ch) {
// step 10: check all chars in 'row'
for (int c = 0; c < a[0].length; c++) {
if (a[row][c] == ch) {
return false;
}
}
// step 11: check all chars in 'col'
for (int r = 0; r < a.length; r++) {
if (a[r][col] == ch) {
return false;
}
}
// step 12: check all chars in the 'box'
int boxRow = (row / 3) * 3;
int boxCol = (col / 3) * 3;
for (int r = boxRow; r < boxRow + 3; r++) {
for (int c = boxCol; c < boxCol + 3; c++) {
if (a[r][c] == ch) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
Solution s = new Solution();
char[][] board = {
{ '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' }
};
s.solveSudoku(board);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
🔑 Key Insights:
- Pattern: Constraint Satisfaction with Backtracking
- 3 Constraints: Row, Column, 3×3 Box (all must be checked!)
- Try 1-9: For each empty cell
- Validate First: Before placing digit
- Backtrack: MUST remove digit if path fails
- Box Calculation:
(row/3)*3and(col/3)*3for start - Time: O(9^m) where m = empty cells, Space: O(m) ✓
🎪 Memory Aid:
"Find empty, try 1-9, check row-col-box, backtrack if stuck!"
"Box start: (row/3)3, (col/3)3!" ✨
⚠️ Critical Points:
Box Calculation - THE INTUITIVE EXPLANATION:
Goal: Given cell (row, col), find top-left corner of its 3×3 box
Think in terms of GROUPS:
Rows divided into 3 groups:
Group 0: rows 0,1,2 (starts at row 0)
Group 1: rows 3,4,5 (starts at row 3)
Group 2: rows 6,7,8 (starts at row 6)
Cols divided into 3 groups:
Group 0: cols 0,1,2 (starts at col 0)
Group 1: cols 3,4,5 (starts at col 3)
Group 2: cols 6,7,8 (starts at col 6)
Formula: boxRow = (row / 3) * 3
Step-by-step for cell (4, 5):
ROW:
row / 3 = 4 / 3 = 1 ← Which group? Group 1
1 * 3 = 3 ← Group 1 starts at row 3
boxRow = 3 ✓
COL:
col / 3 = 5 / 3 = 1 ← Which group? Group 1
1 * 3 = 3 ← Group 1 starts at col 3
boxCol = 3 ✓
Box starts at (3, 3) ✓
Visual for (4, 5):
0 1 2 | 3 4 5 | 6 7 8
3 . . . |⬆️ . . | . . . ← boxRow = 3
4 . . . | . X . | . . . ← row=4, col=5
5 . . . | . . . | . . .
⬆️
boxCol = 3
The pattern:
Division by 3 → Which group (0, 1, or 2)?
Multiply by 3 → Where does that group start (0, 3, or 6)?
All possible box starts: (0,0), (0,3), (0,6),
(3,0), (3,3), (3,6),
(6,0), (6,3), (6,6)
Always multiples of 3!
Alternative formula (same result):
boxRow = row - (row % 3)
"Round down to nearest multiple of 3"
Backtracking (MUST DO!):
board[row][col] = digit;
if (solve(board)) return true;
board[row][col] = '.'; ← CRITICAL!
Without this:
Digit stays even when path fails! ✗
Return Values:
- return true: Board solved OR path succeeds
- return false: No valid digit for this cell
- No empty cell found: Board complete → true
🧪 Edge Cases
Case 1: Almost solved (1 cell empty)
Only one cell needs filling
Quick solution
Case 2: Many empty cells
Harder, more backtracking needed
Still solvable with backtracking
Case 3: Requires deep backtracking
Early choices lead to dead ends
Must backtrack many levels
Algorithm handles it correctly
All handled by backtracking! ✓
🎓 Complexity Analysis
Time Complexity: O(9^m)
Where m = number of empty cells
Why?
Each empty cell: try up to 9 digits
m cells: 9 × 9 × 9 × ... (m times) = 9^m
Worst case: m = 81 (all empty)
9^81 = huge number!
But pruning (validation) eliminates most paths early!
Actual runtime much better than worst case.
Example:
m = 50 empty cells
Worst case: 9^50 = 5 × 10^47
With pruning: ~10^6 - 10^9 operations (practical!)
Space Complexity: O(m)
Recursion stack depth:
Maximum depth = m (number of empty cells)
Each recursive call: O(1) space
Total: O(m)
Board modification: In-place (O(1))
Total: O(m) auxiliary space
📚 Related Problems
Same Core Pattern: - N-Queens (LC 51) - Backtracking with constraints - Valid Sudoku (LC 36) - Just validation (no solving) - Sudoku Solver variants - Different grid sizes
Similar Backtracking: - Word Search (LC 79) - Path finding on grid - Combination Sum (LC 39) - Try values with constraints - Permutations (LC 46) - Generate all arrangements
Happy practicing! 🎯
Note: This is the classic constraint satisfaction problem! Master this and you understand: (1) backtracking with multiple constraints, (2) in-place modification and restoration, (3) pruning invalid paths early, (4) box/grid indexing. Very impressive problem for FAANG interviews - shows deep understanding of backtracking! The key trick is the box calculation: (row/3)*3 and (col/3)*3! 💪✨