Lesson 13.4 · Backtracking
Backtracking on Grids
Mark a cell as used before exploring its neighbours and restore it afterwards, so other paths can use it.
10 min
Think of it like this
Tracing a word through a letter grid with your finger: you can't reuse a letter you're already on, but once you back out of a dead end, those letters are free again for other attempts.
1.Mark, explore, restore
Set the cell to a marker like '#', recurse in four directions, then put the original character back. The restore is the "unchoose" step. Checking bounds and the expected character before marking prunes most branches.
Remember
- Mark visited cells in place, restore on the way back.
- Check bounds and match before recursing.
Common mistakes
- Forgetting to restore the cell, so later searches fail.
- Using a visited set that is never cleared between starting points.