← Back to DSA Animator
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.