17
$\begingroup$

Inspired by Maze Solving Robot and the related one on code golf SE

Rules

  1. You start in a cell in an orthogonal grid of infinite size. Each cell has four edges, and hence, a maximum of four ways to enter or exit it.
  2. Every edge in the grid is either a wall or not a wall.
  3. You will choose to execute a series of moves, which will consist of 'north', 'south', 'east' and 'west' instructions.
  4. If a wall exists in a direction your instruction indicates, the instruction will be skipped.
  5. You can assume that there are an infinite number of cells that are accessible from the starting cell; i.e. walls do not box you into some non-infinite subset of cells.

The Challenge
Find the shortest sequence of instructions one can execute, such that no matter the details of the maze, you can guarantee that you don't end up at the same cell you started from, once execution completes.

P.S. I'm not sure such a sequence can exist; if it can't, prove that.

P.P.S. Help me out in tagging this question....Can't find any relevant ones.

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ interesting puzzle. personally I doubt such a sequence exists but not sure how to prove it $\endgroup$
    – Ivo
    Commented Jan 19, 2017 at 15:46
  • $\begingroup$ You don't account for the scenario where the 'start cell' is surrounded by 4 walls. In such a case, there is by definition no way you'll end up in any other cell then the start cell, proving your question impossible. $\endgroup$
    – Tim Couwelier
    Commented Jan 19, 2017 at 16:19
  • 1
    $\begingroup$ @TimCouwelier I said that an infinite number of cells are accessible from the starting cell. $\endgroup$
    – ghosts_in_the_code
    Commented Jan 19, 2017 at 16:21
  • $\begingroup$ I think the term "maze" may be misleading some solvers, but I can't come up with a better word. Something that indicates "infinite grid with cell walls placed arbitrarily such that they do not create a closed loop". $\endgroup$
    – Ian MacDonald
    Commented Jan 19, 2017 at 17:09
  • $\begingroup$ When I read this question, I immediately had the rather petty, hair-splitting thought: “How can the grid have a shape when its size is infinite?”  Of course, I understand what you mean, and, like you, I’m having trouble coming up with alternatives that are better.  “Orthogonal” might be the best word, followed by “quadrate”, although if you used them, you’d probably need to explain them. … … … … … … … … … … … … … … P.S. “rectilinear” doesn’t fit so well.  To my surprise, even though it contains “rect”, it doesn’t really have anything to do with right angles. $\endgroup$
    – Peregrine Rook
    Commented Jan 19, 2017 at 20:33

2 Answers 2

Reset to default
18
$\begingroup$

Let's assume such a sequence exists, and fix a working sequence. Clearly, this sequence does not contain an equal number of NORTH and SOUTH directions, otherwise the robot would return to the starting cell in an infinite 1-wide north-south corridor. The same goes for WESTs and EASTs.

Without loss of generality, we can assume there are more NORTHs than SOUTHs and more EASTs than WESTs. Now let's build a maze to test the sequence. Start with the empty plane. First, we are going to build a straight infinite wall stretching from east to west. The latitude of this wall will be important. If there are $a$ NORTH and $b$ SOUTH directions in the sequence, we want this wall to block exactly $(a-b)$ NORTH directions. This can be done by referring to the following statement:

If an infinite south-facing wall that is $y$ cells north from the starting cell absorbs $n$ NORTHs from the sequence, then an infinite south-facing wall $y+1$ cells north from the starting point will block at least $(n-1)$ NORTHs. This is true because once the robot has bumped into the wall for the first time, it is now in front of the wall, and the rest of the sequence will be executed the same way as if the wall were pushed 1 more cell to the north.

An infinite wall directly on the north edge of the starting cell will obviously block at least $(a-b)$ NORTHs. If it blocks more than that, move the wall 1 cell to the north. If it still does, move it 1 cell further again. At some point it will block exactly $(a-b)$ NORTH directions. That will be the final place of this wall.

Then with the same method we build an infinite west-facing wall to annihilate any east-west movement.

The sequence will return to the starting point in this 'maze'. This contradiction shows that there is no sequence capable of making progress in every infinite maze.

EDIT:

As @NeilW pointed out, once we put our south-facing wall in its place, we can completely ignore horizontal movement by building infinite vertical walls on the left and right edge of the starting cell. Of course, they don't even need to be infinite. They just have to be longer than the sequence itself.

Improve this answer
$\endgroup$
14
  • $\begingroup$ nice! makes me wonder if there also is a nice proof in the case you would also put the following restriction in place "it is not allowed to put two cells without walls next to each other" $\endgroup$
    – Ivo
    Commented Jan 19, 2017 at 18:32
  • $\begingroup$ @IvoBeckers That would make the starting cell completely enclosed. Did you mean "every cell should have at least one wall"? Or did you mean "no 2x2 rectangle without at least one wall"? $\endgroup$
    – BaSzAt
    Commented Jan 19, 2017 at 18:40
  • $\begingroup$ That would also work and even more clear. What I meant with my restriction is that it would not be allowed to have a cell with no walls in all four directions next to a cell also with no walls in all four directions but your restriction also would guarantee that $\endgroup$
    – Ivo
    Commented Jan 19, 2017 at 18:44
  • $\begingroup$ @IvoBeckers So you mean no 2x1 rectangle without walls. That would be a weaker restriction, but starting with weaker restrictions might be better. Or, as an even weaker form, you could exclude any n×m rectangle without walls for some n and m. Or even any infinite rectangle without walls. $\endgroup$
    – BaSzAt
    Commented Jan 19, 2017 at 18:48
  • $\begingroup$ Exactly, yeah that would be nice $\endgroup$
    – Ivo
    Commented Jan 19, 2017 at 18:52
1
$\begingroup$

Actually, the solution for the infinite-sized maze involves always coming back to the first cell. Here is my algorithm.

  • list_of_possibilities <- initial possibilities
  • start


  • pick first possibility in list_of_possibilities
  • remove first possibility from list_of_possibilities (second possibility will become first possibility)
  • explore possibility until dead end or intersection
  • if (intersection)
    • add new possibilities at the end of list_of_possibilities
  • go back to initial cell and to start

list_of_possibilities is always finite (although it may be very long), and even in an infinite maze the distance to the exit is finite, so the robot will end up on the exit cell (although it may be very long, but it always checks finite paths, so everything is fine).

If you try to explore all the possibilities from your initial choice but pick the wrong choice (or as soon as you pick the wrong choice), you will have to explore an infinite number of possibilities (because the maze is infinite) before realizing your choice was wrong.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ There is no exit cell $\endgroup$
    – ghosts_in_the_code
    Commented Jan 19, 2017 at 16:16
  • $\begingroup$ @ghosts_in_the_code In a sense we can say all non starting cells are exit cells. But you don't finish when you hit an exit cell. You have to stop on it $\endgroup$
    – Cruncher
    Commented Jan 19, 2017 at 19:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.