17

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.

Community
  • 1
ghosts_in_the_code
  • 7,024
  • 1
  • 30
  • 100
  • 2
    interesting puzzle. personally I doubt such a sequence exists but not sure how to prove it – Ivo Jan 19 '17 at 15:46
  • 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. – Tim Couwelier Jan 19 '17 at 16:19
  • 1
    @TimCouwelier I said that an infinite number of cells are accessible from the starting cell. – ghosts_in_the_code Jan 19 '17 at 16:21
  • 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". – Ian MacDonald Jan 19 '17 at 17:09
  • 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. – Peregrine Rook Jan 19 '17 at 20:33
  • P.P.S. I suppose you could call the thing a bi-directional connected graph with orthogonal connectivity, and so the [graph-theory] tag might apply, but that wouldn’t really make matters any clearer. – Peregrine Rook Jan 19 '17 at 20:36
  • Could you please add a link to the related challenge on PPCG? – mbomb007 Jan 19 '17 at 22:31
  • How can "execution complete" in an infinite maze? Would proper code not just run indefinitely -- searching for an exit? I guess part of your question is, prove that that is the case if it is so..? – HC_ Jan 19 '17 at 23:11
  • @HC_: The question is whether one could devise a specific finite set of steps which, when run, would be guaranteed to leave the person at a square other than the starting one. – supercat Jan 20 '17 at 00:18
  • I cannot see why N-E-S-W-N is not a legitimate answer, given the constraints put in place by OP. – Xenocacia Jan 20 '17 at 06:42
  • @Xenocacia that's easy, don't have any walls and you end up in the starting cell. and if you would insist to have walls: have a north wall in the starting cell and a south wall in the cell to the east of the starting cell. I think you might be misunderstanding the question – Ivo Jan 20 '17 at 12:36
  • @ivobeckers: if there were no walls, I'd end up one cell north of my starting point, yes? But ok, I see how the second scenario would kill off my "solution". Thanks! – Xenocacia Jan 20 '17 at 14:27
  • @Xenocacia yeah you're right with the no wall situation. My mistake – Ivo Jan 20 '17 at 14:34
  • Comment rather than answer because I think it's an error in the problem statement, but any countably infinite sequence would suffice. You guarantee not to end up in the starting square by guaranteeing not to end. – Peter Taylor Jan 23 '17 at 07:23
  • @PeterTaylor Lol. That just sounds like a loophole. But you are free to end the question if you want to. – ghosts_in_the_code Jan 23 '17 at 08:51

2 Answers2

18

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.

BaSzAt
  • 5,657
  • 3
  • 21
  • 35
  • 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" – Ivo Jan 19 '17 at 18:32
  • @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"? – BaSzAt Jan 19 '17 at 18:40
  • 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 – Ivo Jan 19 '17 at 18:44
  • @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. – BaSzAt Jan 19 '17 at 18:48
  • Exactly, yeah that would be nice – Ivo Jan 19 '17 at 18:52
  • Once you've determined there's more RIGHT than LEFT, can't you end proof immediately by saying that in a left facing infinite corridor you will end up at the start? – Cruncher Jan 19 '17 at 19:15
  • @Cruncher But RIGHT RIGHT RIGHT RIGHT RIGHT LEFT does not return in that corridor. – BaSzAt Jan 19 '17 at 19:18
  • @BaSzAt ah right. Very clever solution btw – Cruncher Jan 19 '17 at 19:24
  • @Cruncher Thanks. It's a little sad it doesn't look anything like a maze though. It's just a corner. Ivo Beckers has a nice idea to spice it up a little :) – BaSzAt Jan 19 '17 at 19:28
  • @BaSzAt I mean, that's the nature of existance proofs though. You prove using the easiest case possible. Obviously doesn't mean there aren't many other mazes that would fail on the same input. But you only have to show there's 1 :) To me the proposed restriction is uninteresting, and would have a proof just a much less elegant one. Just my opinion though – Cruncher Jan 19 '17 at 19:34
  • @BaSzAt you can suppress movement in one dimension altogether, then you're just in a long dead end, which is fine in any maze. – Neil W Jan 19 '17 at 22:22
  • @NeilW Sorry, I can't determine which of my comments you're referring to. – BaSzAt Jan 19 '17 at 22:30
  • @BaSzAt your remark that your solution is 'just a corner'. – Neil W Jan 19 '17 at 22:33
  • @NeilW Aha, I didn't even think about that! Yes, that's entirely correct, I gave the robot too much space. Thanks! – BaSzAt Jan 19 '17 at 22:39
1

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.

Peregrine Rook
  • 4,880
  • 2
  • 26
  • 40
Tsathoggua
  • 221
  • 1
  • 4