Box Shift Puzzle

While thinking about simple “puzzles” that seem hard at a first glance, but have not enough rules and structural constraints that make it easy to prove that they are NP-complete, I designed the following game (but perhaps it has already a name … let me know if you know it 🙂 ):

  • a $N \times N$ grid contains $S \times S$ blue boxes in the upper left area, the home area; each box occupies a cell;
  • a column (or row) that contains at least one box is picked at random and it is shifted downward (or rightward). If a box exits from one border it re-enters on the opposite site;
  • the random shift is repeated maxmoves times (e.g. $maxmoves = S^2$);
  • the aim of the game is to repack the boxes in the upper left home area, using at most maxmoves upward column shifts or leftward row shifts.

A simple javascript version of the game can be played here.

Can the blue boxes be packed in the upper-left 4×4 yellow area using at most 16 moves?

The rules are simple, but even in a small game with a 4×4 home area it’s hard to find the correct shift sequence …

Continue reading

Rolling a cube can be tricky

An amateur proof that the rolling cube puzzle is NP-complete.

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.

Rolling a cube can be tricky 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).