You are tasked with designing a robot to explore a large but finite maze. The maze is drawn on a square grid, and walls exist on some of the edges of the square grid. Some of the squares contain a flag.
Your robot may interact with the world in the following ways:
1) Check which of the 4 adjacent edges contain walls.
2) Move to one of the 4 adjacent squares (provided there is no wall in the way).
3) Check if there is a flag on your square.
4) Pick up a flag (provided there is a flag on your square and the robot is not already holding a flag).
5) Put down a flag (provided the robot is holding a flag and there is not already a flag on your square).
6) Generate a random bit.
7) Output a number.
Your robot will be placed in a maze. The maze will contain some number of flags (from 100 to 1000). All flags will be reachable from the robot’s starting position. Your robot is tasked with determining the number of flags. The robot may take as long as it needs, but may only output one number and must output the correct answer eventually, with probability 1.
The catch is that your robot is not Turing complete. It only has a finite amount of memory. You can give your robot as much memory as you need, but it must succeed on arbitrarily large mazes.
As always, the solution will eventually be posted in the comments, but you are encouraged to show off by posting your solution first.
Is it safe to assume that the robot knows the position where it starts? If not, can we assume that the border of the grid itself is all walls (so we can make sure we don’t wander off into infinity)?
Can we make any assumption about where walls are within the maze? Most mazes appear to have the walls span all corners — this property would be useful.
The maze is finite. By finite, I mean that there are a finite number of squares that the robot can reach. Everything else is blocked off by walls.
Walls appear only on the edges of the square grid. You cannot assume that the set of squares you can reach is simply connected, and you cannot assume that all the walls are connected, but you can assume that you can reach every flag.
I am not sure what you mean by “the walls span all corners.” You probably are asking if we can assume that every corner of every square is contained in at least one wall. I don’t think it matters, but you may not assume that.
The robot cannot distinguish between its starting spot and any other square on the grid.
Does that clear everything up?
Yar, matey. I think I have a constant space algorithm for if the walls span the corners, if exploring the question of whether that matters is interesting. I think I can modify this to support more open spaces, though.
I cannot imagine how this fact could help you. Are you sure you did not accidentally that all walls are connected?
I’m not sure I’m not assuming that, but I believe I’m not. But if the walls span the maze, and it’s closed, I should be able to use the right hand rule to traverse the entire space. Which means I can just have a counter for how many I’ve seen and stored offsets for my path I’ve traveled since I began.
Nah, you’re right, that assumed the walls are connected, my intuition about that seems to have been way off.
Couldn’t I just keep memory for where (in relation to where I started) the 1000 flags are (for those we’ve found), keep track of where we are, and then just spiral out? Feels like it’d be constant space (as long as integer offsets are considered constant space. I can write some psuedocode for constant space spiraling out by using the same right hand rule but pretending there are walls are N, where N is the current spiral radius.
Any of those numbers might be too large to store in your finite robot.
Note: termination condition is a boolean, a check to see, upon increasing the spiral radius, whether any of the steps since spiral actually went N out. If none did, stop and report the number of flags seen.
“Arbitrarily large” can be quite big.
Any solution that depends on knowing your coordinates is impossible. Imagine you have N bits of memory, and the maze area is 2-to-the-Nth squares long in each dimension. You would need 2N bits to store a location.
Likewise you can’t count the number of turns you have made, so if you use a wall-following algorithm you can’t know if you’ve traversed the outside wall or an inside one.
So if ithe flag counting task is possible then several interesting things must be possible. It has to be possible to reliably traverse every square no matter how many loops and dead-ends exist in the maze.
That is correct. Thank you.
The wording “with probability 1” suggest the possibility of “almost correctness” rather than absolute correctness (though yes, that would require infinite mazes I imagine, which is not what we have). The ability to generate random bit gives the option of Monte Carlo traversal/sampling which would, at some point be close enough to the correct answer that we could declare that to be the output. These are just ideas mind you, I could be entirely wrong.
The maze will be finite. The “with probability 1” just means that you can have an algorithm which always gives the correct answer if it outputs an answer, but which could theoretically run forever if it gets very very unlucky with its random bits. However, as n increases, the probability that the program has not yet halted after n time steps must approach 0. (not just be approximately 0, but approaching 0 in the limit.)
I am prety sure that a basic random walk traversal eventually traverses the entire maze (may not halt). The problem would be remembering the number of flags encountered and not double counting.
My instincts are telling me I can use the flag positions to represent any size-related variable bytes. How I would go about doing this is something of a mystery to me — perhaps a better approach would be to build an isomorphism to a known-competent model and prove space usage is asymptotically < O(n) [so then my constant memory can expand until the crossover point due to constant factors]? Once I figure out a local total ordering of squares, I think I can map this to a 2-state turing machine with a hard cap on number of squares with value X. Not sure if that's enough, plus the random number thing isn't used, which makes me feel I'm missing a key insight.
I eagerly await the solution.
Any (sufficiently sparse) arrangement of flags you make to represent state is indistinguishable from a random starting configuration.
Pingback: The Case of the Massive Maze | LiveRamp Blog
So, what _is_ the solution?
Sketch of the solution is up.
This has been unsolved for a long time now. Could you perhaps post the solution? I’d be curious about it because in my opinion the problem is impossible to solve.
Sketch of solution is up.
Ok, here is the solution.
First, observe that the robot can easily know the contents of every square within a million steps of himself, as well as all walls within that radius. (a million robot steps, not steps through walls.) All the robot has to do is research everything every time he makes a step, then return to where he started researching.
Next, observe that the robot can just move randomly until there are at least 100 flags within a million steps of him. This takes a very long time but that is okay. The robot can then carry all 100 flags around with him in his radius one million bubble.
Now, once the robot has 100 flags with him, he needs to traverse the maze and make sure there are no other flags. If he discovers another flag, he now takes 101 flags with him and tries to traverse the maze.
In order to traverse the maze, the robot will need two subroutines:
1) Check if there is a square below me (with the same horizontal (x) component, but different smaller vertical (y) component that I can reach.
2) Move to the closest square below me that I can reach.
First, lets show that with these two subroutines, the robot can traverse the entire maze. The robot can just move down by checking if there is a square below him, and moving to it if possible. He can repeat this until he is in the lowest reachable square in his column. Then, the robot can use a (modification of) the subroutines to move up as far as he can. While the robot moves all the way down then all the way up, if at any time he can move left, he does so, and starts over. The result of this is that he will check all of a column, and if there is any way to move left from that column, he takes it, until he is in (one of) the leftmost squares in the maze.
Once the robot is in the leftmost square of the maze, he can go all the way to the bottom of the column, then go all the way to the top of that column, to traverse the entire column. Then the robot can go down the column, and if at any time he can take a step of the right, he does so, and repeats. He continues this, traversing every column of the maze, until he cannot move any further right. Then the robot know that it has traversed the entire maze.
If the robot traverses the entire maze, and does not observe any new flags, it can return the number of flags it has with it. If it does observe a new flag, it takes this one more flag and starts over traversing the maze.
Now, we will show how to do the two subroutines. For the first one, we will use a right hand on the wall algorithm. The robot will pretend to keep its right hand on the wall below it, and walk all the way around in a loop until he returns where he started. (For this we will pretend the robot has an orientation, and turns and moves forward. The robot can keep its “orientation” in memory. The robot starts facing right.) Once the robot returns to where he started, we will use a winding number technique. It is guaranteed that the number of times the robot turns right left minus the number of times the robot turns right will be exactly -4 or 4 while walking around the wall. We will keep track of this number (modulo 10). At the end, if the number is 4, the robot cannot move down and if the number is -4 (or 6) the robot can move down. (Think about why this is true)
There is another issue we need to solve for this, the robot needs to be able to know when it returns where it starts using the right hand on the wall technique. For this, the robot will set up a special configuration of flags before it leaves, and it will know it is back where it stated when it returns to that configuration. However, it is possible that remaining flags happen to be in that exact configuration. To check for this, the robot slightly changes the flags and walks back (with his left hand on the wall). If the starting configuration also changed, he must be back where he started.
Now we are ready for subroutine 2. For this, the robot will again put his hand on the wall below him and traverse the wall. While he is doing it, he will keep track of three variables: Y = the number of squares he is above the starting square, X = the number of squares he is to the right of the starting square, and Z = the maximum value of Y at any time that the Y variable was negative and the X was zero. Every time the robot steps left or right, he updates X. Every time he steps up or down, he updates Y. Every time X=0 and 0
Your solution *may* be sound for densely walled mazes, but for sparsely walled mazes (where lots of cycles are possible), surely it can’t work. There is no “left hand on the wall” algorithm that will allow you to travel arbitrarily far. For example, simply imaging that only 1 grid square in 10 on average has any wall around it.
This probably also means that creating an arbitrary-length path back to a flag is impossible – you can’t remember the path, nor rely on the structure of the maze to guide you back to it.
But thanks for finally posting a solution!
(Hey, your site forces commenters to enter a name and email, but doesn’t tell you in advance. When you get an error and hit back, you lose your comment! Luckily, I’m in the habit of copying my comment before hitting submit, for this very reason!)
I do not understand your complaint. I do not do right hand on the wall for the whole maze. I only use it to get around a single obstacle which is in the way for my robot to move down one square. If there aren’t many walls, I do not have to keep my right hand on the wall very long to get to the square below me.
I see now that you are talking about the Pledge Algorithm (http://en.wikipedia.org/wiki/Maze_solving_algorithm#Pledge_algorithm). This will allow you to traverse arbitrarily far in any direction. However, it will not tell you if the “horizontal (x) component” is the same as it was above. You can move down, but you will not know how far left or right you have moved in the process.
I have not seen that before. Thanks. However my algorithm does not use the pledge algorithm anywhere. The reason subroutine 1 works is the sane as the reason the pledge algorithm works, though.