Escaping the maze
The rat in a maze problem gives a grid where some cells are open and some are blocked. A rat starts at the top-left and must reach the bottom-right, moving only through open cells. The goal is to find a path, or to count or list all paths.
Backtracking the route
From the current cell, try each allowed move in turn, often down and right, or all four directions in richer variants:
- If a move lands inside the grid on an open, unvisited cell, mark it as part of the path and recurse.
- If the recursion reaches the destination, you have a solution.
- If every move from a cell fails, unmark it and return so the previous cell can try its other options.
The unmark on retreat is what frees a cell for alternative routes and prevents a path from looping back on itself.
Keeping it bounded
A visited marker, or restricting moves to forward directions, stops infinite cycles. Trying directions in a fixed order makes the search deterministic and the output reproducible.
Key idea
The rat explores open neighbours from each cell, marking the path forward and unmarking on retreat, so blocked routes are abandoned while alternative directions stay available.