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.
EDIT 2026-04-24 the proof is wrong! As pointed out by Andy Tockman (see his comment below), there’s no rule that prevents the ball from crossing the same stop cell multiple times or coming to rest against a wall in the same location (and therefore it could cross the same gadget multiple times if it’s part of a loop). Probably the only way to “save” the NP-completeness is to require a gem to also act as a stop for the player-controlled ball (and replace the stop walls near the ball with mines); in this case, when the gem in a gadget is taken, the ball could no longer pass through the same gadget.
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.
