Consider the following simple problem (puzzle): given
- a $N \times N$ $c$-colored grid $G$
- a $N \times N$ $c$-colored target grid $G_T$
- a number $m$ represented in unary
Can we transform $G$ into $G_T$ using at most $m$ horizontal or vertical shifts.. In a shift an entire column or row is shifted by one cell (columns vertically; rows horizontally) and every shift is circular: the cell that exits from a border re-enters the grid on the opposite side.
Q1. Has this game/problem a name?
Q2. Is it NP-complete?
Q3. What about the variants in which $c$ is fixed (e.g. $c=2$) or the grids are $N \times k$ with $k$-fixed?
We can also consider the simpler variant (I called it "Block Shift Puzzle") in which:
- $c = 2$, i.e. the empty grid (color 1) contains some colored boxes (color 2);
- the target configuration is simply a square area in the upper-left part of the grid, i.e. the boxes must be "packed" in the upper-left part of the grid;
- and the columns/rows can only be shifted in one direction (upward/leftward).
Q4. Is this simpler variant polynomial-time solvable?