An amateur proof that the puzzle game Net is NP-complete.
Abstract
The puzzle game Net, also known as FreeNet or NetWalk, is played on a grid filled with terminals and wires; each tile of the grid can be rotated and the aim of the game is to connect all the terminals to the central power unit avoiding closed loops and open-ended wires. We prove that Net is NP-complete.
A quick proof that the puzze game Inertia (see this version on Simon Tatham’s Portable Puzzle Collection) is NP-complete.
An amateur proof that the Tents puzzle game is NP-complete.
Abstract
We prove that the Tents puzzle game is NP-complete.
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).
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.
