Watch a rat explore a maze using recursive backtracking. See the algorithm try every direction, backtrack on dead ends, and light up the solution path.
A classic backtracking problem where a rat must find a path from the top-left to the bottom-right corner of a maze, exploring all possible routes.
The maze is an N×N grid. Each cell is either open (passable) or a wall (blocked). The rat starts at (0,0) and must reach (N-1,N-1). Walls are generated randomly but the maze is always guaranteed to have at least one solution.
The rat uses Depth-First Search, trying four directions in order: Down → Right → Up → Left. At each cell it marks the path and recurses. If it reaches (N-1,N-1), the maze is solved.
When the rat hits a dead end (no valid neighbors), it backtracks: it unmarks the current cell from the solution path and returns to the previous cell to try a different direction.
Once the rat reaches the goal, all cells marked as part of the active path are converted to the SOLUTION state (shown in green). The path length tells you how many cells the solution visits.
In the worst case the rat explores every possible path in the maze. Pruning via wall checks and visited-cell tracking prevents revisiting cells and drastically cuts down the search space.