The Fire-and-Frost Dragon Bridge
Two fire dragons start on the two left stones and face right. Two frost dragons start on the two right stones and face left. The middle stone is empty. The goal is to swap sides, with the middle stone empty again.
Move one dragon at a time. A dragon may slide one stone forward into the empty space. Or it may jump forward over exactly one dragon of the other kind into the empty space. A dragon may never move backward or turn around.
Slide
Move forward onto the next empty stone.
Jump
Leap over one other-kind dragon into the empty stone.
Forward only
No backing up.
No turning around.
Dragon challenge
Use the investigation record. Continue the proof on separate paper as needed.
What is the fewest number of moves that can get all four dragons to the goal?
Find every different shortest path from the start to the goal. Show where the empty stone is after every move. Two paths are different if the empty stone is in a different place after any move.
Explain why your list has every shortest path and why there cannot be another. You may use pictures, numbers, or words.
Investigation record
| Move | Five-stone state | Empty stone |
|---|---|---|
| Start | ||
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 |
| Path | Empty-stone sequence |
|---|---|
| A | |
| B | |
| C | |
| D |
Completeness notes: At each branch, list every legal forward move and explain why any rejected move cannot belong to a shortest solution.