A quick proof that the puzze game Inertia (see this version on Simon Tatham’s Portable Puzzle Collection) is NP-complete.

# Category Archives: CSTheory

# The Complexity of Camping

An amateur proof that the `Tents`

puzzle game is NP-complete.

**Abstract**

We prove that the `Tents`

puzzle game is NP-complete.

# Rolling a cube can be tricky

An amateur proof that the rolling cube puzzle is NP-complete.

**Abstract**

We settle two open problems related to the rolling cube puzzle: Hamil-

tonian cycles are not unique even in fully labeled boards and rolling

cube puzzle is NP-complete in labeled boards without free cells and with

blocked cells.

click here to download the paper

NOTE: another example of two distinct Hamiltonian cycles in a fully labeled board has also been found by Pálvölgyi Dömötör (see this post on mathoverflow).

# Have fun with Boulder Dash

An amateur proof that the popular game is NP-hard.

**Abstract**

Boulder Dash is a videogame created by Peter Liepa and Chris Gray in 1983 and released for many personal computers and console systems under license from First Star Software. Its concept is simple: the main character must dig through caves, collect diamonds, avoid falling stones and other nasties, and finally reach the exit within a time limit. In this report we show that the decision problem “*Is an $N\times N$ Boulder Dash level** solvable?*” is NP-hard. The constructive proof is based on a simple gadget that allows us to transform the Hamiltonian cycle problem on a 3-connected cubic planar graph to a Boulder Dash level in polynomial time.

click here to download the paper

NOTE: the same result has been proved by G. Viglietta in the paper: Gaming Is a Hard Job, But Someone Has to Do It! ; his proof, which is embedded in a more general and powerful framework that can be used to prove complexity of games, doesn’t require the *Dirt* element.