Definition
The Sudoku Solver uses constraint backtracking over empty cells.
- Empty cell scan finds the next cell marked with a dot or zero.
- Validity check ensures the digit does not already appear in the same row, column, or 3x3 box.
- Placement writes a valid digit and recurses to the next empty cell.
- Backtracking resets the cell to empty if no digit works, triggering undo in the caller.
- Termination returns true when no empty cells remain, propagating success up the call chain.
Think of a 9-by-9 reconciliation grid at National Bank of India where each row, column, and sub-block must contain each code exactly once. You fill the first blank with a candidate that does not already appear in its row, column, or block, move on, and if you get stuck you erase and try a different candidate.
Understanding the Concepts
What is the Sudoku Solver Problem?
Given a partially filled 9x9 Sudoku board, fill every empty cell so that each row, column, and 3x3 box contains the digits 1 through 9 exactly once. The board is represented as a 2D character array where '.' marks empty cells.
At National Bank of India, Pankaj built a tool that automatically completes a reconciliation grid where each row, column, and sub-block must contain each transaction code exactly once.
package com.bank.service;
public class SudokuSolver {
public static boolean solve(char[][] board) {
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') {
for (char d = '1'; d <= '9'; d++) {
if (isValid(board, r, c, d)) {
board[r][c] = d;
if (solve(board)) return true;
board[r][c] = '.'; // backtrack
}
}
return false; // no digit works: trigger backtracking
}
}
}
return true; // no empty cells: solved
}
private static boolean isValid(char[][] board, int row, int col, char digit) {
int boxRow = (row / 3) * 3;
int boxCol = (col / 3) * 3;
for (int i = 0; i < 9; i++) {
if (board[row][i] == digit) return false; // row check
if (board[i][col] == digit) return false; // column check
if (board[boxRow + i / 3][boxCol + i % 3] == digit) return false; // box check
}
return true;
}
public static void main(String[] args) {
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'}
};
if (solve(board)) {
System.out.println("Solved:");
printBoard(board);
}
}
private static void printBoard(char[][] board) {
for (char[] row : board) {
System.out.println(new String(row));
}
}
}
Solved:
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
Why Does This Problem Matter?
Sudoku is the canonical example of constraint satisfaction with backtracking. It demonstrates how to combine constraint checking with exhaustive search. The technique applies to any problem where you must assign values to positions subject to overlapping constraints: scheduling, resource allocation, and configuration validation.
package com.bank.service;
public class ConstraintSatisfactionPattern {
// Same pattern applies to:
// - N-Queens: row, column, diagonal constraints
// - Graph coloring: adjacent nodes must differ
// - Scheduling: time slot, room, instructor constraints
}
How Does the Validity Check Work?
The validity check tests three constraints for a digit at position (row, col): the digit must not appear in the same row, the same column, or the same 3x3 box. The box top-left corner is computed as (row/3)*3 and (col/3)*3.
package com.bank.core;
public class ValidityExplained {
public static void main(String[] args) {
// Box index arithmetic:
// Cell (4, 7) -> box top-left = (4/3)*3, (7/3)*3 = (3, 6)
// Cell (1, 2) -> box top-left = (1/3)*3, (2/3)*3 = (0, 0)
int row = 4, col = 7;
int boxRow = (row / 3) * 3; // 3
int boxCol = (col / 3) * 3; // 6
System.out.println("Cell (" + row + "," + col + ") is in box starting at (" + boxRow + "," + boxCol + ")");
}
}
Cell (4,7) is in box starting at (3,6)
How Is This Different from N-Queens?
| Aspect | Sudoku Solver | N-Queens |
|---|---|---|
| Grid size | Fixed 9x9 | Variable NxN |
| Values | Digits 1-9 | Queen placement |
| Constraints | Row + Column + 3x3 Box | Row + Column + Diagonals |
| Solutions | Usually one | Multiple for N >= 4 |
| Termination | First complete fill | First valid or all valid |
// Sudoku: 3 constraints per cell
// N-Queens: 3 constraints per queen (row, column, diagonals)
What Are Common Mistakes?
The first mistake is returning false at the wrong place. You must return false only after trying all 9 digits and none works. The second mistake is continuing the outer loop after finding an empty cell instead of returning the result of the recursive call.
Wrong code:
// WRONG: continues to next cell even when current cell has no valid digit
for (char d = '1'; d <= '9'; d++) {
if (isValid(board, r, c, d)) {
board[r][c] = d;
solve(board); // BUG: ignores return value
}
}
// falls through without returning false
Correct code:
// CORRECT: returns false to trigger backtracking
for (char d = '1'; d <= '9'; d++) {
if (isValid(board, r, c, d)) {
board[r][c] = d;
if (solve(board)) return true; // propagate success
board[r][c] = '.'; // undo on failure
}
}
return false; // no digit works
What About Optimizing with Bitmasking?
Instead of scanning the row, column, and box for each digit, you can maintain three arrays of bitmasks that track which digits are already placed. This reduces the validity check from O(9) to O(1).
package com.bank.core;
public class SudokuBitmask {
private int[] rowMask = new int[9];
private int[] colMask = new int[9];
private int[] boxMask = new int[9];
public boolean canPlace(int r, int c, int d) {
int bit = 1 << d;
int box = (r / 3) * 3 + (c / 3);
return (rowMask[r] & bit) == 0
&& (colMask[c] & bit) == 0
&& (boxMask[box] & bit) == 0;
}
public void place(int r, int c, int d) {
int bit = 1 << d;
int box = (r / 3) * 3 + (c / 3);
rowMask[r] |= bit;
colMask[c] |= bit;
boxMask[box] |= bit;
}
public void remove(int r, int c, int d) {
int bit = 1 << d;
int box = (r / 3) * 3 + (c / 3);
rowMask[r] &= ~bit;
colMask[c] &= ~bit;
boxMask[box] &= ~bit;
}
}
What About the Minimum Remaining Values Heuristic?
Instead of scanning cells left to right and top to bottom, the MRV heuristic picks the empty cell with the fewest valid candidates first. This dramatically reduces the search space for hard puzzles because the most constrained cell is filled first, which prunes more branches early.
package com.bank.core;
public class MRVHeuristic {
// Find the empty cell with fewest valid digits
public static int[] findMostConstrained(char[][] board) {
int minOptions = 10;
int[] bestCell = null;
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] == '.') {
int options = countValidDigits(board, r, c);
if (options < minOptions) {
minOptions = options;
bestCell = new int[]{r, c};
}
}
}
}
return bestCell;
}
private static int countValidDigits(char[][] board, int r, int c) {
int count = 0;
for (char d = '1'; d <= '9'; d++) {
if (SudokuSolver.isValid(board, r, c, d)) count++;
}
return count;
}
}
What About Time and Space Complexity?
The worst-case time complexity is O(9^E) where E is the number of empty cells, because each empty cell can try up to 9 digits. In practice, the constraint checks prune most candidates immediately, so real Sudoku puzzles solve in milliseconds.
The space complexity is O(E) for the recursion depth, which is at most 81.
package com.bank.core;
public class SudokuComplexity {
// Worst case: O(9^E) where E = number of empty cells
// Practical: milliseconds due to heavy pruning
// Space: O(E) recursion depth, at most 81
// With bitmask: validity check O(1) instead of O(9)
// With MRV: much fewer branches explored
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Validate a filled Sudoku board (check all constraints without solving).
- Count the number of valid solutions for a given board.
- Generate a valid Sudoku puzzle with a unique solution.
- Extend to 16x16 Sudoku (hexadoku).
package com.bank.core;
public class SudokuValidator {
public static boolean isValidBoard(char[][] board) {
for (int i = 0; i < 9; i++) {
boolean[] rowSeen = new boolean[10];
boolean[] colSeen = new boolean[10];
boolean[] boxSeen = new boolean[10];
for (int j = 0; j < 9; j++) {
// Row check
if (board[i][j] != '.') {
int d = board[i][j] - '0';
if (rowSeen[d]) return false;
rowSeen[d] = true;
}
// Column check
if (board[j][i] != '.') {
int d = board[j][i] - '0';
if (colSeen[d]) return false;
colSeen[d] = true;
}
// Box check
int br = (i / 3) * 3 + j / 3;
int bc = (i % 3) * 3 + j % 3;
if (board[br][bc] != '.') {
int d = board[br][bc] - '0';
if (boxSeen[d]) return false;
boxSeen[d] = true;
}
}
}
return true;
}
}
Visual Overview
Sudoku Backtracking Flow:
Find empty cell (r, c)
│
▼
Try digit d = 1 to 9
│
├── isValid(r, c, d)?
│ ├── Check row: no d in row r
│ ├── Check column: no d in column c
│ └── Check box: no d in 3x3 box
│
├── Valid? Place d, recurse to next empty
│ ├── Solved? Return true (propagate up)
│ └── Stuck? Reset cell, try next d
│
└── All digits tried, none works?
Return false (backtrack to caller)
Box Index Arithmetic:
┌───────┬───────┬───────┐
│ Box 0 │ Box 1 │ Box 2 │ Rows 0-2
├───────┼───────┼───────┤
│ Box 3 │ Box 4 │ Box 5 │ Rows 3-5
├───────┼───────┼───────┤
│ Box 6 │ Box 7 │ Box 8 │ Rows 6-8
└───────┴───────┴───────┘
Box = (r/3)*3 + (c/3)
Key Takeaway
The Sudoku solver is backtracking over the empty cells of the grid. I find the next empty cell, try the digits 1 through 9, and place a digit only when it does not already appear in that cell's row, column, or 3x3 box. After placing a valid digit I recurse. If the recursion fills the whole grid I propagate true up and stop. If it gets stuck I reset the cell and try the next digit. When a cell has no valid digit at all I return false, which triggers backtracking in the caller.
The box-index arithmetic maps any cell to its 3x3 region: the box top-left is (row/3)*3 for the row and (col/3)*3 for the column. Real puzzles solve quickly because the three-way validity check prunes most candidates immediately, even though the worst case is exponential.
For hard puzzles, two optimizations make a big difference. Bitmask arrays reduce the validity check from O(9) to O(1) per digit. The minimum remaining values heuristic fills the most constrained cell first, which prunes more branches early and cuts the search time sharply.
In my project at National Bank of India, a reconciliation grid had to be completed so each row, column, and sub-block contained each code exactly once, and the tool filled the blanks automatically. This constraint backtracking solved it reliably for all test cases.
Remember one sentence: try digits 1-9 in each empty cell, check row, column, and box constraints, recurse, and backtrack on dead ends.
---