A quick proof that the puzze game Inertia (see this version on Simon Tatham’s Portable Puzzle Collection) is NP-complete.
Intertia is NP-complete
Reply
Monthly Archives: November 2012
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).