DSA AnimatorDSA animations
Sudoku Solver LC #37 Hard Backtracking · Constraint Check
Problem

Write a program to solve a Sudoku puzzle by filling the empty cells ('.'). Each digit 1-9 must occur exactly once in each row, each column, and each of the nine 3×3 sub-boxes.

Example 1
Input: Standard 9×9 board with 51 empty cells
Output: Filled 9×9 board (unique solution)
Explanation: Scan for each '.' cell, try digits 1-9; if none work, backtrack to previous cell.
Constraints: board is 9×9  |  board[i][j] is a digit or '.'  |  Guaranteed unique solution.
Try Examples
Note: 9×9 board input not supported as text — use the preset example button above.
Approach
Backtracking — Scan & Try 1-9
Scan for next '.' cell. Try digits 1-9; skip if row/col/3×3 box conflict. Place digit → recurse. If no digit works → return false (backtrack to previous cell).
Sudoku Board
Progress
Empty Cells
—
Placed
—
Backtracks
—
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Scan for next empty cell ('.'). If none → solved! Return true.
2
Try digits 1-9; skip if isValid() returns false (row/col/box check)
3
Place digit → recurse. If recursive call returns true → done.
4
If no digit works for this cell → undo + return false (backtrack)
Time
O(9^m)
Space
O(m)

m = number of empty cells

Why Backtracking Works

Classic backtracking on a fixed 9×9 grid. For each empty cell, try valid digits 1-9. If recursion succeeds, propagate true up the call stack. If no digit works, undo (set cell back to '.') and return false to trigger backtracking in the caller. The isValid check covers row, column, and 3×3 box simultaneously in O(9) time.

How to solve Sudoku Solver

LeetCode 37 · Hard · Backtracking · Pattern: Backtracking on a Board

Why the obvious approach is slow

Trying all digits in all empty cells means 9 to the power of about 50 boards. Backtracking stops a branch the moment a rule is broken.

The key idea

Find the next empty cell. Try each digit from 1 to 9 that is not already in its row, column or box. Place it and recurse, and if that fails, erase it and try the next digit.

Remember

Find an empty cell, try valid digits, undo on failure. Returning true stops the search at the first solution.

Run the animation above on your own input, or watch the 1:27 video explanation of Sudoku Solver with a dry run and Java code.

More Backtracking problems