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.