Sudoku Solver

Problem in Plain English

Fill a uniquely solvable 9 by 9 Sudoku board in place while preserving its clues. Track used digits in each row, column and box, and undo every failed guess.

Problem Statement

Given a 9 by 9 character matrix board, fill every . with a digit from 1 through 9. Each row, each column and each of the nine 3 by 3 boxes must contain each digit exactly once.

The input has exactly one solution. Modify the same board in place; do not return a replacement board or change any clue. Examples below show the matrix as nine row strings for readability; code receives mutable character rows.

Constraints

board.length == 9; every row has length 9.
Each cell is a character from 1 through 9 or ..
The input has exactly one solution.

Examples

Example 1

Input: board rows = ["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]
Output: board rows = ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]

Every original clue is retained. For example, row 0 becomes 534678912, column 0 becomes 561847923, and the top-left box contains 534, 672, 198: each has all digits exactly once.

Example 2

Input: board rows = ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]
Output: board rows = ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]

An already solved board has zero empty cells. The base case succeeds immediately and leaves every character unchanged.

Example 3

Input: board rows = [".34678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]
Output: board rows = ["534678912","672195348","198342567","859761423","426853791","713924856","961537284","287419635","345286179"]

Only (0,0) is empty. Its row, column and box all require digit 5, so one placement completes the unique solution.

Intuition

Validation checks the clues but does not supply missing digits. Solving requires choosing a legal digit, exploring what it forces later, and retracting it if a later cell has no option. In Example 1, the first empty cell (0,2) allows 1, 2 or 4. A locally legal 1 eventually fails, so all affected guesses must be undone before trying 2 and then the correct 4. Three used-digit masks make each legality check constant time.

Approaches

Backtracking Masks

Optimal

Solution Details

Reveal Backtracking Masks: intuition, complexity, and code

Intuition

Try legal digits and undo guesses when a suffix cannot be solved. Cached row, column and box masks remove repeated scans; this is the selected approach for simple constant-time legality checks, not a claim that fixed cell ordering minimizes the search. Choosing the most constrained cell can reduce practical branching further.

Step-by-Step Logic

Read clues into nine row, column and box masks. Store the 51 empty coordinates of Example 1 in row-major order; box index is 3 * floor(r / 3) + floor(c / 3).
At (0,2), compute available bits from the complement of the three masks, restricted to the lowest nine bits. The candidates are 1, 2 and 4.
Choose the lowest available digit 1, write it into the board, and add its bit to all three masks. At (0,3), try 2; at (0,5), try 4.
At (0,6) try 8 and at (0,7) try 9. Now (0,8) has no legal digit. Return false, clear 9 and its three bits, then clear 8 before trying the remaining candidate at (0,6).
Continue depth-first, restoring board and masks after every failed branch. After exhausting the branches rooted at 1 and 2 in (0,2), choose 4 there.
When all empty coordinates are filled, return true through every caller without undoing the successful placements. The final board is the Example 1 solution.

Why It Works

Initially each mask describes exactly the clues in its unit. At every recursive call, earlier empty cells are assigned and their bits are present in the masks; later cells remain dots. A candidate bit is absent from all three relevant masks, so placing it preserves row, column and box uniqueness. If recursion fails, clearing that bit from each mask and restoring the dot reinstates exactly the state before the guess; the bit cannot belong to another cell in those units because placement was legal. The search tries every legal digit for the current cell, so it explores every completion consistent with the clues and skips only assignments that already violate a rule. At the base case all 81 cells are filled without repetitions, which forces every unit to contain all nine digits. Existence guarantees some branch succeeds, and success returns before undo, retaining that unique completed board.

Dry Run

Backtracking Masks: variable states at each step
Event	Cell	Candidate or state	Action
Initialize	51 empty cells	masks contain only clues	start search(0)
First guess	(0,2)	available {1,2,4}	place 1
Descend	(0,3), (0,5)	choose 2, then 4	row begins 531274...
Descend	(0,6), (0,7)	choose 8, then 9	row becomes 53127489.
Dead end	(0,8)	available {}	return false
Undo	(0,7), (0,6)	remove 9, then 8 from board and masks	row restored to 531274...
Remaining search (abridged)	(0,2)	branches for 1 and 2 fail; choose 4	row 0 eventually 534678912
Base case	k=51	all units contain digits 1 through 9	retain board rows [534678912,672195348,198342567,859761423,426853791,713924856,961537284,287419635,345286179]

Complexity Analysis

Time Complexity

O(9^e)

Space Complexity

O(e + 1)

Let e be the initial number of empty cells. Each search level tries at most nine digits with constant-time mask work, so a geometric search-tree bound is O(9^e), plus fixed 81-cell initialization. The empty-coordinate list and recursion use O(e + 1) space; the 27 masks are fixed size. Here e is at most 81, so recursion is safe and the literal fixed-board domain has constant bounded space. This parameterized exponential bound makes the search cost explicit rather than labeling all fixed-size puzzles constant time.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public void solveSudoku(char[][] board) {5        int[] rows = new int[9], cols = new int[9], boxes = new int[9];6        List<int[]> empty = new ArrayList<>();7        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) {8            if (board[r][c] == '.') empty.add(new int[]{r, c});9            else {10                int bit = 1 << (board[r][c] - '1'), b = (r / 3) * 3 + c / 3;11                rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;12            }13        }14        search(board, empty, 0, rows, cols, boxes);15    }16    private boolean search(char[][] board, List<int[]> empty, int k,17                           int[] rows, int[] cols, int[] boxes) {18        if (k == empty.size()) return true;19        int r = empty.get(k)[0], c = empty.get(k)[1], b = (r / 3) * 3 + c / 3;20        int available = 511 & ~(rows[r] | cols[c] | boxes[b]);21        while (available != 0) {22            int bit = available & -available;23            available ^= bit;24            board[r][c] = (char) ('1' + Integer.numberOfTrailingZeros(bit));25            rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;26            if (search(board, empty, k + 1, rows, cols, boxes)) return true;27            rows[r] &= ~bit; cols[c] &= ~bit; boxes[b] &= ~bit;28            board[r][c] = '.';29        }30        return false;31    }32}

Hints

Hint 1

For an empty cell, eliminate digits already used by its row, column and box.

Hint 2

Store those used digits as three masks; compute the box from integer division by 3.

Hint 3

Try a legal digit, recurse to the next empty cell, and restore all three masks and the dot on failure. Stop undoing when a full solution succeeds.

Edge Cases

A solved board needs no placements and must remain unchanged.
A single blank requires one legal digit and a direct base-case return.
A locally legal digit can fail much later; every nested guess must be undone.
No-solution and conflicting-clue inputs are outside the unique-solution contract.

Common Mistakes and Interview Tips

Restoring the board while leaving one mask bit set contaminates sibling branches.
Using r / 3 + c / 3 without multiplying the row group by 3 merges different boxes.
Failing to mask the complement with 511 creates candidates outside digits 1 through 9.
Undoing after a successful recursive return erases the solution.

Key Takeaway

Constraint search works by maintaining an exact partial-state invariant: place one legal choice, explore, and reverse every state change if that choice cannot be completed.