Maze and Path Finding
What you'll learn: How to use backtracking to explore all possible paths through a maze by marking visited cells and undoing those marks when you hit dead ends.
The Core Idea
Imagine you're solving a paper maze with a pencil and eraser. You pick a direction, draw a line, and keep going. When you hit a wall or a dead end, you erase your marks back to the last choice point and try a different path. That's backtracking for maze solving!
In code, you start from the entrance and recursively explore each possible direction (up, down, left, right). To avoid going in circles, you mark each cell as visited before moving into it. If you reach the exit, you've found a path! If all directions from your current position are blocked or already visited, you've hit a dead end—so you unmark the current cell (backtrack) and let the recursion return to try other options.
Why Mark and Unmark?
- Marking visited cells prevents infinite loops (walking in circles)
- Unmarking during backtracking allows the cell to be part of a different path attempt later
- This explores the entire search space systematically
The Pattern
- Check if current cell is the goal → success!
- Mark current cell as visited
- Try each possible direction recursively
- If any direction succeeds, return success
- Unmark current cell (backtrack)
- Return failure
This is pure backtracking: make a choice, explore consequences, undo the choice if it doesn't work out.
Key Takeaway: Maze solving with backtracking explores all possible paths by marking cells during exploration and unmarking them when backtracking from dead ends, ensuring every route is systematically tried.