getting rat out of a maze

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开发者_C百科 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?

---

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.

---

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.

---

With no memory the only solution is the random one and it's terrible. If you know the maze is only singly connected you can use a wall-following approach but that can go into an infinite loop if the maze contains a loop.

---

This is a classic problem often used as a homework assignment.

Try this:

1. Can you tell if you are at the way out right now?
2. Once you have that, what do you need to do to find out if you are within one move of the way out?
3. How about if you are within 2 moves of the way out?

...

As Mark notes, the simplest versions of the algorithm I'm trying to lead you to can get locked in a loop. How can you solve this problem?

---

You should run BFS algorithms. The only problem I see is how to define graph. It can be defined with von Neumann neighborhood. Node is defined as X,Y pair. Pseudo code should look like:

BFS
while (!Q.empty()){
    v = Q.top()
    neighbours = get_adj_list(v)
    foreach (w in neighbours){
        if (isWall(w) || isOutsideMaze(w)) skip
        if (isTerminal(w)) printPathAndExit
        if (dist[v] + 1 < dist[w])
            dist[w] = dist[v] + 1
            Q.push(w)
    }
}

GEN_NEIGHBOURS
dx = {-1,1}
dy = {-1,1}

get_adj_list(v)
    adj_list = []
    for (i in dx)
        for (j in dy)
            adj_list << node(v.x-i,v.y-j)
    return adj_list

EDIT: now I read the memory limit is O(1). So I guess you should follow old method to always turn to the right and you will eventually get out of the maze or get back to start position.

EDIT2: from Corn Maze tips:

As with any maze, if consistently take either the right or left hand turns, you will eventually find a way out. Running your finger long the wall of the maze without lifting it will keep you on the right track.

---

If I remember correctly, I had a recursion homework assignment like this a long time ago, however it wasn't limited to O(1) memory. We just couldn't build 'maps' of where we've been and had to use recursion... I guess this would use O(n) memory, where n is the shortest distance to the ladder from the start.

while( 1 )
    {
    if( search( MOVE_LEFT, i ) ||
        search( MOVE_UP, i ) ||
        search( MOVE_RIGHT, i ) ||
        search( MOVE_DOWN, i ) )
         {
         return TRUE;
         }
    i++;
    }

/* recursive function */
bool search( move_type move, long int length )
{

doMove( move ); /* actually move the rat to requested place */

if( hasLadder() )
    return TRUE;

if( 0 == length )
    return FALSE;

switch( move ) /* check each and return rat to previous place */
    {
    case MOVE_LEFT:  
        if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;      
        doMove( MOVE_RIGHT ); break;
    case MOVE_UP:
        if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE; 
        doMove( MOVE_DOWN ); break;
    case MOVE_RIGHT:
        if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;      
        doMove( MOVE_LEFT ); break;
    case MOVE_DOWN:
        if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;      
        doMove( MOVE_UP ); break;
    }

return FALSE;

}   /* search() */

---

Funny that @mousey would ask about a rat... anwyay.

I have seen this problem creep up a number of times already.

The first (and naive) solution is to follow the left (or right) wall, however it's possible to craft specific mazes where the rat end up running in circles.

In fact, for every deterministic order of moves (like 2L, 1R, 2L, 1R, ...) that I tried (being in high school I had time) we could come up with a maze that would make the rat run in circles. Of course, the more complicated the cycle, the more complicated the maze.

Therefore, if you have O(1) memory, the only solution to get out of the maze seems to be a random walk, as proposed by Mark Byers. Unfortunately you cannot prove it's impossible to get out of the maze with such an algorithm.

On the other hand, if you have O(N) memory, it boils down to creating a map (somehow). The strategy I finally come up with back then was to leave pheromon (incrementing a counter) on each case I passed, and when having a choice in a move, to choose among the least visited cases. However it was always possible to get out so I never had to think about a termination condition in case there is no exit.

You can also use a flood fill algorithm...Of course, it was before I learned about the term BFS. This has the advantage that you do have a termination condition (when there isn't any case left to explore).

---

Determining whether there is a way out sounds a lot like a halting problem to me. It can be solved for all trivial and many non trivial cases but for lots of maps unless you can mark where you have been you can't prove that the map isn't infinite.

http://en.wikipedia.org/wiki/Halting_problem