The Fire-and-Frost Dragon Bridge

At a glance

• Part 1: The fewest possible number of moves is 8.
• Part 2: There are exactly 2 shortest paths, and they are mirror images.
• Part 3: Every 8-move solution is forced after its first move, so no third shortest path exists.

Use F for a fire dragon, I for a frost dragon, and _ for the empty stone.

1. Prove that eight moves is the minimum

Dragons of the same kind can never pass one another. Each dragon must therefore travel exactly 3 stone-spaces from its own starting stone to its own goal stone.

A legal move covers at most 2 stone-spaces. One move cannot carry any dragon all 3 spaces, so each of the four dragons needs at least 2 moves. Across four dragons, every solution needs at least

2 +2 +2 +2 =8 moves.

The paths below use 8 legal moves, so 8 is both achievable and minimal.

2. List every shortest path

Shortest path A

1. Start: F F _ I I
2. Move 1: F _ F I I
3. Move 2: F I F _ I
4. Move 3: F I F I _
5. Move 4: F I _ I F
6. Move 5: _ I F I F
7. Move 6: I _ F I F
8. Move 7: I I F _ F
9. Move 8: I I _ F F

Shortest path B

1. Start: F F _ I I
2. Move 1: F F I _ I
3. Move 2: F _ I F I
4. Move 3: _ F I F I
5. Move 4: I F _ F I
6. Move 5: I F I F _
7. Move 6: I F I _ F
8. Move 7: I _ I F F
9. Move 8: I I _ F F

In every row, a one-place change is a forward slide and a two-place change is a forward jump over one dragon of the other kind.

3. Prove the list is complete

An 8-move path gives exactly 2 moves to each dragon. To travel 3 spaces in 2 moves, every dragon must make one 1-space slide and one 2-space jump.

At the start, only two moves are legal: the right-hand fire dragon may slide into the empty middle stone, or the left-hand frost dragon may slide into it. Those choices are mirror images.

After either first move, preserving exactly one slide and one jump for each dragon forces the remaining moves. The branch check below shows the claim rather than assuming it. “Dead” means that no legal sequence reaches the goal; the short dead branches are shown explicitly.

All other states in paths A and B have exactly one legal next move. Thus each opening choice has one completion, the two completions are the listed mirror paths, and there cannot be a third shortest path.

Check

Both lists begin at F F _ I I, end at I I _ F F, contain exactly 8 moves, and keep the empty stone visible after every move. Every dragon moves only forward, and every jump crosses exactly one dragon of the other kind.