Fill every empty cell of a 9x9 grid so the finished board is a valid Sudoku.
A completed board must satisfy all three rules:
1-9 exactly once.1-9 exactly once.3x3 sub-boxes contains the digits 1-9 exactly once.Empty cells are marked with the character '.'. Fill them in place; the input is guaranteed to have exactly one valid solution.
The board is given as a 9x9 grid of single characters — each is either a digit '1'-'9' or '.'.
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"]] Every row, every column, and every 3x3 box ends up holding the digits 1-9 exactly once. It is the only board that fits the given clues.
- board.length == 9 - board[i].length == 9 - Each board[i][j] is a digit 1-9 or the character '.' marking an empty cell. - The puzzle is guaranteed to have exactly one solution.
Sudoku is the classic stage for backtracking: a search that guesses, recurses, and calmly erases every guess that leads nowhere. We start with the honest brute force, then keep the exact same search but make its one repeated question — is this digit legal here? — almost free.
In plain words: some cells are pre-filled clues, the rest are '.'. Assign a digit 1-9 to every blank so that no digit repeats within any row, any column, or any of the nine 3x3 boxes. The clues never change; you only fill blanks, and exactly one assignment works.
Worked example — the top-left box
given clues: first blank (row 0, col 2):
5 3 . its row already has 5 3 7
6 . . its col already has 8
. 9 8 its box already has 5 3 6 9 8
legal digits left → {1,2,4} → try 1 first
Naming the guarantees out loud before you code is what separates a senior candidate from someone who charges in and rewrites the grid three times.
“Is the board always exactly 9 by 9?”
The 3x3 box arithmetic and the nine-digit alphabet assume it; a ragged grid would break the box index.
“Are the given clues guaranteed to be consistent with each other?”
If two clues already clash, no solution exists and the search must simply report failure rather than loop.
“Could the board be already complete, with no blanks?”
Then the answer is the board itself — the recursion should return immediately.
“Is the solution guaranteed unique?”
Yes here, which means the first full board the search reaches is the answer; no need to enumerate more.
“How many cells can be blank?”
Up to roughly sixty, so a check that costs almost nothing per candidate matters far more than clever cell ordering.
Before I code, a few quick clarifications.
Can I assume the grid is always 9 by 9 with digits or dots only?
And since exactly one solution is guaranteed, I can stop at the first complete board I reach.
The clues are frozen. So the search is a sequence of decisions — one per '.' cell — visited in a fixed order (say row by row). That turns a scary 2-D puzzle into a linear chain of "pick a digit, move to the next blank."
Cell (r, c) belongs to exactly one row, one column, and one box, indexed b = (r / 3) * 3 + c / 3. A digit is placeable precisely when none of those three groups already contain it — three membership questions, nothing more.
r=4, c=7 → box b = (4/3)*3 + 7/3 = 3 + 2 = 5
Keep a bitmask per row, per column, and per box: bit d is on when digit d is used. Legality is ((rows[r] | cols[c] | boxes[b]) >> d) & 1 == 0, and placing or erasing a digit is just flipping bit d in three masks. The search tree is identical to brute force — each node is simply thousands of times cheaper.
| Brute force | Optimal | |
|---|---|---|
| Legality test | scan 27 cells | one bitmask AND |
| Place / undo | write / erase 1 cell | write + flip 3 bits |
| Worst-case time | O(9^m) | O(9^m), tiny constant |
| Extra space | O(1) | O(1) — 27 masks |
Both explore the same tree of guesses; the full code for each lives in the Approaches selector below.
Key takeaway
Backtracking is choose → explore → un-choose. When the same tiny legality check runs millions of times, precompute it into O(1) state (here, three bitmasks) and flip that state on the way down and back up.
solve(cell):
if no blank remains: return true
(r, c) = next blank; b = (r/3)*3 + c/3
for d in 1..9:
if d not in rows[r] | cols[c] | boxes[b]:
place d; set the 3 bits
if solve(next): return true
erase d; clear the 3 bits
return false