Fill In a 9×9 Sudoku Puzzle to Completion
Solve this Problem
Given a partially filled 9×9 Sudoku board, fill in every empty cell so that each digit 1–9 appears exactly once in every row, every column, and every 3×3 box. The puzzle is guaranteed to have exactly one valid completion.
Scanning the whole board from the start to find the next empty cell, and checking a candidate digit by walking the entire row, column, and box arrays, both work — but repeat information the search already had. Passing the next position down directly, and maintaining a table of which digits are already used in each row, column, and box, turns both of those repeated derivations into a single lookup: the exact same tree of choices gets explored, just without re-deriving facts about the board that hadn't changed.
Test Case 1:
Input:board = [".39852746","852746139","746139852","591428367","428367591","367591428","973215684","215684973","684973215"]
Output:["139852746","852746139","746139852","591428367","428367591","367591428","973215684","215684973","684973215"]
Explanation:A single empty cell — its digit is the one value missing from its row, column, and box all at once.
Test Case 2:
Input:board = [".398.274.","852746139","746139852","591428367",".283.759.","367591428","973215684","215684973",".849.321."]
Output:["139852746","852746139","746139852","591428367","428367591","367591428","973215684","215684973","684973215"]
Explanation:9 empty cells scattered across the board, one inside each 3×3 box.
Test Case 3:
Input:board = [".39.52.46","8.27.61.9","746139852",".91.28.67","4.83.75.1","367591428",".73.15.84","2.56.49.3","684973215"]
Output:["139852746","852746139","746139852","591428367","428367591","367591428","973215684","215684973","684973215"]
Explanation:18 empty cells, two per box — enough to require genuine backtracking rather than single-candidate deduction.
Constraints
- ◆
The board is always exactly 9 rows of 9 characters, each either a digit '1'–'9' or '.' for an empty cell - ◆
The given puzzle always has exactly one valid completion - ◆
A completed board must have each digit 1–9 appear exactly once in every row, every column, and every 3×3 box
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Full-Array Checks, Re-Scan the Whole Board Every Call
BruteTo find the next cell to fill, scan the entire board from the very top-left every single time a cell is placed — there's no memory of where the previous search left off. To check whether a digit is legal for a cell, walk the whole row array, the whole column, and the whole 3×3 box array directly, one cell at a time. Both habits are correct but wasteful: placing one digit and then re-scanning all 81 cells just to find the next blank one re-examines dozens of cells that haven't changed since the last call.
Time
O(9^(81) worst case)Space
O(1) extraJava
1class Solution {
2 public String[] solveSudokuBoard(String[] board) {
3 char[][] grid = new char[9][9];
4 for (int r = 0; r < 9; r++) grid[r] = board[r].toCharArray();
5 solve(grid);
6 String[] result = new String[9];
7 for (int r = 0; r < 9; r++) result[r] = new String(grid[r]);
8 return result;
9 }
10
11 private boolean solve(char[][] grid) {
12 for (int r = 0; r < 9; r++) {
13 for (int c = 0; c < 9; c++) {
14 if (grid[r][c] == '.') {
15 for (char d = '1'; d <= '9'; d++) {
16 if (isValid(grid, r, c, d)) {
17 grid[r][c] = d;
18 if (solve(grid)) return true;
19 grid[r][c] = '.';
20 }
21 }
22 return false;
23 }
24 }
25 }
26 return true;
27 }
28
29 private boolean isValid(char[][] grid, int row, int col, char d) {
30 for (int i = 0; i < 9; i++) {
31 if (grid[row][i] == d) return false;
32 if (grid[i][col] == d) return false;
33 }
34 int boxRow = (row / 3) * 3, boxCol = (col / 3) * 3;
35 for (int r = 0; r < 3; r++) {
36 for (int c = 0; c < 3; c++) {
37 if (grid[boxRow + r][boxCol + c] == d) return false;
38 }
39 }
40 return true;
41 }
42}Optimal — Track Used Digits Directly, Advance Without Re-Scanning
OptimalDo two things differently. First, pass the next cell's position down explicitly as a parameter, computed once, instead of re-scanning from the top-left to find it — an already-filled cell is passed straight through with a single check, no loop involved. Second, maintain boolean tables for which digits are already used in each row, column, and box; checking whether a digit is legal becomes three direct lookups instead of three array walks. Everything still explores the same shape of search, but locating the next cell and checking a digit's legality are both O(1) instead of O(board size).
Time
O(9^(81) worst case, far smaller constant factor)Space
O(1) extraJava
1class Solution {
2 public String[] solveSudokuBoard(String[] board) {
3 char[][] grid = new char[9][9];
4 for (int r = 0; r < 9; r++) grid[r] = board[r].toCharArray();
5 boolean[][] rowUsed = new boolean[9][10];
6 boolean[][] colUsed = new boolean[9][10];
7 boolean[][] boxUsed = new boolean[9][10];
8 for (int r = 0; r < 9; r++) {
9 for (int c = 0; c < 9; c++) {
10 if (grid[r][c] != '.') {
11 int d = grid[r][c] - '0';
12 int b = (r / 3) * 3 + (c / 3);
13 rowUsed[r][d] = true;
14 colUsed[c][d] = true;
15 boxUsed[b][d] = true;
16 }
17 }
18 }
19 solve(grid, rowUsed, colUsed, boxUsed, 0, 0);
20 String[] result = new String[9];
21 for (int r = 0; r < 9; r++) result[r] = new String(grid[r]);
22 return result;
23 }
24
25 private boolean solve(char[][] grid, boolean[][] rowUsed, boolean[][] colUsed, boolean[][] boxUsed, int row, int col) {
26 if (row == 9) return true;
27 int nextRow = (col == 8) ? row + 1 : row;
28 int nextCol = (col == 8) ? 0 : col + 1;
29 if (grid[row][col] != '.') {
30 return solve(grid, rowUsed, colUsed, boxUsed, nextRow, nextCol);
31 }
32 int b = (row / 3) * 3 + (col / 3);
33 for (int d = 1; d <= 9; d++) {
34 if (!rowUsed[row][d] && !colUsed[col][d] && !boxUsed[b][d]) {
35 grid[row][col] = (char) ('0' + d);
36 rowUsed[row][d] = colUsed[col][d] = boxUsed[b][d] = true;
37 if (solve(grid, rowUsed, colUsed, boxUsed, nextRow, nextCol)) return true;
38 grid[row][col] = '.';
39 rowUsed[row][d] = colUsed[col][d] = boxUsed[b][d] = false;
40 }
41 }
42 return false;
43 }
44}