Boulder Dash

Description

Boulder Dash is a single-player game where a character (a man named Rockford) moves in a square grid, controlled by the player.

A level is a square grid of $n \times n$ tiles and a target number $d$ of diamonds to collect. When a level starts, each tile can either be empty or contain one of:

• Rockford,
• dirt,
• a rock,
• a diamond,
• an unbreakable rock,
• an enemy (of one of several enemy types).

Time is discretized, and the game’s state updates at fixed intervals. At each time step:

• Rockford can move to a neighboring tile;
• every rock without support will fall to the tile below;
• every enemy moves to a neighboring tile, if one is available (the exact pattern depends on the enemy type).

Rockford can move through empty tiles, diamond tiles, or dig through dirt tiles, leaving them empty. If he moves into a diamond tiles, he collects the diamond (turning the tile into an empty tile). If he moves horizontally against a rock which has space on its other side, the rock is also pushed horizontally to allow Rockford to take its place. Enemies follow the borders of empty tiles in a clockwise pattern. This pattern is predictable, but not fixed: if a border that was blocking an enemy disappears, the enemy will go through it the next time it arrives there. If the player “frees” an enemy by digging through a tile that previously blocked its path, the enemy will go through it the next time it reaches that place. No entity can pass through or affect unbreakable rocks.

If a rock is in the tile above an enemy or Rockford, and has been falling for at least one time step, it “kills” the entity below: if the entity was an enemy, it is replaced with a diamond; if it was Rockford, Rockford dies.

Ending a level

When $d$ or more diamonds are collected, an exit door appears. Reaching this exit door wins the level.

Rockford dies (loses one life and starts over) if:

• he and an adversary end up in the same tile (because of a movement by Rockford, the adversary, or both)
• a rock falls on him (if a rock is immobile above the character, the rock instead stays in position until he moves); or
• the time limit expires and Rockford hasn’t reached the exit door.

Initially Rockford has 3 lives, and more can be gained while playing. When no more lives are left the games is lost.

Computational complexity

The problem of deciding whether a level of Boulder Dash is winnable is NP-complete. This has first been proved by [2], then by [1] using a simpler method.

[1] shows that Boulder Dash levels implement single-use paths and location traversal (meaning that the player must visit a set of locations to win). This allows reduce the Hamiltonian cycle problem to a Boulder Dash instance in the following way: Choose any undirected $3$-regular graph $G$; choose a vertex $v$ of $G$, to which we attach a new vertex $u$. Starting from $G$, build a Boulder Dash level where:

• each vertex in $G$, except $u$, corresponds to a diamond to be collected in the level;
• $u$ corresponds to the exit door;
• each edge in $G$ corresponds to a single-use path between the two associated locations. Solving the level involves finding a path starting in $v$, going through all the locations except $u$, then reaching $v$ again and going to $u$, without using the same edge twice. This is equivalent to finding a Hamiltonian cycle in $G$, which is NP-hard [4]. This proof does not use the player’s ability to dig through dirt or get killed by adversaries.

An earlier proof was given in [2], based on Boulder Dash’s similarity with other block-pushing games without gravity. [2] shows that Boulder Dash levels can contain four constructions (one-way paths, forks, XOR crossings, and NAND crossings). This lets them apply [3]’s proof that block-pushing games featuring these constructions are NP-complete, which uses a reduction from $3$-coloring.

References

[1] Giovanni Viglietta, “Gaming is a hard job, but someone has to do it!”, Theory of Computing Systems, 2014.

[2] E. Friedman, “Pushing blocks in gravity is NP-hard”, 2002.

[3] E. D. Demaine, M. Hoffman, “Pushing blocks is NP-complete for non-crossing solution paths”, in CCCG 2001.

[4] M.R. Garey, D. S. Johnson, R. E. Tarjan, “The Planar Hamiltonian Circuit Problem is NP-Complete”, in SIAM Journal on Computing, 1976.

@misc{cog:boulder-dash,
    author = "{CoG contributors}",
    title  = "{Boulder Dash}",
    year   = "2026",
    url    = "https://www.isnphard.com/i/boulder-dash/",
    note   = "[Online; accessed 2026-01-15]"
}