getting rat out of a maze

Question

A rat is placed in a maze at some unknown position in the maze.

All we can go is in up, down, right or left directions. And we have two methods:

• tryMove(<direction>) which returns false if there is a wall and true if we can move.
• bool hasLadder(): which returns true if there is a ladder to escape.

We have to write a function explore which returns true if we find the way out or false if there is no way.

This is a simple graph problem and can be solved using bfs or a dfs algorithm if we can find mark these places. If we cannot mark these places we can move in cycles visiting the same places. Can some one help me to get rat out of the maze please if its unmarked? Is it possible?

Answer 1

Both breadth-first and depth first search require memory and a naive algorithm can loop indefinitely. A rat probably only has O(1) memory.

One way to solve it without remembering where you have been is to pick a direction at random. The solve time will be extremely long, but it should eventually reach every reachable square. This is related to the 2D random walk.

Amazingly, it has been proven that on a two-dimensional lattice, a random walk has unity probability of reaching any point (including the starting point) as the number of steps approaches infinity.

Answer 2

The algorithm is basically USTCON (undirected st-connectivity): given an undirected graph G, determine if there is a path from node s (the rat's start position) to node t (the exit). This problem is in complexity class L, which means it requires a logarithmic amount of memory. So, unless you have an upper bound on the size of the maze, or are willing to approximate, it is impossible with constant space.