Getting a rat from a maze

Question

The rat is placed in a labyrinth in an unknown place in the labyrinth.

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

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

We need to write a function that returns true if we find a way out or false if there is no way.

This is a simple graph task and can be solved using bfs or dfs algorithms if we can find the mark of these places. If we cannot mark these places, we can cycle through visiting the same places. Can someone help me get the rat out of the maze if it is not marked? Is it possible?

Answer 1

A breadth and depth search requires memory, and a naive algorithm can run indefinitely. The rat probably has only O (1) memory.

One way to solve this without remembering where you were is to choose a direction at random. The decision time will be extremely long, but ultimately it should reach any available area. This is due to 2D random .

Surprisingly, it was proved that on a two-dimensional lattice a random walk has a unit probability of reaching any point (including the starting point), since the number of steps approaches infinity.

Answer 2

The algorithm is basically USTCON (undirected st-connectivity): if an undirected graph G is given, determine if there is a path from node s (the initial position of the rat) to node t (exit). This problem is in complexity class L , which means that a logarithmic amount of memory is required. So, if you do not have an upper bound on the size of the maze or are not ready for approximation, this is not possible with constant space.

Answer 3

Without memory, the only solution is a random one, and it's terrible. If you know that the labyrinth is only connected separately, you can use the wall-based approach, but which can go into an infinite loop if the labyrinth contains a loop.

Answer 4

You must run the BFS algorithms. The only problem I see is to define a schedule. It can be determined using the von Neumann area . Node is defined as a pair of X, Y. The pseudocode should look like this:

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(vx-i,vy-j) return adj_list 

EDIT : now I read the O (1) memory limit. Therefore, I think you should follow the old method to always turn right, and you will eventually exit the maze or return to its original position.

EDIT2 : from the corn maze tips:

As in any maze, if you sequentially perform either a right or left turn, you will eventually find a way out. Continuing your finger, the wall of the labyrinth, without lifting it, will keep you on the right track.

Answer 5

This is a classic problem often used as homework.

Try the following:

• Can you tell if you are on your way now?
• Once you do this, what do you need to do to find out if you have one option?
• How about if you are within 2 steps of the exit?

...

How to Mark Notes , the simplest versions of the algorithm to which I am trying to lead you can be blocked in a loop. How can you solve this problem?

Answer 6

If I remember correctly, I had such a recursion homework as it was a long time ago, but it was not limited to O (1) memory. We simply could not build “maps” of where we were and had to use recursion ... I assume that this will use the memory O (n), where n is the shortest distance to the stairs from the very beginning.

 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() */ 

Answer 7

It's funny that @mousey will ask about the rat ... well.

I have seen this problem creep several times already.

The first (and naive) solution is to follow the left (or right) wall, however it is possible to create special labyrinths where the rat ends in circles.

In fact, for each deterministic order of moves (e.g. 2L, 1R, 2L, 1R, ...) that I tried (when I was in high school, I had time), we could come up with a maze that would make the rat run in a circle . Of course, the harder the cycle, the harder the maze.

Therefore, if you have O (1) memory, the only solution to exit the maze is the random walk suggested by Mark Byers. Unfortunately, you cannot prove that it is impossible to exit the maze using such an algorithm.

On the other hand, if you have O (N) memory, it comes down to creating a map (somehow). The strategy that I finally came up with then was to leave the pheromone (increasing the counter) in each case that I went through, and when you have a choice in motion, to choose among the least visited cases. However, it was always possible to exit, so I never had to think about the state of termination if there was no way out.

You can also use the fill fill algorithm ... Of course, that was before I found out about the BFS terms. This has the advantage that you have a termination condition (when there is not a single case left to study).

Answer 8

Determining if there is a way out sounds very much like a stop problem. It can be solved for all trivial and many non-trivial cases, but for many maps, if you cannot mark where you were, you cannot prove that the map is not infinite.

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