Backtracking
Build a solution one choice at a time and undo the last choice when it cannot lead to a solution.
Backtracking: 4 queens, with backtracking
Row 2 has no safe square, so the choice in row 1 was wrong. Lift the queen from (1, 2) and try the squares after it.
Cost
- Space
- O(depth)
Time is exponential in general. Pruning determines practical cost.
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Backtracking covers these too, in the same run.