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 …
The Box Shift Puzzle could be analyzed from a computational complexity perspective:
Input: given a $N \times N$ filled with $S \times S$ boxes, and an integer $M$ represented in unary.
Question: can the $S \times S$ boxes be packed in the upper-left corner (home area) using at most $M$ column or row shifts?
Open problem: what is the complexity of the Box Shift Puzzle? Is it NP-complete?
Also the following variants (or any combination of them) seem interesting:
- V1. in addition to the initial configuration, a target configuration is given and the problem is to decide if the initial configuration can be transformed into the target configuration using at most $M$ moves;
- V2. one of the side of the grid is fixed (the size of the grid is $N \times k$);
- V3. the columns (resp. rows) can be moved in both up-down directions (resp. left-right);
- V4. the boxes cells could be colored with colors in $[1..c]$
… I’ll spend some time on it, if I find something interesting I’ll update this page.