Backtracking
Not met yet
Backtracking builds an answer one choice at a time, checks each choice the moment it's made, and when nothing fits, undoes the last choice and tries the next one there. A recursive function does it naturally: for each choice, make it, call yourself for the rest, and undo it if the call comes back with nothing. A branch that breaks a rule is dropped at once, so every arrangement that starts that way is never built. Seating plans, word grids, sudoku and mazes all go this way.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks a choice that led nowhere can be left in place while the next choice is tried, so never undoes it.
- Thinks backtracking builds every complete arrangement and checks each one at the end, rather than dropping a branch as soon as it breaks a rule.
- Thinks reaching a dead end means there's no answer, rather than going back and trying the next choice.