🧮Backtracking
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
Common mistake
Key takeaways
- 1One choice at a time. Build the answer step by step.
- 2Check early. Stop as soon as it cannot work.
- 3Undo and retry. Step back to the last choice.