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

Reply

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).