Sudoku Solver
- 2 hours ago
- 11 min read
Enforcing Constraints Without Losing Control
Sudoku Solver looks overwhelming because the board is big and the rules feel strict. That's exactly why interviewers like it. It tests whether you can manage many constraints simultaneously while still writing clean, controlled backtracking code. If you've internalized N-Queens, the structure here will feel familiar. This is the same pattern, scaled up and with more constraint types to track.
Problem Statement
Write a function that solves a Sudoku puzzle by filling the empty cells.
The board is a 9×9 grid where:
Empty cells are represented by '.'
Each row must contain digits 1–9 exactly once
Each column must contain digits 1–9 exactly once
Each of the nine 3×3 sub-boxes must contain digits 1–9 exactly once
You must modify the board in place. There is exactly one valid solution.
1. Clarify Requirements Before Jumping Into Code
Before touching code, restate the rules clearly.
Input: A char[][] board with digits '1'–'9' and '.' for empty cells.
Output: No return value - modify the board in place.
Key clarifications:
There is exactly one valid solution. This matters for control flow. As soon as we find it, we can stop.
We're solving, not validating. Assume the input is a legal (possibly partially filled) Sudoku puzzle.
In-place modification means we need careful rollback. When we backtrack, we must restore the cell to '.' and undo the constraint updates.
The three constraint types, stated precisely:
Row constraint: digit d can appear at most once in each row.
Column constraint: digit d can appear at most once in each column.
Box constraint: digit d can appear at most once in each 3×3 sub-box.
All three must hold simultaneously for every placement.
2. Identify the Category of the Problem
This is backtracking with constraint tracking, the same category as N-Queens, scaled up in two ways: more cells (81 vs. n), and more constraint types (three vs. two).
The structure is identical: make a placement, check constraints, recurse, undo on failure. What's new is engineering the constraint checks to be fast enough that the algorithm stays practical despite the larger search space.
3. Start With Brute Force to Build Intuition
The naive approach: for each empty cell, try every digit 1–9. After filling all cells, check whether the board is valid. Repeat for all combinations.
With up to 81 empty cells and 9 choices each, that's up to 9⁸¹ combinations, a number so large it's essentially meaningless to compute. Even if most are eliminated quickly, this is completely infeasible without pruning.
But the brute force reveals the right question: how early can we detect that a placement is invalid? The answer determines how aggressively we prune the search tree. Place a digit that violates a constraint and we should know immediately, not after filling 40 more cells.
4. Brainstorm More Solutions
Step 1: Reframe as a Sequence of Decisions
Just as N-Queens became "choose a column for each row," Sudoku becomes "choose a digit for each empty cell." We process cells one at a time, left to right, top to bottom. When we hit an empty cell, we try digits 1–9. If a digit is valid, we place it and move to the next cell. If we exhaust all digits without finding a valid one, we backtrack.
When we reach cell index 81 (past the last cell), the board is fully filled and valid.
Step 2: The Core Question - How Do We Check Constraints Fast?
For each candidate digit at (row, col), we need to verify three things:
This digit isn't already in row.
This digit isn't already in col.
This digit isn't already in the 3×3 box containing (row, col).
The naive way approach would be to scan the row (9 cells), scan the column (9 cells), and scan the box (9 cells), which amounts to 27 comparisons per candidate, times 9 candidates per cell, times up to 81 cells. That's a lot of redundant work.
Can we do better? Think about what we did in N-Queens. Instead of scanning all previous queens to check attacks, we maintained sets that let us answer "is this diagonal occupied?" in O(1). Can we apply the same idea here?
Yes! We can maintain boolean arrays that track which digits are already used in each row, column, and box. Before placing digit d at (row, col), check three array lookups. That's O(1) per check regardless of how filled the board is.
Step 3: Design the Constraint Trackers
We need three 2D boolean arrays:
rows[r][d] = true if digit d is used in row r
cols[c][d] = true if digit d is used in column c
boxes[b][d] = true if digit d is used in box b
Where d ranges from 1 to 9 (we'll use arrays of size 10 to avoid index arithmetic, and just ignore index 0).
Before backtracking begins, scan the pre-filled cells and initialize all three arrays. Then every constraint check during backtracking is three array lookups.
Step 4: The Box Index - How Do We Identify Which Box a Cell Belongs To?
Thinking about boxes, we run into another problem. How do we identify which box a cell belongs to? We know there are nine 3×3 boxes, laid out in a 3×3 arrangement, but the input is provided as just one large 2D array. We need a single number - lets say 0 through 8 - that uniquely identifies which box a given cell belongs to.
Let's start by focusing on the rows. Row 0, 1, and 2 all belong to the top band of boxes. Rows 3, 4, 5 belong to the middle band. Rows 6, 7, 8 belong to the bottom band. If we divide our row number by 3 using integer division, we find that gives us either 0, 1, or 2 regardless of which specific row within the band.
The same is true for columns. Columns 0, 1, 2 belong to the left group. Columns 3, 4, 5 belong to the middle group. Columns 6, 7, 8 belong to the right group. So if we create column groups by diving col / 3 - again we get 0, 1, or 2.
Now we have two numbers - a row-band (0, 1, or 2) and a column-group (0, 1, or 2) - and we need to combine them into a single box index from 0 to 8.
Let's think about the top rows of boxes first: row-band 0, column-groups 0, 1, 2. We want those groups to map to boxes with indices 0, 1, 2. But notice that 0, 1, 2 are the exact indices of our column-groups, which means whatever we're doing with the rowGroups in our equation needs to zero out. Since our rowGroup here is 0, that may mean we're using multiplication somehow - maybe something like 0 * ? + colGroup, which results in 0, 1, 2 regardless of what the ? is.
Now think about the middle rows of boxes: row-band 1, column-groups 0, 1, 2. We want those to map to box indices 3, 4, 5. Notice that's just the top row shifted up by 3. So we need rowGroup to contribute exactly 3 to our result when it's 1 - meaning the ? we were considering earlier is probably a 3.
Check the bottom row: row-band 2, column-groups 0, 1, 2 should give 6, 7, 8. With rowGroup 3, that's 2 * 3 = 6, then we add the column-group to get 6, 7, or 8. That works.
So the formula is:
boxIndex = (row / 3) * 3 + (col / 3)Let's verify: cell (4, 7) - row group is 4/3 = 1, col group is 7/3 = 2, box index is 1*3 + 2 = 5. That's the middle-right box. Correct.
This formula - the same kind of coordinate-to-index mapping we used for diagonals in N-Queens - turns a 2D position into a single identifier we can use as an array index.
Step 5: Trace Through a Small Example
Suppose we're solving this partial board and we've processed cells 0–17 (the first two rows). Now we're at cell 18 - position (2, 0) - which is empty.
We try digit 1: check rows[2][1], cols[0][1], boxes[6][1]. Suppose column 0 already has a 1 (from row 0). cols[0][1] is true — skip.
We try digit 2: all three checks pass. Place '2' at (2, 0). Update rows[2][2] = cols[0][2] = boxes[6][2] = true. Recurse to cell 19.
If the recursion eventually returns false (no valid completion exists), we backtrack: restore (2, 0) to '.', set rows[2][2] = cols[0][2] = boxes[6][2] = false, and try digit 3.
The rollback is exact - three assignments to set flags false, one assignment to restore the cell. Nothing else changes.
Step 6: When Do We Return True vs. False?
This problem has a different control flow than Subsets or N-Queens, where we always explored the full tree. Here, there's exactly one solution and we want to stop as soon as we find it.
That means our backtracking function returns a boolean:
true means "I found a valid completion from this point - propagate success upward."
false means "no valid completion exists from this point - backtrack and try something else."
When a recursive call returns true, we immediately return true ourselves without trying other digits. This short-circuits the search as soon as the solution is found.
Step 7: Complexity Analysis
The time complexity is the trickiest part of this problem to analyze precisely. Let's build up to it from scratch.
In the worst case, every cell is empty and we must try digits for each one. There are 81 cells and up to 9 candidates per cell, which gives a naive upper bound of O(9^81). But that's a vast overestimate - it assumes every digit is valid at every cell, which the constraints make impossible.
Think about what the constraints actually enforce. Each row, column, and box can contain each digit at most once. So at any given empty cell, the number of valid candidates isn't 9 - it's 9 minus the digits already present in its row, column, and box. In a densely filled board, this might be 1 or 2. Even in a sparse board, the three overlapping constraints together typically eliminate most candidates.
A tighter way to think about it: the board has 81 cells, and at each step we're effectively choosing from at most 9 options - but realistically far fewer due to constraint propagation. The most widely cited theoretical bound for backtracking Sudoku solvers is approximately O(9^(n)) where n is the number of empty cells, with the understanding that the effective branching factor is much less than 9 in practice. Some analyses tighten this further to roughly O(9^(81/9)) = O(9^9) ≈ O(387 million) by observing that constraints between rows, columns, and boxes limit how independently cells can actually vary - but this is an approximation that assumes uniform constraint density.
The honest answer is that Sudoku's worst-case complexity is an open research question, and the theoretical bounds are loose. What matters for interviews is being able to say: the naive bound is O(9^81), the constraints reduce the effective branching factor dramatically, and in practice the algorithm runs in milliseconds on any valid puzzle because most branches are pruned within the first few levels of recursion.
5. Trade-Offs at a Glance
Approach | Time | Space | Notes |
Brute force | O(9^81) | O(1) | Completely infeasible |
Backtracking, slow checks | Exponential | O(1) | Correct but slow |
Backtracking + constraint arrays | Exponential | O(1) extra | Practical; standard solution |
6. Pseudocode
initialize rows[9][10], cols[9][10], boxes[9][10] to false
scan pre-filled cells:
for each (r, c) where board[r][c] != '.':
d = board[r][c] - '0'
rows[r][d] = cols[c][d] = boxes[boxIndex(r,c)][d] = true
backtrack(cellIndex):
if cellIndex == 81:
return true ← all cells filled, solution found
row = cellIndex / 9
col = cellIndex % 9
if board[row][col] != '.':
return backtrack(cellIndex + 1) ← pre-filled, skip
box = boxIndex(row, col)
for d from 1 to 9:
if rows[row][d] or cols[col][d] or boxes[box][d]:
continue ← constraint violated, skip
board[row][col] = '0' + d
rows[row][d] = cols[col][d] = boxes[box][d] = true
if backtrack(cellIndex + 1):
return true ← solution found, propagate up
board[row][col] = '.'
rows[row][d] = cols[col][d] = boxes[box][d] = false
return false ← no digit worked, backtrack
boxIndex(row, col):
return (row / 3) * 3 + (col / 3)7. Edge Cases
Already solved board: Every cell is pre-filled. The recursion skips all cells and returns true immediately at cell 81.
Nearly solved board: One or two empty cells. The algorithm fills them quickly, likely on the first or second try.
Many empty cells: The constraint arrays do the heavy lifting — most candidates are eliminated immediately, keeping the search tree manageable.
Deep backtracking required: Some puzzles are designed to require many backtracks before the solution is found. The algorithm handles this correctly — rollback is exact, so no state leaks between branches.
8. Full Solution
public class SudokuSolver {
private static boolean[][] rows = new boolean[9][10];
private static boolean[][] cols = new boolean[9][10];
private static boolean[][] boxes = new boolean[9][10];
public static void solveSudoku(char[][] board) {
// Initialize constraint arrays from pre-filled cells
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] != '.') {
int d = board[r][c] - '0';
int b = getBoxIndex(r, c);
rows[r][d] = cols[c][d] = boxes[b][d] = true;
}
}
}
backtrack(board, 0);
}
private static boolean backtrack(char[][] board, int cell) {
if (cell == 81) return true; // sudoku solved
int row = cell / 9;
int col = cell % 9;
if (board[row][col] != '.') {
return backtrack(board, cell + 1); // pre-filled, skip
}
int box = getBoxIndex(row, col);
for (int d = 1; d <= 9; d++) {
if (rows[row][d] || cols[col][d] || boxes[box][d])
continue;
// Place digit
board[row][col] = (char) ('0' + d);
rows[row][d] = cols[col][d] = boxes[box][d] = true;
// solution found
if (backtrack(board, cell + 1)) return true;
// Undo placement
board[row][col] = '.';
rows[row][d] = cols[col][d] = boxes[box][d] = false;
}
return false; // no valid digit — trigger backtrack
}
private static int getBoxIndex(int row, int col) {
return (row / 3) * 3 + (col / 3);
}
}The rollback symmetry is the same as N-Queens: every assignment before the recursive call is mirrored by an undo after it. Three flags set → three flags cleared. One cell filled → one cell restored. If you ever touch state asymmetrically, you'll have a subtle bug that only manifests deep in the recursion.
9. Test Your 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'}
};
solveSudoku(board);
// Verify the solution:
for (char[] row : board) {
System.out.println(new String(row));
}
// Expected:
// 534678912
// 672195348
// 198342567
// 859761423
// 426853791
// 713924856
// 961537284
// 287419635
// 34528617910. Key Lessons for Future Problems
Constraint tracking is what separates strategy from brute force. The backtracking skeleton is simple. What makes Sudoku Solver a real engineering problem is designing constraint checks that are fast enough to prune aggressively. Three O(1) lookups per candidate versus 27 comparisons is the difference between a practical algorithm and a slow one.
Precompute from the initial state. The pre-filled cells define the starting constraints. Initializing the boolean arrays before backtracking begins means those constraints are always reflected - you never have to special-case pre-filled cells during the recursion (beyond skipping them).
The box index formula is worth deriving, not memorizing. (row / 3) * 3 + (col / 3) converts a 2D position to a box number. Understand why: integer division groups rows into bands of 3, and the formula combines the row-band and column-band into a single index 0–8. If you forget it under pressure, you can re-derive it in 30 seconds by thinking about what "which box am I in?" means geometrically.
Return-value backtracking is different from void backtracking. In Subsets and N-Queens, the backtracking function was void - it explored the full tree and collected all results. Here, the function returns a boolean because there's exactly one solution and we stop as soon as we find it. Recognizing when to use each form - "collect all results" vs. "find first solution and stop" - is an important skill. When the problem guarantees one solution and you just need to find it, the boolean return lets you short-circuit immediately.
Sudoku and N-Queens are the same pattern at different scales. Both place items one at a time, both check multiple constraint types per placement, both use O(1) constraint lookups with precomputed structures, and both roll back state exactly on failure. If you understand one deeply, the other is straightforward to derive.
Sudoku Solver isn't about filling numbers. It's about managing complexity under pressure - designing clean state, applying constraints aggressively, and trusting the backtracking framework to handle the rest. That's exactly what hard technical interview problems test.
Good Luck and Happy Coding!
Comments