One of the Stock Video Game Puzzles, a puzzle based around a set of locations with paths between them, where each place must be visited but only once, and visiting twice is a failure and something bad happens. Usually each "location" is a tile, and will be described as such going forward for simplicity.
What happens when stepping on an already stepped tile may vary on severity, and could be anything. It's not relevant to the trope but is an open question if unprovided. It might just reset the puzzle, letting the player try again immediately... But there's no reason it couldn't just end the game immediately, if the creator is feeling extremely cruel.
For a Justification of why the spaces can only be visited once, compare Temporary Platform. Cracked ice as tiles is a variant that's been seen multiple times, along with mixing this trope with Frictionless Ice and a Slippy-Slidey Ice World.
The "Hamiltonian Path"
of the trope name is the mathematical term from graph theory for the path needed to solve the puzzle, while a Space-Filling Path is the trope where getting from point A to point B involves a gratuitous amount of sidetracking, but the term could be used to describe how all the space is being used in a Hamiltonian Path.
In a game that actually uses square, or just four-sided, tiles, if there's an odd number of tiles in the puzzle, that means that by visualizing the tiles as colored in two alternating colors like a checkerboard, a correct solution must have the "color" of the starting tile be the same "color" as the ending tile.
Video Game Examples:
open/close all folders
Video Games
- Blobun is a puzzle game about a blob bunny who has to cover every floor tile on a map with slime she leaves behind when moving (How does that help in finding a witch who can undo the slimification? Who cares?), but since moving into her own slime trail gets her stuck, she has to find a way to move into each tile only once. Progressing through the game introduces twists such as blocks that must be lowered with items, metal hole tiles that requires passing through twice and a grey form that makes Stephanie leave no trail behind, for use in block puzzles.
- Deadly Rooms of Death: Trapdoors, which fall after the player steps onto and then off them, are a common room element. Some rooms include red doors, which open when all trapdoors in a room have been dropped, so a contiguous region of trapdoors becomes a Hamiltonian path puzzle. Level 15 of King Dugan's Dungeon consists entirely of puzzles of this type.
- Dragon Age: Inquisition: The optional Temple of Mythal rituals are the making of Hamiltonian paths with floor tile stepping, stepping on certain sets of floor tiles only once. The mandatory first puzzle is a simplified version where the tiles form a single ring, so the "puzzle" consists of just walking around the shrine once.
- Epic Battle Fantasy: some games feature puzzles where the player must activate a set of buttons and may not step on an already activated button, rewarding a treasure chest if successful.
- Evoland Classic: The puzzle in the dungeon is to walk a Hamiltonian Path on a set of tiles to unlock the way to the "Diablo mode" upgrade.
- Finding Nemo (THQ): The level Minefield requires you to traverse the level without bouncing on the same mine too many times, otherwise the mine will explode and you die.
- Genshin Impact: To harvest the Vasmrti and other Sumeru Nurseries, the party must walk across all the dirt patches from the glowing one to where the Vasmrti sprout is:
Tutorial: traverse each "field" without interruption or repetition,
- The infamous Golden Gun Room in GoldenEye (1997) requires you to follow a Hamiltonian path across the tiles to reach the weapon, or else the automated gun turrets will turn you to Swiss cheese.
- Golden Sun: An early-game dungeon features several rooms in which you need to hop across a spiderweb using leaves as stepping stones. The leaves break once you hop on them , and hopping on one a second time will send you falling through the web to the floor below. You have to do this at one point to progress.
- Honkai: Star Rail: In Herta Space Station, the "Unearthly Marvel" puzzle is a "bridge" made of Hard Light tiles, which you have to step on once each; once you've stepped on all tiles, it'll turn into a solid path and a treasure chest will appear as a reward. Some Unearthly Marvel may have "walls" in between the tiles that you can't pass through, some others have "teleporters" that brings you from one tile to a distant one.
- In The Precursor City in Jak and Daxter: The Precursor Legacy, there is a set of platforms over a pool with electrified water with closed door on the other side. Landing on platform lights it up, and landing on lit platform shuts it down. When all platforms are lit, the mentioned door opens and reveals Power Cell.
- Legend of Grimrock 2: A puzzle in Orul's Crypt consists of a room of energy platforms, with a pillar in the middle to make traversal more confusing. Each platform disappears when stepped off, and the door at the end only opens when all the platforms have disappeared. Because of the parity issue, only one of the three possible starting tiles is correct.
- The Legend of Zelda franchise:
- The Legend of Zelda: Link's Awakening: The eighth dungeon features several rooms with impassible gaps in the floor and a magical device that fills in those gaps as it moves. It resets all progress if it touches any solid ground before filling in the gap completely. Also, once you start the device, it moves at a constant speed, so all you can control is its direction, making this a test of reflexes in addition to a pathing puzzle.
- The Legend of Zelda: Oracle Games: The Hero's Cave in a linked Oracle of Ages game has a Moon Logic Puzzle room with a Hamiltonian Path Puzzle, where you have to walk a non-intersecting path that turns every blue floor tile red. However, no matter which path you take, you're always going to end up with at least one spare blue tile. You're supposed to realize that blocks created using the Cane of Somaria are red, and cover the last blue tile with one. Prior to this puzzle, Cane blocks have only been required to hold down pressure switches, check for bottomless pits in pitch-black rooms, and as an obstacle in a boss battle — having any other properties, let alone such an exotic one, is never hinted at.
- Machinarium has a series of 5×5 grids where the player must light up all tiles. You choose which direction to move the cursor, but only stop when the cursor reaches a lit (and impassable) tile. Each puzzle has a few tiles already lit, which you must plan around.
- Mega Man Battle Network 6: Cybeast Gregar and Cybeast Falzar: The JudgeTree's main gimmick is a Hamiltonian Path Puzzle, where Mega will cause grass to grow wherever he steps off a square. Stepping on the grass (a traversed square) is considered an offence that will force Mega back to a checkpoint after getting hammered by a gavel, the damage of which increases depending on how many offences he's committed.
- Persona 5: The Mementos Depths has a series of puzzles in which the player must turn a series of yellow floor tiles blue without stepping on any of the blue tiles. Each puzzle has at least one blank tile that the player can safely step on at any time, and using these tiles efficiently is often the key to solving them.
- Pokémon Ruby and Sapphire: Sootopolis Gym has three tile-walking puzzles to get to the gym leader. All the tiles in each set must be walked over to unlock the stairs to the next section, and the player must end their walk right in front of the stairs forward, otherwise they are stuck walking over a cracked tile and ending up in the basement, where they have to fight trainers to make it back up to the starting floor.
- Q*bert has perhaps the earliest example in a video game. Starting in Level 3, if you step on a cube with the final color it returns to the either the intermediate color (Level 4) or the start color (Level 3 and Level 5 onward). Sequel Q*bert's Qubes has a similar handicap in later levels. This doesn't strictly require you to step on each cube exactly once (indeed, the triangular structure of the board makes that impossible), but does mean you have to think carefully about your routing if you want to get those last few cubes.
- Sonic Frontiers: A frequent type of minigames to obtain collectibles on the islands is a square grid of lit-up tiles that Sonic must turn off by stepping on them.
- Watchperson is an educational game for 8-bit micros, based on the Seven Bridges of Königsberg problem, in which the player must walk all the streets of a town exactly once.
- Zen Puzzle Garden requires visiting each square of sand once, and requires travelling in a straight line until the path is blocked. The game stops just short of a Hamiltonian path, as the player is able to freely move around the surrounding border when not raking sand.
Non-Video Game examples:
Tabletop Games- The Knight's tour is a Chess puzzle where a knight visits all 64 squares on the chess board, exactly once.
- Dungeons & Dragons:
- Subverted in the Advanced Dungeons & Dragons 1st Edition adventure UK1 Beyond the Crystal Cave. One of the leprechauns' riddles is asking how the Player Characters could cross each of the five bridges across a river once and return to the leprechauns. There is no way to do so, but the riddle has nothing to do with the adventure, so the PCs aren't punished if they fail.
- The Tomb of I'jin in the titular Tomb of the Nine Gods from Tomb of Annihilation has a puzzle where players must walk over a tiled floor's tiles in a certain order. If a character steps on the wrong tile, they'll be attacked by locusts, and if the damage drops their health to 0, that gets them Stripped to the Bone which prevents the victim from being revived conventionally.
Web Videos
- Ted:
- In the Ted-Ed Virus riddle, a scientist is trapped in a laboratory with a deadly virus, and the only way to escape without letting the virus out to endanger the world is to visit each infected room in the building once and trigger a self-destruct button in each room that will fill that room with concrete once the scientist leaves. It turns out that a true Hamiltonian path that finishes at the facility exit is impossible... but the facility entrance is currently uninfected, so the scientist can visit it twice as part of their route.
- The Ragnarok riddle is a variation — the serpent Jormungandr has swallowed Valhalla and contorted its body into a graph. In order to kill the serpent, Thor must travel the entire length of its body, blasting it with a continuous lightning spell, in an eulerian path that visits each edge of the graph exactly once.
- Another variation is the Penniless Pilgrim riddle, where your goal is to find a route that not only never doubles back on itself (though it can cross itself), but has a net value of zero when you reach your goal (with specific directions adding or subtracting from that value).
- In the Ted-Ed Virus riddle
Real Life
- The travelling salesman problem is a Hamiltonian path that attempts to minimize the overall travel cost between the nodes.