Sudoku Solver (LeetCode
Learn how to solve Sudoku using backtracking, recursion, row-column-box validation, empty-cell selection, and pruning. Includes intuition, board representation, Java code, dry runs, complexity analysis, common mistakes, and interview tips.
Sudoku Solver (LeetCode #37)
Introduction
The Sudoku Solver problem is one of the most important constraint-based backtracking problems.
It is frequently discussed in interviews at companies such as:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Bloomberg
- Goldman Sachs
- JPMorgan Chase
This problem tests whether you can:
- Model a constraint-satisfaction problem
- Search through possible assignments
- Validate rows, columns, and subgrids
- Prune invalid choices early
- Restore mutable state
- Stop after finding one complete solution
- Analyze exponential search
- Optimize candidate selection
Sudoku is a natural progression after learning:
- Subsets
- Permutations
- Combinations
- Combination Sum
- N-Queens
The core backtracking pattern is:
graph TD
Choose["Choose"] --> Validate["Validate"]
Validate["Validate"] --> Explore["Explore"]
Explore["Explore"] --> Unchoose["Unchoose"]
Unlike simple combination problems, Sudoku has multiple overlapping constraints.
Every placed digit must satisfy:
- Row uniqueness
- Column uniqueness
- 3×3 box uniqueness
Problem Statement
You are given a partially completed 9 × 9 Sudoku board.
Fill the empty cells so that the completed board is valid.
Each row must contain the digits:
1 through 9
without repetition.
Each column must contain the digits:
1 through 9
without repetition.
Each 3 × 3 subgrid must also contain the digits:
1 through 9
without repetition.
The board contains:
- Digits
'1'through'9' '.'for empty cells
The solution must modify the input board in-place.
Example
Input
[
["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"]
]
Sudoku Rules
A completed board is valid only when all three rules are satisfied.
Rule 1 — Row Uniqueness
Every row must contain each digit exactly once.
Valid row:
5 3 4 6 7 8 9 1 2
Invalid row:
5 3 4 6 7 8 9 5 2
Digit 5 appears twice.
Rule 2 — Column Uniqueness
Every column must contain each digit exactly once.
Valid column:
5
6
1
8
4
7
9
2
3
Invalid column:
5
6
1
8
4
7
5
2
3
Digit 5 appears twice.
Rule 3 — 3×3 Box Uniqueness
Each 3 × 3 subgrid must contain the digits 1 through 9 without repetition.
Example box:
5 3 4
6 7 2
1 9 8
Board Coordinates
The board uses zero-based indexes.
Rows 0 through 8
Columns 0 through 8
A cell is identified by:
(row, column)
Example:
(0,0)
is the upper-left cell.
(8,8)
is the lower-right cell.
What Is an Empty Cell?
An empty cell contains:
'.'
Example:
if (board[row][column] == '.') {
// Cell needs a digit
}
The solver searches for an empty cell and tries candidate digits from:
1 through 9
Why Sudoku Is a Backtracking Problem
For each empty cell, multiple digits may appear valid initially.
A choice that is valid now may create a contradiction later.
Example:
graph TD
Place_4_in_Cell_A["Place 4 in Cell A"] --> Place_2_in_Cell_B["Place 2 in Cell B"]
Place_2_in_Cell_B["Place 2 in Cell B"] --> Continue_Solving["Continue Solving"]
Continue_Solving["Continue Solving"] --> No_Valid_Digit_for_Cell_Z["No Valid Digit for Cell Z"]
The solver must:
- Return to a previous choice.
- Remove the digit.
- Try another candidate.
This is exactly the backtracking process.
Core Backtracking Flow
graph TD
Find_Empty_Cell["Find Empty Cell"] --> Try_Digits_1_to_9["Try Digits 1 to 9"]
Try_Digits_1_to_9["Try Digits 1 to 9"] --> Digit_Valid["Digit Valid?"]
Digit_Valid["Digit Valid?"] --> Solve_Remaining_Board["Solve Remaining Board"]
Solve_Remaining_Board["Solve Remaining Board"] --> Solved["Solved?"]
Solved["Solved?"] --> Try_Next_Candidate["Try Next Candidate"]
Choose–Validate–Explore–Unchoose
Choose
board[row][column] = digit;
Place a candidate digit.
Validate
Before placement, verify that the digit does not already appear in:
- The same row
- The same column
- The same 3×3 box
Explore
if (solve(board)) {
return true;
}
Continue solving the remaining board.
Unchoose
board[row][column] = '.';
Restore the cell when the branch fails.
Why Return a Boolean?
LeetCode #37 requires only one valid completed board.
The recursive method can return:
true
when a complete solution is found.
This immediately stops further exploration.
Without a boolean return, the algorithm might continue searching after solving the board.
Base Condition
The board is solved when no empty cell remains.
Conceptually:
graph TD
No_Found["No '.' Found"] --> Every_Cell_Filled_Validly["Every Cell Filled Validly"]
Every_Cell_Filled_Validly["Every Cell Filled Validly"] --> Return_true["Return true"]
The recursive function scans the board.
If it cannot find any empty cell, the current board is complete.
Brute Force Approach
Suppose the board has:
E
empty cells.
Each empty cell can theoretically contain one of nine digits.
A naive search explores up to:
9^E
assignments.
For a board with 50 empty cells:
9^50
is astronomically large.
Backtracking reduces the search by rejecting invalid values immediately.
Backtracking Pruning
Before placing a digit, check the Sudoku constraints.
Example:
graph TD
Candidate_5["Candidate 5"] --> Already_in_Row["Already in Row?"]
Already_in_Row["Already in Row?"] --> Yes["Yes"]
Yes["Yes"] --> Reject_Immediately["Reject Immediately"]
The algorithm does not explore any board beginning with an invalid placement.
This early rejection is pruning.
Board Representation
The board is represented as:
char[][] board
Example:
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'}
};
Approach 1 — Basic Backtracking
Core Idea
Scan the board from top-left to bottom-right.
When an empty cell is found:
- Try digits
'1'through'9'. - Check whether the digit is valid.
- Place it.
- Recursively solve the board.
- Remove it if recursion fails.
If all cells are filled, return success.
Java Code — Basic Sudoku Solver
public class SudokuSolver {
public void solveSudoku(
char[][] board) {
validateBoardShape(board);
solve(board);
}
private boolean solve(
char[][] board) {
for (int row = 0;
row < 9;
row++) {
for (int column = 0;
column < 9;
column++) {
if (board[row][column]
!= '.') {
continue;
}
for (char digit = '1';
digit <= '9';
digit++) {
if (!isValid(
board,
row,
column,
digit)) {
continue;
}
board[row][column] =
digit;
if (solve(board)) {
return true;
}
board[row][column] =
'.';
}
return false;
}
}
return true;
}
private boolean isValid(
char[][] board,
int row,
int column,
char digit) {
return isRowValid(
board,
row,
digit)
&& isColumnValid(
board,
column,
digit)
&& isBoxValid(
board,
row,
column,
digit);
}
private boolean isRowValid(
char[][] board,
int row,
char digit) {
for (int column = 0;
column < 9;
column++) {
if (board[row][column]
== digit) {
return false;
}
}
return true;
}
private boolean isColumnValid(
char[][] board,
int column,
char digit) {
for (int row = 0;
row < 9;
row++) {
if (board[row][column]
== digit) {
return false;
}
}
return true;
}
private boolean isBoxValid(
char[][] board,
int row,
int column,
char digit) {
int boxStartRow =
(row / 3) * 3;
int boxStartColumn =
(column / 3) * 3;
for (int currentRow =
boxStartRow;
currentRow
< boxStartRow + 3;
currentRow++) {
for (int currentColumn =
boxStartColumn;
currentColumn
< boxStartColumn + 3;
currentColumn++) {
if (board[currentRow]
[currentColumn]
== digit) {
return false;
}
}
}
return true;
}
private void validateBoardShape(
char[][] board) {
if (board == null
|| board.length != 9) {
throw new IllegalArgumentException(
"Board must contain 9 rows");
}
for (char[] row : board) {
if (row == null
|| row.length != 9) {
throw new IllegalArgumentException(
"Every row must contain 9 cells");
}
}
}
}
Compact Interview Implementation
public class Solution {
public void solveSudoku(
char[][] board) {
solve(board);
}
private boolean solve(
char[][] board) {
for (int row = 0;
row < 9;
row++) {
for (int column = 0;
column < 9;
column++) {
if (board[row][column]
!= '.') {
continue;
}
for (char digit = '1';
digit <= '9';
digit++) {
if (!isValid(
board,
row,
column,
digit)) {
continue;
}
board[row][column] =
digit;
if (solve(board)) {
return true;
}
board[row][column] =
'.';
}
return false;
}
}
return true;
}
private boolean isValid(
char[][] board,
int row,
int column,
char digit) {
for (int index = 0;
index < 9;
index++) {
if (board[row][index]
== digit) {
return false;
}
if (board[index][column]
== digit) {
return false;
}
int boxRow =
3 * (row / 3)
+ index / 3;
int boxColumn =
3 * (column / 3)
+ index % 3;
if (board[boxRow][boxColumn]
== digit) {
return false;
}
}
return true;
}
}
Combined Validation Loop Explained
The compact implementation checks row, column, and box in one loop.
For:
index = 0 through 8
Row Cell
board[row][index]
Checks every column in the current row.
Column Cell
board[index][column]
Checks every row in the current column.
Box Cell
int boxRow =
3 * (row / 3)
+ index / 3;
int boxColumn =
3 * (column / 3)
+ index % 3;
Maps indexes 0 through 8 to the nine cells of the relevant 3 × 3 box.
Finding the 3×3 Box
For any cell:
(row, column)
the top-left corner of its box is:
graph TD
boxStartRow_0_0["boxStartRow"] --> boxStartColumn_1_1["boxStartColumn"]
boxStartRow_0_0["boxStartRow"] --> column_1_2["column"]
row_0_1["row"] --> N_3_1_3["3"]
row_0_1["row"] --> N_3_1_4["3"]
Box Example
Suppose:
row = 4
column = 7
Calculate:
graph TD
boxStartRow_0_0["boxStartRow"] --> N_4_1_1["4"]
boxStartRow_0_0["boxStartRow"] --> N_3_1_2["3"]
N_4_1_1["4"] --> N_1_2_1["1"]
N_4_1_1["4"] --> N_3_2_2["3"]
N_1_2_1["1"] --> N_3_3_1["3"]
graph TD
boxStartColumn_0_0["boxStartColumn"] --> N_7_1_1["7"]
boxStartColumn_0_0["boxStartColumn"] --> N_3_1_2["3"]
N_7_1_1["7"] --> N_2_2_1["2"]
N_7_1_1["7"] --> N_3_2_2["3"]
N_2_2_1["2"] --> N_6_3_1["6"]
The box begins at:
(3,6)
and includes:
Rows 3, 4, 5
Columns 6, 7, 8
3×3 Box Layout
The nine boxes are arranged as:
Box 0 | Box 1 | Box 2
------+-------+------
Box 3 | Box 4 | Box 5
------+-------+------
Box 6 | Box 7 | Box 8
A box index can be calculated as:
graph TD
boxIndex_0_0["boxIndex"] --> row_1_1["row"]
boxIndex_0_0["boxIndex"] --> N_3_1_2["3"]
row_1_1["row"] --> column_2_1["column"]
row_1_1["row"] --> N_3_2_2["3"]
This formula becomes useful in optimized solutions.
Why Return False After Trying All Digits?
Consider this section:
for (char digit = '1';
digit <= '9';
digit++) {
// Try candidate
}
return false;
If no digit from 1 to 9 solves the board, the current partial assignment is invalid.
The function returns false so the previous recursive call can undo its choice.
Why Return Immediately After Processing One Empty Cell?
The solver finds the first empty cell.
It tries every possible digit for that cell.
There is no need for the current recursive call to continue scanning other cells directly.
The next recursive call will scan the board again after the chosen digit is placed.
If all candidates fail, the current branch is impossible.
Therefore:
return false;
appears immediately after trying the candidates for the first empty cell.
Incorrect Control Flow
This structure is wrong:
for every cell {
if empty {
try digits;
}
}
return true;
If one empty cell cannot be filled, the method must stop and backtrack.
Continuing to later cells would leave the board incomplete.
Detailed Backtracking Example
Consider a simplified section of the puzzle.
Suppose the solver reaches an empty cell:
(row 0, column 2)
Initial row:
5 3 . . 7 . . . .
Column 2 contains:
.
.
8
.
.
.
.
.
.
The upper-left 3 × 3 box contains:
5 3 .
6 . .
. 9 8
Candidate 1 at (0,2)
Check row:
1 not present
Check column:
1 not present
Check box:
1 not present
Candidate 1 is locally valid.
Place:
5 3 1 . 7 . . . .
Continue recursively.
A contradiction may appear later.
If that happens, remove 1 and try the next candidate.
Candidate 2 at (0,2)
If candidate 1 eventually fails, restore:
5 3 . . 7 . . . .
Try 2.
Again check:
- Row
- Column
- Box
If valid, recurse.
Candidate 4 at (0,2)
In the known solution, the final value is:
4
The solver may reach this value after earlier candidate branches fail.
Place:
5 3 4 . 7 . . . .
Then continue solving.
Backtracking Snapshot
graph TD
Try_1["Try 1"] --> Later_Contradiction["Later Contradiction"]
Later_Contradiction["Later Contradiction"] --> Remove_1["Remove 1"]
Remove_1["Remove 1"] --> Try_2["Try 2"]
Try_2["Try 2"] --> Later_Contradiction["Later Contradiction"]
Later_Contradiction["Later Contradiction"] --> Remove_2["Remove 2"]
Remove_2["Remove 2"] --> Try_4["Try 4"]
Try_4["Try 4"] --> Continue_Successfully["Continue Successfully"]
The exact order and number of failed branches depend on earlier choices.
Simplified Recursion Tree
For one empty cell:
graph TD
Empty_0_0["Empty"] --> N_1_1_1["1"]
Empty_0_0["Empty"] --> N_2_1_2["2"]
Cell_0_1["Cell"] --> N_3_1_3["3"]
Cell_0_1["Cell"] --> N_4_1_4["4"]
N_1_1_1["1"] --> invalid_2_1["invalid"]
N_1_1_1["1"] --> valid_2_2["valid"]
invalid_2_1["invalid"] --> Next_3_1["Next"]
invalid_2_1["invalid"] --> Empty_3_2["Empty"]
valid_2_2["valid"] --> Cell_3_3["Cell"]
Next_3_1["Next"] --> N_1_4_1["1"]
Next_3_1["Next"] --> N_2_4_2["2"]
Empty_3_2["Empty"] --> N_3_4_3["3"]
Empty_3_2["Empty"] --> N_9_4_4["9"]
Invalid values are pruned immediately.
Valid values create deeper branches.
Full Search State
At any point, the search state is the current board.
Every filled empty cell represents a decision.
Example:
graph TD
Initial_Board["Initial Board"] --> Place_Digit_in_Empty_Cell_1["Place Digit in Empty Cell 1"]
Place_Digit_in_Empty_Cell_1["Place Digit in Empty Cell 1"] --> Place_Digit_in_Empty_Cell_2["Place Digit in Empty Cell 2"]
Place_Digit_in_Empty_Cell_2["Place Digit in Empty Cell 2"] --> Place_Digit_in_Empty_Cell_3["Place Digit in Empty Cell 3"]
Place_Digit_in_Empty_Cell_3["Place Digit in Empty Cell 3"] --> Contradiction["Contradiction"]
Contradiction["Contradiction"] --> Undo_Digit_3["Undo Digit 3"]
Undo_Digit_3["Undo Digit 3"] --> Try_Another_Digit["Try Another Digit"]
Why the Board Must Be Restored
Suppose the solver places:
board[row][column] = '4';
and recursion fails.
Before trying another digit:
board[row][column] = '.';
must restore the cell.
Without restoration, the next branch would see an incorrect pre-filled value.
Correct State Restoration
board[row][column] =
digit;
if (solve(board)) {
return true;
}
board[row][column] =
'.';
Why Pre-Filled Cells Are Never Changed
The solver skips cells that are not empty.
if (board[row][column]
!= '.') {
continue;
}
This preserves the original puzzle clues.
Only cells that originally or currently contain '.' are assigned by backtracking.
Validating the Initial Puzzle
The standard LeetCode problem guarantees that the input puzzle is valid.
In production code, the initial board may need validation.
Check that:
- Every value is
'.'or'1'through'9' - No row contains duplicate digits
- No column contains duplicate digits
- No box contains duplicate digits
Validation will be covered more deeply in Part 2.
Basic Initial Board Validator
public class SudokuValidator {
public boolean isValidSudoku(
char[][] board) {
if (board == null
|| board.length != 9) {
return false;
}
for (char[] row : board) {
if (row == null
|| row.length != 9) {
return false;
}
}
for (int row = 0;
row < 9;
row++) {
for (int column = 0;
column < 9;
column++) {
char digit =
board[row][column];
if (digit == '.') {
continue;
}
if (digit < '1'
|| digit > '9') {
return false;
}
board[row][column] =
'.';
boolean valid =
isValid(
board,
row,
column,
digit);
board[row][column] =
digit;
if (!valid) {
return false;
}
}
}
return true;
}
private boolean isValid(
char[][] board,
int row,
int column,
char digit) {
for (int index = 0;
index < 9;
index++) {
if (board[row][index]
== digit) {
return false;
}
if (board[index][column]
== digit) {
return false;
}
int boxRow =
3 * (row / 3)
+ index / 3;
int boxColumn =
3 * (column / 3)
+ index % 3;
if (board[boxRow][boxColumn]
== digit) {
return false;
}
}
return true;
}
}
This validator is easy to understand but repeatedly scans rows, columns, and boxes.
Part 2 introduces a more efficient validation approach.
Complexity Analysis
Sudoku backtracking complexity depends heavily on the puzzle.
Let:
E = number of empty cells
Each empty cell may try up to:
9
digits.
A loose upper bound is:
O(9^E)
This represents the worst case without effective pruning.
Validation Cost
The basic isValid() method checks:
- Nine row cells
- Nine column cells
- Nine box cells
This is:
O(9)
Since the board size is fixed, it is often treated as:
O(1)
However, conceptually for a generalized N × N Sudoku-like board, validation would cost more.
Practical Runtime
Real Sudoku puzzles contain many constraints.
Most candidates are rejected quickly.
Therefore, actual runtime is usually much smaller than the theoretical upper bound.
Performance depends on:
- Number of empty cells
- Puzzle difficulty
- Cell selection order
- Candidate order
- Constraint propagation
- Validation data structures
Space Complexity
Recursion Stack
At most one recursive level per empty cell:
O(E)
For standard Sudoku:
E <= 81
Board
The board contains:
81 cells
and is modified in-place.
Additional board space:
O(1)
for fixed 9 × 9 Sudoku.
Total Auxiliary Space
For the basic implementation:
O(E)
because of recursion.
No additional result board is required.
Complexity Summary
| Complexity | Basic Backtracking |
|---|---|
| Worst-Case Time | O(9^E) |
| Validation per Candidate | O(1) for fixed 9×9 board |
| Recursion Depth | O(E) |
| Additional Board Space | O(1) |
| Output Space | O(1), board modified in-place |
Why Sudoku Has One-Solution Early Exit
Unlike N-Queens, the Sudoku problem does not ask for every valid board.
As soon as a complete valid board is found:
return true;
propagates through every recursive level.
This prevents unnecessary continued search.
What If the Puzzle Has Multiple Solutions?
The standard solver returns the first solution found according to:
- Empty-cell scan order
- Candidate digit order
To return all solutions, the algorithm must:
- Copy completed boards
- Continue after finding a solution
- Remove the early
return true
That variation can consume much more time and memory.
Find One Solution vs All Solutions
| One Solution | All Solutions |
|---|---|
| Return boolean | Store completed boards |
| Stop on success | Continue searching |
| Less runtime | Potentially huge runtime |
| Standard LeetCode #37 | Useful for analysis or validation |
Correctness Intuition
The algorithm is correct because:
- It preserves all original clues.
- It selects only empty cells.
- It tries every digit from
1through9. - It places a digit only when row, column, and box constraints remain valid.
- It recursively solves the remaining board.
- It removes digits from failed branches.
- It returns success only when no empty cell remains.
Therefore, any returned board is a valid Sudoku solution.
If a valid solution exists, every candidate choice is eventually considered, so the solver can find it.
Formal Invariant
At every recursive call:
All currently filled cells satisfy the Sudoku constraints.
Initially, the puzzle is assumed valid.
Before placing a new digit, isValid() verifies that the invariant remains true.
If recursion fails, the digit is removed, restoring the previous valid state.
When no empty cell remains, the invariant applies to the complete board.
Therefore, the completed board is valid.
Common Interview Mistakes
Mistake 1 — Forgetting to Reset the Cell
Incorrect:
board[row][column] = digit;
solve(board);
Missing:
board[row][column] = '.';
Without state restoration, failed candidates remain on the board.
Mistake 2 — Returning True Too Early
Do not return true immediately after placing a locally valid digit.
Correct:
if (solve(board)) {
return true;
}
The remaining board must also be solvable.
Mistake 3 — Continuing After an Empty Cell Has No Valid Digit
When all digits fail for the current empty cell:
return false;
The current branch is impossible.
Mistake 4 — Modifying Original Clues
Skip non-empty cells.
Never overwrite pre-filled values.
Mistake 5 — Incorrect Box Start Calculation
Correct:
int boxStartRow =
(row / 3) * 3;
int boxStartColumn =
(column / 3) * 3;
Mistake 6 — Checking Only Row and Column
Sudoku also requires box uniqueness.
Ignoring boxes can produce invalid boards.
Mistake 7 — Not Stopping After a Solution
The standard problem needs one solution.
Returning a boolean avoids unnecessary continued search.
Mistake 8 — Claiming Polynomial Time
Sudoku solving through backtracking is exponential in the worst case.
Mistake 9 — Using String Conversion Repeatedly
The board is already mutable as char[][].
Avoid converting rows to strings during every recursive step.
Mistake 10 — Not Validating Input Shape
Production code should ensure the board is exactly 9 × 9.
Mistake 11 — Accepting Invalid Characters
Only these values are valid:
'.'
'1' through '9'
Mistake 12 — Confusing Box Coordinates
The box is determined by integer division:
graph TD
row_0_0["row"] --> column_1_1["column"]
row_0_0["row"] --> N_3_1_2["3"]
Edge Cases
Already Solved Board
The solver scans the entire board.
No empty cell is found.
It returns:
true
without making changes.
Board with One Empty Cell
The solver tries digits until the only valid value is found.
Recursion then confirms the completed board.
Invalid Initial Board
The LeetCode problem guarantees valid input.
Production code should reject or report the invalid puzzle.
Unsolvable Board
The recursive solver eventually tries every valid branch and returns:
false
The public API should decide whether to:
- Leave the board unchanged
- Throw an exception
- Return a boolean
- Return an optional result
Safer Production API
The LeetCode method returns void, assuming a solution exists.
A production-style API can return a boolean.
public class SudokuService {
public boolean solveSudoku(
char[][] board) {
validateBoardShape(board);
return solve(board);
}
private boolean solve(
char[][] board) {
// Backtracking implementation
return false;
}
private void validateBoardShape(
char[][] board) {
if (board == null
|| board.length != 9) {
throw new IllegalArgumentException(
"Board must be 9x9");
}
for (char[] row : board) {
if (row == null
|| row.length != 9) {
throw new IllegalArgumentException(
"Board must be 9x9");
}
}
}
}
Preserving the Original Board on Failure
The in-place solver may restore every failed choice through backtracking.
If the puzzle is unsolvable, the board should return to its original state, provided:
- Only empty cells are modified
- Every failed assignment is reset
For stronger safety, solve a copy and copy the result back only on success.
Copy-on-Solve Strategy
public boolean solveSafely(
char[][] board) {
char[][] workingCopy =
copyBoard(board);
if (!solve(workingCopy)) {
return false;
}
for (int row = 0;
row < 9;
row++) {
System.arraycopy(
workingCopy[row],
0,
board[row],
0,
9);
}
return true;
}
private char[][] copyBoard(
char[][] board) {
char[][] copy =
new char[9][9];
for (int row = 0;
row < 9;
row++) {
System.arraycopy(
board[row],
0,
copy[row],
0,
9);
}
return copy;
}
This approach provides transactional behavior:
Success → Apply solved board
Failure → Original board unchanged
Sudoku as a Constraint Satisfaction Problem
Sudoku can be modeled using CSP terminology.
Variables
Each empty cell is a variable.
Example:
Cell (0,2)
Domain
Possible digits:
1 through 9
after excluding row, column, and box conflicts.
Constraints
For every cell:
- Row values must be unique.
- Column values must be unique.
- Box values must be unique.
Assignment
Placing a digit assigns a value to a variable.
Backtracking
When a later variable has no valid value, undo earlier assignments.
Candidate Domain Example
Suppose cell (0,2) cannot use:
3, 5, 6, 7, 8, 9
Its remaining domain may be:
{1, 2, 4}
The basic solver tries candidates in numerical order.
Advanced solvers calculate domains and choose highly constrained cells first.
This will be covered in Part 2.
Sudoku vs N-Queens
| Sudoku | N-Queens |
|---|---|
| Many empty cells | One queen per row |
| Digits 1–9 | Columns 0–n−1 |
| Row, column, box constraints | Column and diagonal constraints |
| Stop after one solution | Often return all solutions |
| Variable number of decisions | Exactly n queen placements |
| Strong candidate-domain heuristics | Simple row-by-row ordering |
Both rely on early validation and state restoration.
Sudoku vs Combination Sum
| Sudoku | Combination Sum |
|---|---|
| Assign values to cells | Select candidate numbers |
| Multiple constraint groups | Target-sum constraint |
| Every empty cell must be filled | Combination length varies |
| Usually one solution needed | All combinations returned |
| Candidate reuse depends on cells | Numeric candidates may repeat |
Production Applications
Sudoku itself is a puzzle, but the same search pattern appears in:
- Scheduling
- Timetable generation
- Resource allocation
- Configuration validation
- Assignment optimization
- Puzzle solving
- Rule engines
- Test-data generation
- Seating arrangements
- Constraint-based planning
Real-World Example — Employee Scheduling
Suppose employees must be assigned to shifts.
Constraints include:
- One employee cannot work two overlapping shifts.
- Each shift requires specific skills.
- Weekly hour limits must be respected.
- Some employees are unavailable at certain times.
The process resembles Sudoku:
graph TD
Empty_Shift_Slot["Empty Shift Slot"] --> Try_Employee["Try Employee"]
Try_Employee["Try Employee"] --> Validate_Constraints["Validate Constraints"]
Validate_Constraints["Validate Constraints"] --> Assign["Assign"]
Assign["Assign"] --> Continue["Continue"]
Continue["Continue"] --> Backtrack_on_Conflict["Backtrack on Conflict"]
Real-World Example — Exam Timetable
Courses must be placed into time slots and rooms.
Constraints:
- Students cannot have overlapping exams.
- Room capacity must be sufficient.
- Instructors cannot be double-booked.
- Some rooms support only specific equipment.
Each exam slot acts like a Sudoku cell with a candidate domain.
Real-World Example — Configuration Selection
An enterprise platform may have configuration fields with compatibility rules.
Example:
- Database type
- Cloud region
- Deployment mode
- Authentication provider
- Network topology
Some combinations are invalid.
A constraint solver can assign one configuration value at a time and backtrack when compatibility rules fail.
Strong Interview Explanation
I scan the board for the first empty cell. For that cell, I try digits from 1 through 9. Before placing a digit, I verify that it does not already exist in the same row, column, or 3×3 box. If valid, I place it and recursively solve the remaining board. If recursion succeeds, I return true immediately. Otherwise, I reset the cell to empty and try the next digit. If no digit works, I return false so the previous call can backtrack. When no empty cell remains, the board is solved.
Interview Tips
Interviewers commonly ask:
- Why is Sudoku a backtracking problem?
- Why does the recursive method return boolean?
- What is the base condition?
- Why process only the first empty cell?
- Why must the cell be reset?
- How is a 3×3 box located?
- What is the worst-case time complexity?
- How do you validate a candidate?
- How would you optimize repeated validation?
- How would you choose the best empty cell?
- How would you determine whether a puzzle has multiple solutions?
- How would you validate the initial board?
- How would you preserve the original board on failure?
- Can bitmasks improve the solution?
- How would you generate a Sudoku puzzle?
Unit Test — Standard Puzzle
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.Test;
class SudokuSolverTest {
private final SudokuSolver solution =
new SudokuSolver();
@Test
void shouldSolveStandardPuzzle() {
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'}
};
char[][] expected = {
{'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'}
};
solution.solveSudoku(board);
for (int row = 0;
row < 9;
row++) {
assertArrayEquals(
expected[row],
board[row]);
}
}
}
Unit Test — Already Solved Board
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.Test;
class SolvedSudokuTest {
private final SudokuSolver solution =
new SudokuSolver();
@Test
void shouldLeaveSolvedBoardUnchanged() {
char[][] board = {
{'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'}
};
char[][] original =
copy(board);
solution.solveSudoku(board);
for (int row = 0;
row < 9;
row++) {
assertArrayEquals(
original[row],
board[row]);
}
}
private char[][] copy(
char[][] board) {
char[][] result =
new char[9][9];
for (int row = 0;
row < 9;
row++) {
System.arraycopy(
board[row],
0,
result[row],
0,
9);
}
return result;
}
}
Unit Test — Board Shape Validation
import static org.junit.jupiter.api.Assertions.assertThrows;
import org.junit.jupiter.api.Test;
class SudokuBoardValidationTest {
private final SudokuSolver solution =
new SudokuSolver();
@Test
void shouldRejectBoardWithWrongRowCount() {
char[][] board =
new char[8][9];
assertThrows(
IllegalArgumentException.class,
() -> solution.solveSudoku(board));
}
@Test
void shouldRejectBoardWithWrongColumnCount() {
char[][] board =
new char[9][8];
assertThrows(
IllegalArgumentException.class,
() -> solution.solveSudoku(board));
}
}
Sudoku Solver (LeetCode #37) — Part 2
Optimizing Sudoku Validation
The basic solution checks the current row, column, and 3 × 3 box every time it tests a candidate digit.
Although each scan is constant time for a fixed 9 × 9 board, the same checks are repeated thousands of times during difficult searches.
We can reduce candidate validation to direct lookup by maintaining:
- Digits used in every row
- Digits used in every column
- Digits used in every box
This changes candidate validation from repeated scanning to:
O(1)
lookup.
Approach 2 — Row, Column, and Box Boolean Arrays
Core Idea
Create three lookup structures:
boolean[][] rows;
boolean[][] columns;
boolean[][] boxes;
Each structure has:
9 groups
10 digit positions
Index 0 is unused so that digit values 1 through 9 can be used directly.
Example:
rows[2][7] = true;
means digit 7 already exists in row 2.
Lookup Structure Meaning
Row Lookup
rows[row][digit]
Returns whether the digit is already present in the row.
Column Lookup
columns[column][digit]
Returns whether the digit is already present in the column.
Box Lookup
boxes[boxIndex][digit]
Returns whether the digit is already present in the 3 × 3 box.
Box Index Formula
For a cell:
(row, column)
calculate its box using:
graph TD
boxIndex_0_0["boxIndex"] --> row_1_1["row"]
boxIndex_0_0["boxIndex"] --> N_3_1_2["3"]
row_1_1["row"] --> column_2_1["column"]
row_1_1["row"] --> N_3_2_2["3"]
Box Index Examples
Cell (0,0)
(0 / 3) × 3 + (0 / 3)
=
0
Cell (1,7)
graph TD
N_1_0_0["1"] --> N_0_1_1["0"]
N_1_0_0["1"] --> N_2_1_2["2"]
N_0_1_1["0"] --> N_2_2_1["2"]
Cell (4,4)
graph TD
N_4_0_0["4"] --> N_1_1_1["1"]
N_4_0_0["4"] --> N_3_1_2["3"]
N_3_0_1["3"] --> N_1_1_3["1"]
N_1_1_1["1"] --> N_4_2_1["4"]
Cell (8,8)
graph TD
N_8_0_0["8"] --> N_2_1_1["2"]
N_8_0_0["8"] --> N_3_1_2["3"]
N_3_0_1["3"] --> N_2_1_3["2"]
N_2_1_1["2"] --> N_8_2_1["8"]
Box Index Layout
0 | 1 | 2
--+---+--
3 | 4 | 5
--+---+--
6 | 7 | 8
Initializing the Lookup Structures
Before solving, scan the original puzzle.
For every fixed digit:
- Convert the character into an integer.
- Calculate its box index.
- Mark the digit as used.
Example:
int digit =
board[row][column] - '0';
int box =
(row / 3) * 3
+ column / 3;
rows[row][digit] = true;
columns[column][digit] = true;
boxes[box][digit] = true;
Detecting Invalid Initial Boards
During initialization, check whether the digit is already marked.
if (rows[row][digit]
|| columns[column][digit]
|| boxes[box][digit]) {
return false;
}
This detects duplicate values in:
- A row
- A column
- A box
Optimized Java Solution
public class SudokuSolverOptimized {
private static final int SIZE = 9;
public boolean solveSudoku(
char[][] board) {
validateBoardShape(board);
boolean[][] rows =
new boolean[SIZE][10];
boolean[][] columns =
new boolean[SIZE][10];
boolean[][] boxes =
new boolean[SIZE][10];
if (!initializeConstraints(
board,
rows,
columns,
boxes)) {
return false;
}
return solve(
board,
0,
rows,
columns,
boxes);
}
private boolean solve(
char[][] board,
int cellIndex,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
if (cellIndex
== SIZE * SIZE) {
return true;
}
int row =
cellIndex / SIZE;
int column =
cellIndex % SIZE;
if (board[row][column]
!= '.') {
return solve(
board,
cellIndex + 1,
rows,
columns,
boxes);
}
int box =
boxIndex(
row,
column);
for (int digit = 1;
digit <= 9;
digit++) {
if (rows[row][digit]
|| columns[column][digit]
|| boxes[box][digit]) {
continue;
}
placeDigit(
board,
row,
column,
box,
digit,
rows,
columns,
boxes);
if (solve(
board,
cellIndex + 1,
rows,
columns,
boxes)) {
return true;
}
removeDigit(
board,
row,
column,
box,
digit,
rows,
columns,
boxes);
}
return false;
}
private boolean initializeConstraints(
char[][] board,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
char value =
board[row][column];
if (value == '.') {
continue;
}
if (value < '1'
|| value > '9') {
return false;
}
int digit =
value - '0';
int box =
boxIndex(
row,
column);
if (rows[row][digit]
|| columns[column][digit]
|| boxes[box][digit]) {
return false;
}
rows[row][digit] = true;
columns[column][digit] = true;
boxes[box][digit] = true;
}
}
return true;
}
private void placeDigit(
char[][] board,
int row,
int column,
int box,
int digit,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
board[row][column] =
(char) ('0' + digit);
rows[row][digit] = true;
columns[column][digit] = true;
boxes[box][digit] = true;
}
private void removeDigit(
char[][] board,
int row,
int column,
int box,
int digit,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
board[row][column] = '.';
rows[row][digit] = false;
columns[column][digit] = false;
boxes[box][digit] = false;
}
private int boxIndex(
int row,
int column) {
return (row / 3) * 3
+ column / 3;
}
private void validateBoardShape(
char[][] board) {
if (board == null
|| board.length != SIZE) {
throw new IllegalArgumentException(
"Board must contain 9 rows");
}
for (char[] row : board) {
if (row == null
|| row.length != SIZE) {
throw new IllegalArgumentException(
"Every row must contain 9 cells");
}
}
}
}
Why Use a Linear Cell Index?
The recursive method uses:
cellIndex
from:
0 through 80
Convert it using:
row = cellIndex / 9;
column = cellIndex % 9;
This avoids restarting a nested board scan during every recursive call.
It also gives a clear base condition:
cellIndex == 81
Constraint State Restoration
When a candidate fails, restore every modified structure.
board[row][column] = '.';
rows[row][digit] = false;
columns[column][digit] = false;
boxes[box][digit] = false;
Forgetting even one structure will incorrectly block candidates in later branches.
Complexity of Boolean Lookup Solution
The worst-case search remains exponential:
O(9^E)
where E is the number of empty cells.
However, candidate validation is now:
O(1)
instead of repeatedly scanning row, column, and box cells.
Auxiliary lookup memory is fixed:
3 × 9 × 10 booleans
For standard Sudoku, this is:
O(1)
space.
Approach 3 — Precompute Empty Cells
Core Idea
Instead of examining all 81 cells during recursion, collect only empty positions.
Example:
List<Cell> emptyCells;
The recursive depth then corresponds directly to an empty cell index.
Cell Representation
Using a Java record:
public record Cell(
int row,
int column) {
}
Empty Cell Collection
List<Cell> emptyCells =
new ArrayList<>();
for (int row = 0;
row < 9;
row++) {
for (int column = 0;
column < 9;
column++) {
if (board[row][column]
== '.') {
emptyCells.add(
new Cell(
row,
column));
}
}
}
Java Code — Empty Cell Optimization
import java.util.ArrayList;
import java.util.List;
public class SudokuSolverWithEmptyCells {
private static final int SIZE = 9;
public boolean solveSudoku(
char[][] board) {
boolean[][] rows =
new boolean[SIZE][10];
boolean[][] columns =
new boolean[SIZE][10];
boolean[][] boxes =
new boolean[SIZE][10];
List<Cell> emptyCells =
new ArrayList<>();
if (!initialize(
board,
rows,
columns,
boxes,
emptyCells)) {
return false;
}
return solve(
board,
0,
emptyCells,
rows,
columns,
boxes);
}
private boolean solve(
char[][] board,
int emptyIndex,
List<Cell> emptyCells,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
if (emptyIndex
== emptyCells.size()) {
return true;
}
Cell cell =
emptyCells.get(
emptyIndex);
int row = cell.row();
int column = cell.column();
int box =
(row / 3) * 3
+ column / 3;
for (int digit = 1;
digit <= 9;
digit++) {
if (rows[row][digit]
|| columns[column][digit]
|| boxes[box][digit]) {
continue;
}
board[row][column] =
(char) ('0' + digit);
rows[row][digit] = true;
columns[column][digit] = true;
boxes[box][digit] = true;
if (solve(
board,
emptyIndex + 1,
emptyCells,
rows,
columns,
boxes)) {
return true;
}
board[row][column] = '.';
rows[row][digit] = false;
columns[column][digit] = false;
boxes[box][digit] = false;
}
return false;
}
private boolean initialize(
char[][] board,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes,
List<Cell> emptyCells) {
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
char value =
board[row][column];
if (value == '.') {
emptyCells.add(
new Cell(
row,
column));
continue;
}
if (value < '1'
|| value > '9') {
return false;
}
int digit =
value - '0';
int box =
(row / 3) * 3
+ column / 3;
if (rows[row][digit]
|| columns[column][digit]
|| boxes[box][digit]) {
return false;
}
rows[row][digit] = true;
columns[column][digit] = true;
boxes[box][digit] = true;
}
}
return true;
}
public record Cell(
int row,
int column) {
}
}
Benefit of Empty Cell Precomputation
Without precomputation, recursive calls may repeatedly scan fixed cells.
With precomputation:
Recursive Depth = Number of Empty Cells
This improves clarity and reduces unnecessary board traversal.
It does not change the worst-case exponential complexity.
Approach 4 — Minimum Remaining Values Heuristic
Core Idea
The order in which empty cells are processed has a major impact on search performance.
Instead of selecting the first empty cell, choose the cell with the fewest valid candidates.
This strategy is called:
Minimum Remaining Values
or:
MRV
Why MRV Works
Suppose two empty cells have these candidate sets:
Cell A → {1, 2, 4, 7}
Cell B → {3}
Choosing Cell B first is better.
Its value is forced.
If digit 3 creates a contradiction, the solver discovers it immediately instead of exploring many branches through Cell A.
Fail-Fast Principle
MRV follows a general search principle:
Explore the most constrained decision first.
This reduces the branching factor near the top of the recursion tree.
Candidate Count
For every empty cell, count digits that are not already used in its:
- Row
- Column
- Box
Choose the cell with the smallest count.
MRV Backtracking Flow
graph TD
Find_Unfilled_Cell_with_Fewe["Find Unfilled Cell with Fewest Candidates"] --> No_Candidates["No Candidates?"]
No_Candidates["No Candidates?"] --> Return_false["Return false"]
Return_false["Return false"] --> One_or_More_Candidates["One or More Candidates"]
One_or_More_Candidates["One or More Candidates"] --> Try_Each_Candidate["Try Each Candidate"]
Try_Each_Candidate["Try Each Candidate"] --> Recurse["Recurse"]
Recurse["Recurse"] --> Undo_on_Failure["Undo on Failure"]
Java Code — MRV Sudoku Solver
public class SudokuSolverMRV {
private static final int SIZE = 9;
public boolean solveSudoku(
char[][] board) {
boolean[][] rows =
new boolean[SIZE][10];
boolean[][] columns =
new boolean[SIZE][10];
boolean[][] boxes =
new boolean[SIZE][10];
if (!initialize(
board,
rows,
columns,
boxes)) {
return false;
}
return solve(
board,
rows,
columns,
boxes);
}
private boolean solve(
char[][] board,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
CandidateCell best =
findMostConstrainedCell(
board,
rows,
columns,
boxes);
if (best == null) {
return true;
}
if (best.candidateCount()
== 0) {
return false;
}
int row = best.row();
int column = best.column();
int box =
boxIndex(
row,
column);
for (int digit = 1;
digit <= 9;
digit++) {
if (rows[row][digit]
|| columns[column][digit]
|| boxes[box][digit]) {
continue;
}
board[row][column] =
(char) ('0' + digit);
rows[row][digit] = true;
columns[column][digit] = true;
boxes[box][digit] = true;
if (solve(
board,
rows,
columns,
boxes)) {
return true;
}
board[row][column] = '.';
rows[row][digit] = false;
columns[column][digit] = false;
boxes[box][digit] = false;
}
return false;
}
private CandidateCell
findMostConstrainedCell(
char[][] board,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
CandidateCell best = null;
int bestCount =
Integer.MAX_VALUE;
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
if (board[row][column]
!= '.') {
continue;
}
int box =
boxIndex(
row,
column);
int count = 0;
for (int digit = 1;
digit <= 9;
digit++) {
if (!rows[row][digit]
&& !columns[column][digit]
&& !boxes[box][digit]) {
count++;
}
}
if (count < bestCount) {
bestCount = count;
best =
new CandidateCell(
row,
column,
count);
if (count <= 1) {
return best;
}
}
}
}
return best;
}
private boolean initialize(
char[][] board,
boolean[][] rows,
boolean[][] columns,
boolean[][] boxes) {
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
char value =
board[row][column];
if (value == '.') {
continue;
}
if (value < '1'
|| value > '9') {
return false;
}
int digit =
value - '0';
int box =
boxIndex(
row,
column);
if (rows[row][digit]
|| columns[column][digit]
|| boxes[box][digit]) {
return false;
}
rows[row][digit] = true;
columns[column][digit] = true;
boxes[box][digit] = true;
}
}
return true;
}
private int boxIndex(
int row,
int column) {
return (row / 3) * 3
+ column / 3;
}
public record CandidateCell(
int row,
int column,
int candidateCount) {
}
}
MRV Trade-Off
MRV performs additional work to scan all empty cells at each recursive level.
However, it often saves far more work by dramatically reducing the search tree.
For easy puzzles, the simpler solver may already be fast enough.
For difficult puzzles, MRV can provide a major improvement.
Approach 5 — Bitmask Sudoku Solver
Core Idea
Each row, column, and box needs to track digits 1 through 9.
Nine digits fit inside an integer bitmask.
Use bit positions:
Bit 0 → Digit 1
Bit 1 → Digit 2
...
Bit 8 → Digit 9
Digit Bit Formula
For digit d:
int bit =
1 << (d - 1);
Examples:
Digit 1 → 000000001
Digit 2 → 000000010
Digit 9 → 100000000
Used Digit Masks
Maintain:
int[] rowMasks =
new int[9];
int[] columnMasks =
new int[9];
int[] boxMasks =
new int[9];
Check Candidate Availability
A candidate is unavailable when its bit appears in any mask.
int used =
rowMasks[row]
| columnMasks[column]
| boxMasks[box];
boolean unavailable =
(used & bit) != 0;
Available Candidate Mask
All nine digits:
int fullMask =
(1 << 9) - 1;
Binary:
111111111
Available digits:
int available =
fullMask & ~used;
Extract Candidate Bits
Use:
int bit =
available & -available;
Then remove it:
available &= available - 1;
Convert the bit to a digit:
int digit =
Integer.numberOfTrailingZeros(bit)
+ 1;
Java Code — Bitmask Solver with MRV
public class SudokuSolverBitmask {
private static final int SIZE = 9;
private static final int FULL_MASK =
(1 << 9) - 1;
public boolean solveSudoku(
char[][] board) {
int[] rowMasks =
new int[SIZE];
int[] columnMasks =
new int[SIZE];
int[] boxMasks =
new int[SIZE];
if (!initialize(
board,
rowMasks,
columnMasks,
boxMasks)) {
return false;
}
return solve(
board,
rowMasks,
columnMasks,
boxMasks);
}
private boolean solve(
char[][] board,
int[] rowMasks,
int[] columnMasks,
int[] boxMasks) {
CellChoice choice =
findBestCell(
board,
rowMasks,
columnMasks,
boxMasks);
if (choice == null) {
return true;
}
if (choice.availableMask()
== 0) {
return false;
}
int row = choice.row();
int column = choice.column();
int box =
boxIndex(
row,
column);
int available =
choice.availableMask();
while (available != 0) {
int bit =
available & -available;
available &=
available - 1;
int digit =
Integer.numberOfTrailingZeros(
bit)
+ 1;
board[row][column] =
(char) ('0' + digit);
rowMasks[row] |= bit;
columnMasks[column] |= bit;
boxMasks[box] |= bit;
if (solve(
board,
rowMasks,
columnMasks,
boxMasks)) {
return true;
}
board[row][column] = '.';
rowMasks[row] ^= bit;
columnMasks[column] ^= bit;
boxMasks[box] ^= bit;
}
return false;
}
private CellChoice findBestCell(
char[][] board,
int[] rowMasks,
int[] columnMasks,
int[] boxMasks) {
CellChoice best = null;
int fewestCandidates =
Integer.MAX_VALUE;
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
if (board[row][column]
!= '.') {
continue;
}
int box =
boxIndex(
row,
column);
int used =
rowMasks[row]
| columnMasks[column]
| boxMasks[box];
int available =
FULL_MASK & ~used;
int count =
Integer.bitCount(
available);
if (count
< fewestCandidates) {
fewestCandidates =
count;
best =
new CellChoice(
row,
column,
available);
if (count <= 1) {
return best;
}
}
}
}
return best;
}
private boolean initialize(
char[][] board,
int[] rowMasks,
int[] columnMasks,
int[] boxMasks) {
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
char value =
board[row][column];
if (value == '.') {
continue;
}
if (value < '1'
|| value > '9') {
return false;
}
int digit =
value - '0';
int bit =
1 << (digit - 1);
int box =
boxIndex(
row,
column);
if ((rowMasks[row] & bit)
!= 0
|| (columnMasks[column]
& bit) != 0
|| (boxMasks[box] & bit)
!= 0) {
return false;
}
rowMasks[row] |= bit;
columnMasks[column] |= bit;
boxMasks[box] |= bit;
}
}
return true;
}
private int boxIndex(
int row,
int column) {
return (row / 3) * 3
+ column / 3;
}
public record CellChoice(
int row,
int column,
int availableMask) {
}
}
Why XOR Works During Removal
Placement sets the bit using:
mask |= bit;
The candidate was previously absent.
Therefore, removal can toggle it off using:
mask ^= bit;
Using this safely depends on the invariant that the bit is currently set exactly once in that constraint group.
For maximum clarity, this can also be written as:
mask &= ~bit;
Bitmask Advantages
- Candidate lookup is extremely fast.
- Candidate sets are represented compactly.
Integer.bitCount()counts candidates quickly.- Candidate iteration avoids scanning all digits.
- MRV integrates naturally.
Bitmask Trade-Offs
- Harder to explain than boolean arrays.
- Bit manipulation mistakes are easy.
- Less readable for beginner-level interviews.
- Generalizing to larger symbol sets requires wider masks.
A strong interview strategy is:
- Explain basic backtracking.
- Optimize with boolean arrays.
- Mention bitmasks as an advanced improvement.
Constraint Propagation
Backtracking guesses values.
Constraint propagation fills values that are already forced before guessing.
Examples include:
- Naked singles
- Hidden singles
Naked Single
A naked single is an empty cell with exactly one possible candidate.
Example:
Cell (4,4) candidates = {5}
The solver can place 5 immediately.
MRV naturally selects these cells first.
Hidden Single
A hidden single occurs when a digit has only one possible location within a:
- Row
- Column
- Box
Even if that cell has multiple candidates, one particular digit is forced there.
Why Constraint Propagation Helps
Suppose ten cells can be filled deterministically before any guess.
Filling them reduces:
- Number of empty cells
- Candidate domains
- Search depth
- Branching factor
Professional Sudoku engines often combine:
Constraint Propagation
+
Backtracking
Simplified Naked Single Pass
public boolean fillNakedSingles(
char[][] board,
int[] rowMasks,
int[] columnMasks,
int[] boxMasks) {
boolean changed = false;
for (int row = 0;
row < 9;
row++) {
for (int column = 0;
column < 9;
column++) {
if (board[row][column]
!= '.') {
continue;
}
int box =
(row / 3) * 3
+ column / 3;
int used =
rowMasks[row]
| columnMasks[column]
| boxMasks[box];
int available =
((1 << 9) - 1)
& ~used;
if (Integer.bitCount(
available) == 1) {
int digit =
Integer.numberOfTrailingZeros(
available)
+ 1;
board[row][column] =
(char) ('0' + digit);
rowMasks[row] |=
available;
columnMasks[column] |=
available;
boxMasks[box] |=
available;
changed = true;
}
}
}
return changed;
}
A complete propagation engine must carefully record changes so they can be undone during backtracking.
That rollback requirement makes production implementations more complex.
Candidate Ordering
The basic solver tries digits:
1 through 9
Alternative candidate ordering may improve the chance of finding a solution earlier.
Possible heuristics include:
- Least constraining value
- Most frequent missing digit
- Digit affecting the fewest neighboring cells
For standard Sudoku, MRV usually provides a more meaningful improvement than complex digit ordering.
Detecting Multiple Solutions
A Sudoku puzzle is typically expected to have exactly one solution.
To detect multiple solutions:
- Continue searching after the first solution.
- Count completed boards.
- Stop when the count reaches
2.
There is no need to enumerate every solution if the goal is only to determine uniqueness.
Java Code — Count Up to Two Solutions
public class SudokuSolutionCounter {
private static final int SIZE = 9;
public int countSolutionsUpToTwo(
char[][] board) {
int[] rowMasks =
new int[SIZE];
int[] columnMasks =
new int[SIZE];
int[] boxMasks =
new int[SIZE];
if (!initialize(
board,
rowMasks,
columnMasks,
boxMasks)) {
return 0;
}
return count(
board,
rowMasks,
columnMasks,
boxMasks,
2);
}
private int count(
char[][] board,
int[] rowMasks,
int[] columnMasks,
int[] boxMasks,
int limit) {
CellChoice choice =
findBestCell(
board,
rowMasks,
columnMasks,
boxMasks);
if (choice == null) {
return 1;
}
if (choice.availableMask()
== 0) {
return 0;
}
int row = choice.row();
int column = choice.column();
int box =
(row / 3) * 3
+ column / 3;
int available =
choice.availableMask();
int total = 0;
while (available != 0
&& total < limit) {
int bit =
available & -available;
available &=
available - 1;
int digit =
Integer.numberOfTrailingZeros(
bit)
+ 1;
board[row][column] =
(char) ('0' + digit);
rowMasks[row] |= bit;
columnMasks[column] |= bit;
boxMasks[box] |= bit;
total += count(
board,
rowMasks,
columnMasks,
boxMasks,
limit - total);
board[row][column] = '.';
rowMasks[row] &=
~bit;
columnMasks[column] &=
~bit;
boxMasks[box] &=
~bit;
}
return total;
}
private CellChoice findBestCell(
char[][] board,
int[] rowMasks,
int[] columnMasks,
int[] boxMasks) {
CellChoice best = null;
int bestCount =
Integer.MAX_VALUE;
int fullMask =
(1 << 9) - 1;
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
if (board[row][column]
!= '.') {
continue;
}
int box =
(row / 3) * 3
+ column / 3;
int available =
fullMask
& ~(rowMasks[row]
| columnMasks[column]
| boxMasks[box]);
int count =
Integer.bitCount(
available);
if (count < bestCount) {
bestCount = count;
best =
new CellChoice(
row,
column,
available);
if (count == 0) {
return best;
}
}
}
}
return best;
}
private boolean initialize(
char[][] board,
int[] rowMasks,
int[] columnMasks,
int[] boxMasks) {
for (int row = 0;
row < SIZE;
row++) {
for (int column = 0;
column < SIZE;
column++) {
char value =
board[row][column];
if (value == '.') {
continue;
}
if (value < '1'
|| value > '9') {
return false;
}
int digit =
value - '0';
int bit =
1 << (digit - 1);
int box =
(row / 3) * 3
+ column / 3;
if ((rowMasks[row] & bit)
!= 0
|| (columnMasks[column]
& bit) != 0
|| (boxMasks[box] & bit)
!= 0) {
return false;
}
rowMasks[row] |= bit;
columnMasks[column] |= bit;
boxMasks[box] |= bit;
}
}
return true;
}
public record CellChoice(
int row,
int column,
int availableMask) {
}
}
Uniqueness Result
Interpret the count:
0 → No solution
1 → Unique solution
2 → Multiple solutions
The method stops counting after two because larger counts are unnecessary for uniqueness validation.
Sudoku Board Validator
A validator checks whether a partially filled board is currently valid.
It does not need to determine whether the puzzle is solvable.
Java Code — Efficient Validator
public class ValidSudoku {
public boolean isValidSudoku(
char[][] board) {
if (board == null
|| board.length != 9) {
return false;
}
int[] rowMasks =
new int[9];
int[] columnMasks =
new int[9];
int[] boxMasks =
new int[9];
for (int row = 0;
row < 9;
row++) {
if (board[row] == null
|| board[row].length
!= 9) {
return false;
}
for (int column = 0;
column < 9;
column++) {
char value =
board[row][column];
if (value == '.') {
continue;
}
if (value < '1'
|| value > '9') {
return false;
}
int digit =
value - '0';
int bit =
1 << (digit - 1);
int box =
(row / 3) * 3
+ column / 3;
if ((rowMasks[row] & bit)
!= 0
|| (columnMasks[column]
& bit) != 0
|| (boxMasks[box] & bit)
!= 0) {
return false;
}
rowMasks[row] |= bit;
columnMasks[column] |= bit;
boxMasks[box] |= bit;
}
}
return true;
}
}
Validator vs Solver
| Validator | Solver |
|---|---|
| Checks current consistency | Completes missing values |
| No recursive search required | Uses backtracking |
| O(81) for standard board | Exponential worst case |
| Returns boolean | Modifies or returns solved board |
| Does not prove solvability | Searches for a solution |
A valid partial board can still be unsolvable.
Generating a Sudoku Puzzle
A simplified Sudoku generator typically follows these steps:
- Generate a complete valid board.
- Remove selected digits.
- Check whether the puzzle still has a unique solution.
- Restore digits when uniqueness is lost.
- Continue until the desired clue count or difficulty is reached.
Generate a Complete Board
A solver can generate a complete board by:
- Starting with an empty board
- Randomizing candidate order
- Using backtracking
Without randomization, the same board may be generated repeatedly.
Remove Digits Carefully
Removing clues arbitrarily can produce:
- Multiple solutions
- No solution
- A puzzle that is too easy
- A puzzle that is extremely hard
After removing each clue, count solutions up to two.
Keep the removal only when exactly one solution remains.
Simplified Generator Flow
graph TD
Generate_Full_Valid_Grid["Generate Full Valid Grid"] --> Shuffle_Cell_Order["Shuffle Cell Order"]
Shuffle_Cell_Order["Shuffle Cell Order"] --> Remove_One_Clue["Remove One Clue"]
Remove_One_Clue["Remove One Clue"] --> Count_Solutions["Count Solutions"]
Count_Solutions["Count Solutions"] --> Exactly_One["Exactly One?"]
Exactly_One["Exactly One?"] --> Continue["Continue"]
Production Puzzle Generation Concerns
A real generator must consider:
- Unique solution
- Difficulty level
- Symmetry
- Solving techniques required
- Number of clues
- Generation time
- Randomness quality
Difficulty is not determined only by the number of empty cells.
It also depends on the reasoning techniques required to solve the puzzle.
Parallel Search Discussion
Backtracking branches are logically independent after different candidate choices.
However, parallel Sudoku solving is often unnecessary because:
- Standard puzzles are small.
- Strong heuristics solve most boards quickly.
- Task scheduling overhead can exceed useful work.
- The first solution should cancel other tasks.
- Shared board state must be copied.
Parallel search is more relevant for:
- Large batches of puzzles
- Puzzle generation
- Solution counting
- Generalized Sudoku boards
Better Parallelization Strategy
Instead of parallelizing recursive branches for one puzzle, process independent puzzles concurrently.
Puzzle 1 → Worker 1
Puzzle 2 → Worker 2
Puzzle 3 → Worker 3
This avoids shared recursive state and provides more predictable scaling.
Generalized Sudoku
Standard Sudoku is:
9 × 9
with:
3 × 3
boxes.
A generalized Sudoku may use:
N² × N²
boards with:
N × N
boxes.
Examples:
| Box Size | Board Size |
|---|---|
| 2×2 | 4×4 |
| 3×3 | 9×9 |
| 4×4 | 16×16 |
Generalized Complexity
For a board with:
M
symbols and:
E
empty cells, a loose bound is:
O(M^E)
Bitmask representation must use a type large enough for M bits.
For more than 64 symbols, use:
BitSet- Boolean arrays
- Arbitrary-precision bit structures
Production API Design
A production Sudoku service should clearly separate:
- Validation
- Solving
- Uniqueness checking
- Puzzle generation
- Difficulty analysis
Possible API:
public interface SudokuService {
boolean isValid(
char[][] board);
boolean solve(
char[][] board);
int countSolutions(
char[][] board,
int limit);
boolean hasUniqueSolution(
char[][] board);
}
Transactional Solving
To avoid modifying an invalid or unsolvable caller board:
- Validate the input.
- Copy the board.
- Solve the copy.
- Copy back only on success.
This provides safer behavior for enterprise APIs.
Thread Safety
A solver is thread-safe when all mutable state is method-local.
Avoid storing arrays such as:
rowMasks
columnMasks
boxMasks
as shared instance fields unless a new solver instance is created per request.
Best practice:
Keep recursive state local to the solve request.
Cancellation and Timeouts
Difficult or generalized puzzles may require execution limits.
Possible safeguards:
- Deadline checks
- Maximum recursion nodes
- Thread interruption
- Request cancellation
- Puzzle size limits
Node Limit Example
public final class SearchBudget {
private long remainingNodes;
public SearchBudget(
long maximumNodes) {
this.remainingNodes =
maximumNodes;
}
public void consume() {
remainingNodes--;
if (remainingNodes < 0) {
throw new IllegalStateException(
"Search budget exceeded");
}
}
}
Call:
budget.consume();
at each recursive node.
Common Optimization Mistakes
Mistake 1 — Forgetting to Initialize Fixed Digits
Constraint arrays or masks must include all original puzzle clues before search begins.
Mistake 2 — Incorrect Box Index
Correct:
(row / 3) * 3
+ column / 3
Mistake 3 — Not Restoring Masks
If a candidate fails, clear its row, column, and box state.
Mistake 4 — Using XOR Without Maintaining the Invariant
XOR removal assumes the bit is currently set exactly once.
Use:
mask &= ~bit;
when explicit clearing is easier to reason about.
Mistake 5 — Selecting the Cell with the Most Candidates
MRV requires the fewest candidates, not the most.
Mistake 6 — Treating Zero Candidates as Success
An empty cell with zero candidates represents a contradiction.
Return:
false
Mistake 7 — Confusing Validity with Solvability
A board can have no immediate duplicates and still have no complete solution.
Mistake 8 — Continuing After Two Solutions During Uniqueness Checking
If the goal is only to determine uniqueness, stop at two.
Mistake 9 — Mutating the Caller Board During Validation
A validator should normally be read-only.
Mistake 10 — Assuming More Empty Cells Always Means Harder
Puzzle difficulty depends on constraint structure, not only clue count.
Senior-Level Interview Questions
Why Does MRV Improve Performance?
MRV chooses the variable with the smallest candidate domain.
This tends to expose contradictions earlier and reduces branching near the top of the search tree.
Is Sudoku NP-Complete?
Generalized Sudoku is NP-complete.
Standard 9 × 9 Sudoku has a fixed finite board size, so complexity discussions usually refer to generalized Sudoku or practical exponential backtracking behavior.
Why Is Memoization Usually Not Helpful?
A Sudoku state is defined by the entire partial board or equivalent masks.
Different paths rarely reach the exact same meaningful state because assignments are position-specific.
Storing full board states would require substantial memory.
Constraint propagation and variable-ordering heuristics usually provide more value.
Can Exact Cover Solve Sudoku?
Yes.
Sudoku can be transformed into an exact-cover problem with constraints for:
- Cell assignment
- Row-digit placement
- Column-digit placement
- Box-digit placement
Algorithm X with Dancing Links is a well-known alternative.
Backtracking remains easier to explain in most coding interviews.
What Is the Difference Between Forward Checking and MRV?
Forward checking removes invalid candidates after each assignment and detects empty domains.
MRV chooses the variable with the smallest remaining domain.
They are complementary techniques.
How Would You Return All Solutions?
Replace early success propagation with result collection.
At every complete board:
results.add(
copyBoard(board));
Then continue backtracking.
Be careful because the number of solutions can be large.
How Would You Find Whether a Puzzle Is Unique?
Count solutions with an upper limit of two.
0means unsolvable.1means unique.2means multiple solutions.
How Would You Improve Candidate Iteration?
Use a bitmask of available candidates.
Instead of testing all digits from 1 through 9, iterate only set bits.
Why Is In-Place Solving Useful?
It reduces allocation and simplifies recursive state.
However, production APIs may prefer solving a copy to avoid exposing partial modifications if the operation fails or is cancelled.
How Would You Benchmark Solvers?
Use a representative dataset containing:
- Easy puzzles
- Medium puzzles
- Hard puzzles
- Unsolvable boards
- Multiple-solution boards
Measure:
- Runtime
- Recursive nodes
- Backtracks
- Allocation rate
- Maximum recursion depth
Use JMH for controlled Java benchmarks.
Strong Senior-Level Explanation
I first initialize row, column, and box constraint structures from the original clues. During recursion, I choose an empty cell, ideally using the Minimum Remaining Values heuristic. I compute its available candidates through constant-time lookup or bitmasks. For each candidate, I update the board and all three constraint structures, recurse, and restore the state if the branch fails. When no empty cell remains, the puzzle is solved. MRV reduces the branching factor by selecting the most constrained cell, while bitmasks make candidate computation and iteration efficient.
Additional Unit Tests — Optimized Solver
import static org.junit.jupiter.api.Assertions.assertTrue;
import org.junit.jupiter.api.Test;
class SudokuSolverOptimizedTest {
private final SudokuSolverOptimized solver =
new SudokuSolverOptimized();
private final ValidSudoku validator =
new ValidSudoku();
@Test
void shouldSolveAndProduceValidBoard() {
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'}
};
assertTrue(
solver.solveSudoku(board));
assertTrue(
validator.isValidSudoku(board));
}
}
Unit Test — Invalid Initial Board
import static org.junit.jupiter.api.Assertions.assertFalse;
import org.junit.jupiter.api.Test;
class InvalidSudokuTest {
private final SudokuSolverOptimized solver =
new SudokuSolverOptimized();
@Test
void shouldRejectDuplicateInRow() {
char[][] board = {
{'5', '3', '5', '.', '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'}
};
assertFalse(
solver.solveSudoku(board));
}
}
Unit Test — Bitmask Solver
import static org.junit.jupiter.api.Assertions.assertTrue;
import org.junit.jupiter.api.Test;
class SudokuSolverBitmaskTest {
private final SudokuSolverBitmask solver =
new SudokuSolverBitmask();
private final ValidSudoku validator =
new ValidSudoku();
@Test
void shouldSolveUsingBitmasks() {
char[][] board = {
{'.', '.', '9', '7', '4', '8', '.', '.', '.'},
{'7', '.', '.', '.', '.', '.', '.', '.', '.'},
{'.', '2', '.', '1', '.', '9', '.', '.', '.'},
{'.', '.', '7', '.', '.', '.', '2', '4', '.'},
{'.', '6', '4', '.', '1', '.', '5', '9', '.'},
{'.', '9', '8', '.', '.', '.', '3', '.', '.'},
{'.', '.', '.', '8', '.', '3', '.', '2', '.'},
{'.', '.', '.', '.', '.', '.', '.', '.', '6'},
{'.', '.', '.', '2', '7', '5', '9', '.', '.'}
};
assertTrue(
solver.solveSudoku(board));
assertTrue(
validator.isValidSudoku(board));
}
}
Unit Test — Unique Solution Detection
import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.api.Test;
class SudokuSolutionCounterTest {
private final SudokuSolutionCounter counter =
new SudokuSolutionCounter();
@Test
void shouldDetectUniqueSolution() {
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'}
};
assertEquals(
1,
counter.countSolutionsUpToTwo(
board));
}
}
Unit Test — Validator
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;
import org.junit.jupiter.api.Test;
class ValidSudokuTest {
private final ValidSudoku validator =
new ValidSudoku();
@Test
void shouldAcceptValidPartialBoard() {
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'}
};
assertTrue(
validator.isValidSudoku(board));
}
@Test
void shouldRejectDuplicateInBox() {
char[][] board = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '5', '.', '1', '9', '.', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
assertFalse(
validator.isValidSudoku(board));
}
}
Approach Comparison
| Approach | Candidate Validation | Cell Selection | Main Benefit |
|---|---|---|---|
| Basic board scanning | O(1) fixed board, repeated scans | First empty cell | Easiest to explain |
| Boolean lookup arrays | O(1) | Sequential | Clear and efficient |
| Precomputed empty cells | O(1) | Fixed empty order | Avoids scanning clues |
| MRV + boolean arrays | O(1) | Fewest candidates | Strong pruning |
| Bitmask + MRV | O(1) bit operations | Fewest candidates | Best compact optimization |
| Exact cover | Specialized | Constraint-driven | Advanced solver technique |
Final Complexity Discussion
Let:
E = number of empty cells
and let the average number of candidates per selected cell be:
B
A practical search description is:
O(B^E)
The loose worst-case bound is:
O(9^E)
Strong constraints and MRV reduce B significantly.
For standard Sudoku, the board size is fixed, so lookup structures use constant memory.
Final Summary
The Sudoku Solver problem demonstrates how backtracking can solve a highly constrained assignment problem.
The basic algorithm:
graph TD
Find_Empty_Cell["Find Empty Cell"] --> Try_Digits["Try Digits"]
Try_Digits["Try Digits"] --> Validate["Validate"]
Validate["Validate"] --> Place["Place"]
Place["Place"] --> Recurse["Recurse"]
Recurse["Recurse"] --> Undo_on_Failure["Undo on Failure"]
The optimized algorithm maintains row, column, and box constraints so candidate validation becomes constant time.
Further improvements include:
- Precomputing empty cells
- Selecting the most constrained cell
- Representing candidates with bitmasks
- Propagating forced assignments
- Stopping solution counting after two
The worst-case search remains exponential, but strong pruning makes standard Sudoku solving practical.
Key Takeaways
- Sudoku is a constraint-satisfaction problem.
- Each empty cell is a variable.
- Candidate digits form the variable’s domain.
- Rows, columns, and boxes define constraints.
- Use backtracking to try assignments.
- Restore every state change after a failed branch.
- Boolean arrays provide constant-time validation.
- The box index is
(row / 3) * 3 + column / 3. - Precompute empty cells to avoid repeated board scanning.
- MRV chooses the cell with the fewest candidates.
- MRV exposes contradictions earlier.
- Bitmasks compactly represent used and available digits.
- Use
Integer.bitCount()to count candidates. - Iterate candidate bits instead of all digits.
- Constraint propagation can fill forced cells before guessing.
- A valid board is not necessarily solvable.
- Count up to two solutions to test uniqueness.
- Stop after the first solution for LeetCode #37.
- Solve a copy when transactional behavior is required.
- Keep recursive state request-local for thread safety.
- Generalized Sudoku has exponential complexity.
- The same pattern applies to scheduling, timetables, and configuration systems.
Sudoku Solver Interview Checklist
Before an interview, be prepared to explain:
- Why Sudoku requires backtracking
- The recursive base condition
- Why the solver returns boolean
- Row, column, and box validation
- The box start and box index formulas
- State restoration
- Worst-case complexity
- Boolean lookup optimization
- Empty-cell precomputation
- MRV heuristic
- Bitmask candidate calculation
- Candidate-bit iteration
- Initial board validation
- Unsolvable puzzle handling
- Multiple-solution detection
- Transactional solving
- Sudoku generation basics
- Exact cover as an advanced alternative