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.

enter image description here

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?

I implemented this variant in Javascript and it can be played online here (even small grids seem not so easy to solve).

  • $\begingroup$ a bit confused about the setup, what do shift operations do? do you shift the entire grid, or just one cell, or they operate on an entire row/column? $\endgroup$
    – AmeerJ
    Nov 30 '19 at 12:47
  • $\begingroup$ If you do not place a bound on the number of shifts, this is an instance of the string isomorphism problem (where the grid is the string, and you consider the group of permutations generated by the shifts). $\endgroup$ Nov 30 '19 at 13:05
  • 3
    $\begingroup$ Aha, but my comment is not interesting, because (as long as both dimensions of the grid are at least $2$) the generated group is either the full symmetric group or the alternating group, depending on parity of the grid size. Thus, the unbounded problem is easy. $\endgroup$ Nov 30 '19 at 14:56
  • 3
    $\begingroup$ I think this resembles a Rubix cube problem which is NP-complete (arxiv.org/pdf/1706.06708.pdf), you can think of the circular shifts as rotating a vertical/horizontal slice of the cube, although they have a couple of difference, like the flattened surface of a cube is not a square, and the slice rotations correspond to a circular shift of size $n$, but maybe the proof could inspire a reduction for this problem $\endgroup$
    – AmeerJ
    Nov 30 '19 at 15:14
  • 1
    $\begingroup$ @AmeerJ: thanks! The NP-complete $n \times n \times 1$ variant of Rubik's Cube (Rubik's Square) is also very interesting and similiar; I'll check if that proof can be useful. $\endgroup$ Nov 30 '19 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.