Can paths crossover in Lode Runner?

96 Views Asked by At

In the game Lode Runner, a tile is an element of the set $\{A,B,S,L,P\}$ (standing for air, brick, stone, ladder, pipe respectively), and a stage is a finite rectangular grid of tiles. We call $B,S$ solid tiles. The player occupies a single tile. Say the player is supported if the tile it occupies is $L$ or $P$, or the tile below it is $B,S$ or $L$. The player may move to an adjacent tile subject to the following rules:

  1. The player may not move to a solid tile.
  2. Subject to 1, the player may move down.
  3. Subject to 1, a supported player may move left or right.
  4. Subject to 1, a player occupying a ladder may move up.

Additionally, if a player is supported, the tile to its left is not solid, and the tile below that one is $B$, the player may destroy the $B$, temporarily converting it to $A$ for a fixed amount of time; after which it solidifies back to $B$. An example is shown below (the * represents the player):

A*    A*    A*
BS => AS => BS

Similarly the player may destroy a $B$ below and to the right.

For the purpose of this question, suppose the player moves arbitrarily fast. Equivalently, rather than solidifying after a delay, suppose the player may choose at any time to wait for the oldest destroyed $B$ to solidify (however note that the order of destruction must still equal the order of solidification). (The original game also includes enemies and gold; suppose these don't exist).

Does there exist a stage in which the player can get from the top right to the bottom left, and from top left to bottom right, but not from top right to bottom right, nor from top left to bottom left?

Note that it is possible to satisfy the first three of the four conditions:

AAAAAA
SBAAAS
SSBBBS
AABBBS
ASBBBA
1

There are 1 best solutions below

0
On BEST ANSWER

I eventually found the following solution using only $\{A,L,B\}$. I've replaced $A$ by spaces and added row/column labels, so eg 1b refers to the top right tile. This image (of a slight variant) might be easier to visualize.

It works with the infinite player speed assumption given in the question, though in the real game block 55 solidifies too quickly. I would still be interested to see a simpler solution.

  123456789ab
1     BBB    
2 BBBBLLLBBBB
3   LL   LL  
4    L   L   
5 BB  B B  BB
6 BBBBBBBBBBB
7 BBBBBBBBBBB
8 BBBBBBBBBBB
9 BBBBBBBBBBB
a  BBBBBBBBB 
b  BBBBBBBBB 

To get from 11 to bb, destroy 24,55,57,5a in that order, then all tiles in the triangle with vertices 66,6a,aa:

  123456789ab
1     BBB    
2 BBB LLLBBBB
3   LL   LL  
4    L   L   
5 BB        B
6 BBBBB     B
7 BBBBBB    B
8 BBBBBBB   B
9 BBBBBBBB  B
a  BBBBBBBB  
b  BBBBBBBBB 

On the other hand, suppose we can get from 1b to bb. Note that 5a,5b can't be in the destroyed state at the same time, so we can't destroy 6b or anything below it. Therefore we must destroy aa. Working backwards, it is easy to see that we must destroy the triangle with vertices 66,6a,aa, and therefore must destroy 55,5a. Now these can only be destroyed from positions 44,4b respectively, so we must visit both. We can't get from 4b to 44, regardless of which bricks are destroyed. So we must get from 44 to 4b, which is only possible if block 24 is destroyed. This can only be done from 13, which can't be reached from 1b, a contradiction.

The other two conditions follow by symmetry.

It's possible to construct an example using only $B$ and $L$, and both of those tiles are also necessary.