Backtracking
Build a solution one choice at a time and undo the last choice when it cannot lead to a solution.
Decision · step 2 of 32Backtracking: 4 queens, with backtracking
Row 0, square (0, 0): no queen shares its column or a diagonal. Place a queen and move to row 1.
What you will see
CHOOSE -> EXPLORE -> FAIL -> BACKTRACK as a decision tree; dead branches grey out.
Cost
| Space | O(depth) |
|---|
Time is exponential in general; pruning determines practical cost.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Each node of the decision tree announces the choice made and whether it led to success, failure or further choices.
Reduced motion: Tree nodes appear and grey out in place; no travelling focus.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Backtracking covers these too, in the same run.