Skip to main content
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Backtracking Visualizer

Sudoku

Step 0 / 0
Speed 100ms
Step Progress 0 / 0
Recursion Depth 0
Pruned Branches 0
Status Ready
Empty
Placing / Active
Conflict / Pruned
Solution
Placed
Step Explanation

Select an algorithm and press Play to watch the search tree explore and backtrack.

—
Pseudocode 
 
 
 
 
  
 
 
Sudoku Solver
  
 
  Intermediate (3/5)
 
~45 minutes   Constraint satisfaction  Row/column/box validity checks  Fill-and-recurse pattern  Backtracking on dead ends  
Prereqs: Recursion, Backtracking basics (N-Queens helps)  
 
Quick Reference
Sudoku Solver
The Sudoku solver fills every empty cell with a digit 1-9 such that each row, column, and 3×3 box contains every digit exactly once. Backtracking fills cells in order and undoes choices that violate the constraints.

Difficulty: Intermediate (3/5)
backtracking
Complexity
Best Time
O(9^(n²))
Average Time
O(9^(n²))
Worst Time
O(9^(n²))
Space
O(n²)
When to Use
Use the Sudoku solver to practice constraint-satisfaction backtracking — the same pattern powers cryptoarithmetic, regex backtracking, and constraint solvers.
Pros
  • Real-world puzzle everyone recognizes
  • Shows constraint propagation (row/column/box checks)
  • Easily extended with MRV heuristics for speed
Cons
  • Worst case is exponential
  • Simple cell order ignores good heuristics
  • No reasoning about candidates (no naked singles pre-solve)
History
Sudoku as a puzzle was popularized by Nikoli in 1986 in Japan, though its modern form dates to 1979 in Dell Magazines. Computer solvers based on backtracking appeared with the puzzle's global boom in 2005.
 
 
Fill every empty cell of a Sudoku grid with a digit 1-9 so each row, column, and 3×3 box contains every digit exactly once. The puzzle is a textbook constraint satisfaction problem, and backtracking solves it by the simplest possible policy: fill the next empty cell with a legal guess, and if that guess dead-ends, erase it and try another.


How It Works


    

  1. Find the first empty cell.
    2. 

  2. Try each candidate value 1-9.
    3. 

  3. Validate the candidate against the cell’s row, column, and 3×3 box.
    4. 

  4. Place a valid value and recurse to the next empty cell.
    5. 

  5. Backtrack — clear the cell and try the next candidate when no value completes the puzzle.
    6. 



The validity check is a constraint test: it guarantees the partial grid stays legal after every placement, so a fully filled board is automatically correct — no final verification pass needed.


Key Insight


This is “chronological backtracking”: each placement is a guess that later placements must honor. On failure, the solver unwinds to the most recent decision and changes it, climbing back up the recursion stack. Because constraints are checked incrementally, hopeless partial grids are abandoned as soon as the first illegal cell appears — that pruning is what turns an astronomically large search into seconds.


Worked Example


The visualizer solves a classic Wikipedia puzzle. The solver fills cells in a fixed left-to-right, top-to-bottom order:


    

  1. The first empty cell is (0,2), which can legally hold a small set of candidates — watch it try each until one survives.
    2. 

  2. Near the top rows, candidates usually succeed quickly; the backtracking becomes visible in the middle rows, where an early guess leads to a row/box conflict and the solver steps back, clears cells, and retries.
    3. 

  3. The final frame shows the completed grid with every row, column, and box containing 1-9.
    4. 



The key moment to watch: after an invalid guess, the solver doesn’t restart — it undoes just one placement at a time and continues from the nearest decision point.


Edge Cases & Pitfalls


    

  • Duplicate clues: the puzzle must be consistent; the solver will still report failure if no fill satisfies all clues.
    • 

  • Guaranteed uniqueness: a well-posed puzzle has exactly one solution — but a plain backtracker will happily stop at the first one.
    • 

  • Order matters for speed: filling in naive row-major order is much slower than filling the cell with the fewest candidates first (MRV).
    • 

  • Row/col/box indexing: the box check uses (r//3)*3 + (c//3) — off-by-one here silently corrupts the grid.
    • 



Optimizations



























HeuristicIdeaEffect
Minimum Remaining Values (MRV)Fill the cell with the fewest candidatesPrunes far earlier
Constraint propagationApply naked/hidden singles before searchingOften solves easy puzzles with zero guesses
Dancing LinksExact-cover formulationNear-instant on hard puzzles


Applications


    

  • Constraint satisfaction — scheduling, timetabling, and resource allocation share this search shape
    • 

  • Logical deduction engines — infer-and-check reasoning
    • 

  • Crypto/encoding puzzles — any “fill slots obeying rules” problem
    • 



Practice Trajectory


    

  1. Watch the visualizer: identify the first dead-end branch and count how many cells it unwinds.
    2. 

  2. Verify a single placement by hand using the row/column/box check.
    3. 

  3. Add MRV (pick the empty cell with the fewest candidates) and compare step counts.
    4. 

  4. Detect a puzzle with no solution and confirm the solver reports failure rather than looping.
    5. 

  5. Explain why a fully-filled board needs no final correctness pass.
    6.