Skip to content
BENIBIX Learn

Backtracking

Development🧮 Algorithms & Data StructuresAlgorithm Design Techniques

Also known as Backtracking Algorithm, Backtrack Search

Try a choice, and step back to try another when it leads to a dead end.

Think of it like

It is like a maze game. At a dead end, you walk back to the last turn and try a new way.

Example

A Sudoku solver puts a 4 in an empty box. Three moves later nothing fits, so it goes back and tries a 5.

Why it matters

It solves puzzles where trying every full answer would take far too long. Cutting dead ends early saves most of the work.

Definition

Backtracking builds an answer one choice at a time. After each choice, it checks whether the answer can still work. If it cannot, it undoes the last choice and tries the next one. This skips whole groups of choices that are sure to fail. Sudoku solvers, maze solvers and puzzles like eight queens use it.
On the right, a path hits a dead end, steps back and tries the other way.

Common mistake

Checking only at the very end. Test each choice as soon as it is made, or it is just brute force.

Key takeaways

  1. 1
    One choice at a time. Build the answer step by step.
  2. 2
    Check early. Stop as soon as it cannot work.
  3. 3
    Undo and retry. Step back to the last choice.

Compare