---
title: "Backtracking overview"
description: "Watch recursive choices, pruning, and exact rollback in N-Queens, swap-based permutations, and an MRV Sudoku solver."
source: https://vizlearn.app/algorithms/backtracking
---

# Backtracking Visualizations

Backtracking is recursion with an undo contract. Make one choice, update the shared state, search below it, then restore exactly what changed if that branch fails. The recursion supplies the shape; rollback keeps sibling branches honest.

These lessons put that contract in three different workbenches. N-Queens reserves compact attack keys. Permutations swaps an item into the fixed prefix and swaps it back. Sudoku writes a digit into the board, lets row, column, and box constraints react, then clears the digit when the child cannot finish.

## Compare the lessons

| Lesson        | Choice                               | Pruning test                     | State that must be restored      | Output                    |
| ------------- | ------------------------------------ | -------------------------------- | -------------------------------- | ------------------------- |
| N-Queens      | one column for the next row          | occupied column or diagonal key  | queen plus three constraint keys | first valid board         |
| Permutations  | one remaining item for the next slot | none in the distinct-value trace | the forward swap                 | every positional ordering |
| Sudoku Solver | one legal digit for the MRV cell     | row, column, and 3×3 box         | the tentative board cell         | first completed grid      |

N-Queens and Sudoku are constraint searches. A rejected candidate can skip a whole subtree because the current partial assignment already violates—or cannot satisfy—a rule. Permutations deliberately explores every leaf. Its lesson is not pruning but restoration: without the reverse swap, later branches begin from the wrong array.

## A recommended order

Start with **N-Queens**. One queen owns three small keys, so you can see both halves of a backtracking step without much bookkeeping: reserve on placement, release on rollback. Its `n = 4` trace also makes failure unavoidable before the first solution.

Continue with **Permutations**. The array itself is the call state, and the same swap operation moves forward and backward. Watch the caller snapshot before each loop iteration; that one invariant explains why nested reverse swaps restore an arbitrarily deep subtree.

Finish with **Sudoku Solver**. It combines rollback with a search-order heuristic. MRV chooses the blank with the fewest legal digits, the constraint matrix explains each domain, and a zero-candidate cell sends three tentative writes back out of the recursion before the correct root choice can proceed.

## What to watch

- Identify the smallest reversible mutation. It is one queen and three keys, one swap, or one board cell—not the whole recursive subtree.
- Separate rejection from rollback. A rejected candidate never enters the state; a rolled-back candidate was locally valid but failed deeper down.
- Check the loop boundary. Before the next sibling choice begins, the caller must see its original state.
- Ask what stops the search. N-Queens and Sudoku return their first solution, while permutations records a leaf and deliberately continues.
- Compare search order with correctness. MRV and left-to-right column order change the trace and cost, not which complete assignments are valid.

## All backtracking visualizations

Choose a lesson below, step into a failed branch, and watch the highlighted code restore the same state the canvas removes.