# Pathfinding with disappearing platforms - is it solvable?

This is a puzzle but might not have a solution. So "is it possible?" is a proper question.

The puzzle idea was inspired by the question logic problem/puzzle solving, and if the puzzle here turns out to be solvable, this question would be an answer to the linked question. (Hence the cross-link.)

Imagine the following situation:

There is a grid of 6x10 rectangular stones of fields of which some contain 'magical' stones which are solid under specific circumstances (defined below, shown in grey) and 'vacuum' otherwise. The other fields are 'vacuum' all the time.

This field is extended by a top and a bottom row of (6) always solid fields (shown in brown on the bottom, omitted on the top.)

There are 6 "players" which want to get across the field. They can only 'walk' on solid fields and (-this is due to the original puzzle question-) along a given path:

While a player stands still, he sends off six straight rays defined by the diagonals of the fields and a vertical line. (The centre of the rays is always the centre of the field he's standing in, regardless where on the field the player stands.):

Now a stone becomes solid (black) if, and only if, at least two different rays cross over its centre, while rays of a player standing on the platform do not count.

Note that 2 parallel rays are not considered crossing each other.

So the starting position is:

Now the puzzle-question is:

Can you bring all players safely across the field (along the defined path)?

and if not,

Can you bring at least one player safely across the field (along the defined path)?

Notation: Assuming only one player moves at a time, you can note its colour and final position (assuming the path to that one is 'walkable'. See my example answer below.

## Hints

When testing a valid move, do it by the following 3 steps:

1. "Remove" a player and his colour and check which platforms are (still) solid.

2. Move player along valid, solid path to any position. (Multiple players are allowed on the same field!)

4. This is the new "next" starting position. Note down the move and restart from 1.

Thanks to EFrog there is now also a helper tool for checking the situation. (See his answer below for details and instructions.) In accordance to the 4 points above:

Select a colour (click the big square to change colour) to "pick up" a player. Now check which 'path' is available and move the player to the end-position you want. (The tool does not allow going diagonal directly, but the rules allow it where indicated in the pre-given path.) To set-down a player, simply select another player/colour. Using 'black' mean that all players are set-down.

• Are the starting squares of all the players always solid? What happens to a player who finishes crossing the field? (My best guess would be that they can move freely along a row K, since otherwise the answer to your first question is a trivial "No"). Jan 13, 2015 at 14:33
• I haven't heard back from the original poster of that other thread, so I'm making a Flash program to simulate this. (Hopefully.) Jan 13, 2015 at 15:07
• I don't get one thing. If all players stand on same spot, does that spot disappear? Jan 13, 2015 at 15:11
• @shyos, yes. The moment there are less than two rays of different colour that cross (over the magic platforms), it disappears. So you always need at least 2 players not on the magic platform you want to sustain. (Which reminds me, that I have to draw a "K" line as Peter Taylor suggested. At least if question 1 should get a chance.) Jan 13, 2015 at 15:13
• @shyos No. That is what I meant by crossing. (See 2nd step in my example and D5 not being solid) Jan 13, 2015 at 15:20

I stumbled over this question by chance and it caught my interest. I am surprised nobody wrote a program to solve it yet.

One question that isn't clear is what happens to a player who is standing on a tile when the tile stops to be solid. One would expect that the player falls and dies, but that isn't stated explicitly.

Anyway, I wrote a program using its own notation. I just gave names to the tiles instead of the chess-like notation. So the board looks like this:

V W X Y Z [
. . U . . .
. . . T . .
. Q R S . .
. P O . . .
. . N . . .
. . . M L .
. . . J K .
. . I . . .
. . H . . .
. G . . . .
F E D C B A


(Yes, '[' is the 27th letter of the English alphabet!).

I wrote a program to search all possible position accessible from the starting position. If it is correct, it is not possible to cross the whole path even with a single player. The furthest anyone can go is square Q.

solution: ABCDEF.....................
C -> H: AB.DEF.H...................
D -> I: AB..EF.HI..................
F -> H: AB..E..HI..................
E -> C: ABC....HI..................
H -> L: ABC....HI..L...............
A -> D: .BCD...HI..L...............
C -> H: .B.D...HI..L...............
D -> C: .BC....HI..L...............
H -> K: .BC....HI.KL...............
B -> D: ..CD...HI.KL...............
C -> H: ...D...HI.KL...............
D -> C: ..C....HI.KL...............
H -> N: ..C....HI.KL.N.............
C -> D: ...D...HI.KL.N.............
H -> G: ...D..G.I.KL.N.............
N -> Q: ...D..G.I.KL....Q..........
I -> G: ...D..G...KL....Q..........
D -> G: ......G...KL....Q..........


Java source code: https://pastebin.com/kHv7uSEB

If however there are 7 players, 2 players starting on A, then all can cross to the top row. Here is how. Each move is displayed with the occupied squares along the path.

solution: ABCDEF.....................
A -> H: ABCDEF.H...................
D -> I: ABC.EF.HI..................
F -> L: ABC.E..HI..L...............
A -> K: .BC.E..HI.KL...............
B -> N: ..C.E..HI.KL.N.............
H -> O: ..C.E...I.KL.NO............
I -> Q: ..C.E.....KL.NO.Q..........
C -> G: ....E.G...KL.NO.Q..........
E -> C: ..C...G...KL.NO.Q..........
L -> P: ..C...G...K..NOPQ..........
C -> B: .B....G...K..NOPQ..........
G -> C: .BC.......K..NOPQ..........
K -> T: .BC..........NOPQ..T.......
B -> D: ..CD.........NOPQ..T.......
N -> W: ..CD..........OPQ..T..W....
P -> [: ..CD..........O.Q..T..W...[
T -> P: ..CD..........OPQ.....W...[
W -> Z: ..CD..........OPQ........Z[
O -> K: ..CD......K....PQ........Z[
C -> G: ...D..G...K....PQ........Z[
[ -> Y: ...D..G...K....PQ.......YZ.
P -> L: ...D..G...KL....Q.......YZ.
Z -> X: ...D..G...KL....Q......XY..
D -> P: ......G...KL...PQ......XY..
G -> N: ..........KL.N.PQ......XY..
Y -> Z: ..........KL.N.PQ......X.Z.
P -> O: ..........KL.NO.Q......X.Z.
X -> Y: ..........KL.NO.Q.......YZ.
L -> P: ..........K..NOPQ.......YZ.
K -> S: .............NOPQ.S.....YZ.
Z -> [: .............NOPQ.S.....Y.[
N -> W: ..............OPQ.S...W.Y.[
P -> X: ..............O.Q.S...WXY.[
Q -> V: ..............O...S..VWXY.[
O -> P: ...............P..S..VWXY.[
S -> Z: ...............P.....VWXYZ[
P -> V: .....................VWXYZ[


Another possibility is to remove the restriction that a stone must remain solid as long as a player stands on it. If you only need to solidify the stone when stepping on it, the problem becomes possible.

But the original problem taken strictly has no solution.

• Can you post your program here, too? Aug 17, 2020 at 4:29
• It is 200 lines long. Aug 18, 2020 at 15:29
• Thanks for picking this up. You can pastebin your code and just provide the link here, maybe. ? I'm accepting your answer (unless some better comes in the future). Aug 18, 2020 at 21:10
• It is a first for me. But you learn every day. I cleaned up the code a bit and pastebin'd it. The link is in the answer. Aug 18, 2020 at 21:25

This isn't really an answer, but this is a program that I made that should allow you to better solve this puzzle (or create your own using the same premises).

BmyGuest's Puzzle

Instructions

This is a very clunky program that I put together, but it should be fairly user-friendly and easy to work with.

The grid: The grid consists of the same 6x10 layout presented in the OP (with one extra row at the bottom to start on and another at top for finishing). Each tile in the grid can be turned "on" or "off" by clicking. Tiles that are turned "on" are indicated by white triangles in the corners, while tiles that are "off" are indicated by black triangles. The tiles that are "on" represent the path -- only these tiles will respond to the characters' positions. (Note that it is set to the default path presented in the OP, but it can be changed if you like.)

The little arrow things: In the bottom-right of the screen is a large red box with an arrow on each side. If you click on the red box, it should cycle through the colors (Red > Blue > Green > Yellow > Purple > Orange > Blank/None > Red). Use this to choose which player you intend to control. By clicking on the appropriate arrow button near the selection box, you can then move that character in the indicated direction on the map.

Other: You may use the spacebar to place all of the players back in their starting positions. This does not reset the path to default, just the player positions.

As I said, this is a rather clunky program. So there are a couple of known issues.

First, the player dots are able to move off of the grid. I didn't feel the need to put in restrictions, as this is just a sandbox-style program.

Second, players aren't able to move diagonally in my program; however, this is allowed in the puzzle. Just be sure that you complete each diagonal move you intend and don't stop halfway. :D

I hope this helps and my instructions make sense.

• Finally: I think you could quick-solve the "self collision" by actually not checking the collision of lines, but the collision of lines with the 3 upper OR 3 lower points in each square (left/centre/right). A valid combination has to have 2 or 3 of those points occupied. Jan 13, 2015 at 18:41
• @BmyGuest I updated my post. I actually have it set up to see if a line crosses the very center of the tile. If so, then lineCrosses increases by 1 for every line crossing the center. If lineCrosses is >= 2, then the tile is "solid". That's why when you select a player and turn him hollow, the self-collision doesn't happen (the graphic for the player isn't touching the center of the tile). Jan 13, 2015 at 18:45
• That's nice for the self-collision of the player, but you still have 2 parallel lines (overlaying each other) activating tiles, which by definition shouldn't happen. That's what I meant by the 2 out of 3 condition check as alternative. (You don't need a count for the 3 spots. It doesn't matter how many lines are on it, just that at least 2 spots per tile are "hit" ) Oh, well, yes, and the players on the tile... Jan 13, 2015 at 18:47
• BTW, sorry for being such a P.I.D.A perfectionist. What you've done is already great. Jan 13, 2015 at 18:50
• @BmyGuest I haven't done any programming in a couple years, and I'm not a pro or anything, so this is actually kinda fun for me. Try this: fastswf.com/0jk17wE It should handle the parallel lines problem (I have to check five additional points, but it's easy.) as well as including the new finishing line. Jan 13, 2015 at 19:11

This is a partial answer only, demonstrating the first few (potential) steps.

Each image depicts the situation after the named move. Remember during movement the rays of the moving player are off, so all platforms 'held' by his rays (and no other 2 crossing colours) will immediately disappear!

Orange --> A2

Yellow --> C2

Cyan--> C3

Orange --> 4

Yellow --> D4

Purple --> B3

etc...

• I think if you can get three across while leaving three on the starting row, then you can nearly assume that you can get the other three across using just the column lines from the finished three. Jan 13, 2015 at 18:14