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