Problem statement
Fill the dots in a 9×9 Sudoku board so each row, column and 3×3 box contains digits 1 through 9 exactly once. Do not change existing clues. The method updates the supplied board in place rather than returning a new board.
LeetCode Sudoku Solver guarantees one solution and supplies digits or .. The algorithm below assumes valid initial clues. It is not a general invalid-board validator; Valid Sudoku is a separate question.
The examples above use nine row strings so the whole input and output remain readable. Each string represents one row of the character matrix.
Constraints & requirements
- CONTRACT
- LeetCode: exactly 9×9, digits or ., and one guaranteed solution. The teaching code assumes valid clues; it is not a general invalid-board validator. The judge method returns void and updates the board.
Examples 3 test cases
Example 1 Case 1
- Input
53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79- Output
534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
Nine row strings describe the board. Fill every dot while preserving the original digits.
Example 2 Case 2
- Input
534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179- Output
Same completed board
No empty cell remains, so no mutation is needed.
Example 3 Case 3
- Input
53.678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179- Output
Replace the first-row dot with 4; other cells unchanged
Row, column and box constraints agree on the single missing digit.
Hints Optional
01Hint 1
Choose the first empty cell and try each digit 1–9.
02Hint 2
A locally legal digit must avoid conflicts in its row, column and 3×3 box.
03Hint 3
If a descendant fails, restore .; if it succeeds, keep the placements and return immediately.
How to think before coding
Find one empty cell, then try each digit that conflicts with no row, column or box entry. A successful child means KEEP the placement and stop. A failed child means restore ‘.’ before another candidate. Finding no empty cell is success under the stated valid-clue assumption. The wrapper updates the same board; it does not return a second solved board.
Brute force and the improvement
If E cells are empty, assign each one a digit 1..9 without checking conflicts until the board is complete. That explores up to 9^E assignments, with a full 81-cell validation per candidate on the fixed 9×9 board and O(E) search frames. Almost all assignments violate a clue much earlier. Check row, column and box before recursing instead. This remains a backtracking search, not a polynomial guarantee; choosing the most-constrained empty cell is an additional heuristic beyond the clear first-empty-cell implementation below.
Intuition: legal locally does not mean solved globally
Choose the first empty cell and ask which digit is currently allowed. A digit must not already occur in its row, column or box.
Placing a legal digit does not prove that all later cells can be filled. If a later cell has no possible completion, false returns to the caller that made the earlier choice. Restore its dot and try the next digit.
This is a search for one complete board. On success, keep the placements. Undoing the successful branch would erase the answer that the caller expects to see.
Algorithm
- Scan for the first dot.
- Try digits 1 through 9, rejecting local conflicts.
- Write a safe digit and recurse on the board.
- If the child succeeds, return true immediately.
- Otherwise restore the dot and try another digit.
- If none completes this cell, return false to the waiting caller.
- If the scan finds no dot, return true.
How does the box formula work?
3*(row/3) and 3*(col/3) identify the upper-left corner of the containing 3×3 box. For i=0..8, i/3 selects its local row and i%3 its local column.
For cell (4,7), the box starts at (3,6). The offsets visit (3,6),(3,7),(3,8),(4,6),…,(5,8). One nine-iteration loop can check the row, column and all box cells without confusing their coordinates.
Java solution
A void public wrapper updates the board; the boolean helper reports success internally. The no-solution exception is defensive behavior outside the guaranteed-solution contract.
import java.util.*;
class Solution {
public static void solveSudoku(char[][] board) {
// Contract: a valid 9x9 puzzle with one solution; modify the provided board.
if (!fillSudoku(board)) throw new IllegalArgumentException("No solution for the supplied puzzle");
}
private static boolean fillSudoku(char[][] board) {
for (int row = 0; row < 9; row++) for (int col = 0; col < 9; col++) {
if (board[row][col] != '.') continue; // Preserve every given clue.
for (char digit = '1'; digit <= '9'; digit++) {
if (!sudokuSafe(board, row, col, digit)) continue; // Check row, column AND box.
board[row][col] = digit; // Choose a locally legal value.
if (fillSudoku(board)) return true; // Keep all successful placements; do not undo them.
board[row][col] = '.'; // Dead end later: restore this cell before another digit.
}
return false; // THIS first empty cell had no successful value; tell the waiting caller.
}
return true; // No empty cell remains; validity follows from valid clues and safe placements.
}
private static boolean sudokuSafe(char[][] board, int row, int col, char digit) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == digit || board[i][col] == digit) return false; // Row and column.
int boxRow = 3 * (row / 3) + i / 3, boxCol = 3 * (col / 3) + i % 3;
if (board[boxRow][boxCol] == digit) return false; // Traverse all nine cells of the correct box.
}
return true; // A local permission to try, not proof the whole puzzle is solvable.
}
public static void main(String[] args) {
char[][] board = {
"53..7....".toCharArray(), "6..195...".toCharArray(), ".98....6.".toCharArray(),
"8...6...3".toCharArray(), "4..8.3..1".toCharArray(), "7...2...6".toCharArray(),
".6....28.".toCharArray(), "...419..5".toCharArray(), "....8..79".toCharArray()
};
solveSudoku(board); // Modifies this board, returns no separate result.
for (char[] row : board) System.out.println(new String(row)); // Solved rows, starting 534678912.
}
}The driver prints the solved nine rows shown in Example 1. Existing clues remain unchanged. A fully filled valid board returns without making any new placements.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: the article’s 9×9 puzzle, whose first row is "53..7...."
What to track: A call scans for the first dot in row-major order. row/col identify that dot; digit is a tentative choice. Long descendant searches below are summarized explicitly, not presented as consecutive instructions.
-
Find the first empty cell
Java operationif (board[row][col] != '.') continue;Staterow = 0; col = 2; board[0][2] = '.'The scan skips the given 5 and 3. A clue is never overwritten.
-
Try the first locally safe digit
Java operationboard[row][col] = digit;Statedigit = '1'; first row becomes "531.7...."sudokuSafe checks the row, column and 3×3 box first. Locally safe means permission to try, not proof the puzzle is solved.
-
Search below this guess
Java operationif (fillSudoku(board)) return true;Statethe child tries later dots; eventually this entire digit-1 subtree returns falseThe known unique solution has 4 at (0,2), so no completion can retain this 1. This row summarizes many recursive calls.
-
Restore the failed guess
Java operationboard[row][col] = '.';Stateresumed caller restores board[0][2]; first row is "53..7...." againFailed descendants have already restored their own dots. This caller restores only the cell it chose.
-
Try 2, then reject 3
Java operationif (!sudokuSafe(board, row, col, digit)) continue;Statedigit 2 is locally safe but its descendant search also fails and is undone; digit 3 conflicts with the existing row clueNo recursive child is created for 3. The next permitted digit at this cell is 4.
-
Keep the successful continuation
Java operationif (fillSudoku(board)) return true;Statechoose 4 at (0,2); eventually no dots remain; the terminal call returns trueEvery waiting caller returns immediately on true, so the chosen digits remain on the board. Undoing on success would erase the solution.
Final result: the complete solved board, with first row "534678912"; all original clues preserved.
The sample’s first dot is (0,2). Its row contains 5,3,7; its column already has 8; its box contains 5,3,6,9,8. The locally allowed candidates are 1,2,4.
first empty cell (0,2) ├─ try 1 → locally safe → explore descendants │ └─ eventually a dead end → false → restore . ├─ try 2 → locally safe → explore descendants │ └─ eventually a dead end → false → restore . └─ try 4 → explore descendants → complete solution → true keep 4 and every later successful placement
This is a summarized tree, not an immediate failure at the very next cell. The supplied puzzle has one solution, whose (0,2) value is 4; the earlier locally legal branches cannot complete it.
| Return from a child | What the caller does | Why |
|---|---|---|
| false | Restore its chosen cell to . |
That digit did not permit a complete solution |
| true | Return true without restoration | The board now holds the answer |
| No empty cell found | Return true | All placements are complete and constraints were preserved |
Each caller remembers the cell whose choice it owns. The next recursive scan does not transfer ownership of that cell to another frame.
Why it works
Given consistent clues, every tentative placement passes all three constraint checks, preserving local Sudoku validity. If there are no empty cells, each nine-cell row, column and box contains nine different digits from 1..9 and therefore contains the whole required set.
At an empty cell, every safe digit is tried. Any full solution extending the current board uses one of those digits, so no solution is missed. Restoring failed placements makes siblings independent. Returning on success preserves the solved board in the original object.
Complexity and alternative approaches
Let E be the initial number of empty cells. A loose worst-case bound is O(9^E) search: each level fills one empty cell and has at most nine digit choices. The 81-cell scan and nine-step safety checks are constants for this fixed 9×9 task, though they affect practical runtime.
Recursive auxiliary space is O(E). The board is modified in place and no alternative boards are copied. For a fixed 9×9 grid, E≤81; parameterizing by E makes the search growth clearer than saying only “constant.”
Row/column/box masks can speed up safety checks. Choosing the empty cell with the fewest legal candidates often prunes more strongly than row-major order. Those optimizations need careful updates and restoration. Merely validating the initial board neither solves it nor proves that it has a completion.
Common mistakes
- Forgetting the box test or using the wrong box offsets.
- Treating the first locally allowed digit as final.
- Undoing after a successful return and erasing the answer.
- Returning false only after scanning unrelated empty cells instead of failing the current choice.
- Claiming that no dots proves an arbitrary invalid starting board is valid; the clue-validity assumption matters.