<p>Consider the following simple problem (puzzle): given </p>

<ul>
<li>a <span class="math-container">$N \times N$</span> <span class="math-container">$c$</span>-colored grid <span class="math-container">$G$</span> </li>
<li>a <span class="math-container">$N \times N$</span> <span class="math-container">$c$</span>-colored <em>target</em> grid <span class="math-container">$G_T$</span></li>
<li>a number <span class="math-container">$m$</span> represented in unary</li>
</ul>

<p>Can we transform <span class="math-container">$G$</span> into <span class="math-container">$G_T$</span> using at most <span class="math-container">$m$</span> 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 <em>circular</em>: the cell that exits from a border  re-enters the grid on the opposite side.</p>

<p><a href="https://i.sstatic.net/Ek5H9.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Ek5H9.png" alt="enter image description here"></a></p>

<blockquote>
  <p>Q1. Has this game/problem a name?<br>
  Q2. Is it NP-complete?<br>
  Q3. What about the variants in which <span class="math-container">$c$</span> is fixed (e.g. <span class="math-container">$c=2$</span>) or the grids are <span class="math-container">$N \times k$</span> with <span class="math-container">$k$</span>-fixed?</p>
</blockquote>

<p><strong>Update:</strong></p>

<p>We can also consider the simpler variant (I called it "Block Shift Puzzle") in which:</p>

<ul>
<li><span class="math-container">$c = 2$</span>, i.e. the empty grid (color 1) contains some colored boxes (color 2);</li>
<li>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; </li>
<li>and the columns/rows can only be shifted in one direction (upward/leftward).</li>
</ul>

<blockquote>
  <p>Q4. Is this simpler variant polynomial-time solvable? </p>
</blockquote>

<p>I implemented this variant in Javascript and it can be <a href="http://www.nearly42.org/games/boxshift/" rel="nofollow noreferrer">played online here</a> (even small grids seem not so easy to solve).</p>

CC BY-SA 4.0
2019-11-30T12:47:49.293Z
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?
AmeerJ
CC BY-SA 4.0
2019-11-30T13:05:08.110Z
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).
Emil Jeřábek
CC BY-SA 4.0
2019-11-30T13:13:32.470Z
@Ameer: I clarified what a shift move is (also see the figure).
Marzio De Biasi
CC BY-SA 4.0
2019-11-30T14:56:22.007Z
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.
Emil Jeřábek
CC BY-SA 4.0
2019-11-30T15:14:06.190Z
I think this resembles a Rubix cube problem which is NP-complete (https://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
AmeerJ
CC BY-SA 4.0
2019-11-30T17:44:31.597Z
@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.
Marzio De Biasi
CC BY-SA 4.0
2020-10-25T06:34:43.837Z
Was your inspiration this game? https://en.wikipedia.org/wiki/Labyrinth_(board_game)
domotorp
CC BY-SA 4.0
2020-10-25T06:36:48.820Z
Apparently this game was recently shown to be NP-complete: https://drops.dagstuhl.de/opus/volltexte/2018/8821/pdf/LIPIcs-FUN-2018-30.pdf
domotorp
CC BY-SA 4.0
2020-10-26T21:43:59.130Z
@domotorp: interesting paper, but that problem is very different; in my setting the target configuration is given as input and there are no fixed blocks. I was not inspired by any game, but it has simple rules, so perhaps it exists. An NP-complete proof should probably use the limit $m$ on the moves, but the lack of fixed structures makes it unmanageable (perhaps the unlimited moves version is easier). Note that even the much simpler "bichromatic monotone" variant (I made a simple online playable version of it) seems hard to solve in polynomial time.
Marzio De Biasi
<reference-request><np-complete><puzzles>
Reconstructing a colored grid with vertical and horizontal shifts
Marzio De Biasi
# Reconstructing a colored grid with vertical and horizontal shifts

(Asked by: username_0 on 2019-11-29)

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](https://i.sstatic.net/Ek5H9.png)](https://i.sstatic.net/Ek5H9.png)

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

**Update:**

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](http://www.nearly42.org/games/boxshift/) (even small grids seem not so easy to solve).

**Tags:** reference-request, np-complete, puzzles

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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).  
> **username_0**: @Ameer: I clarified what a shift move is (also see the figure).  
> **username_2**: 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.  
> **username_1**: I think this resembles a Rubix cube problem which is NP-complete (https://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  
> **username_0**: @username_1: 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.  
> **username_3**: Was your inspiration this game? https://en.wikipedia.org/wiki/Labyrinth_(board_game)  
> **username_3**: Apparently this game was recently shown to be NP-complete: https://drops.dagstuhl.de/opus/volltexte/2018/8821/pdf/LIPIcs-FUN-2018-30.pdf  
> **username_0**: @username_3: interesting paper, but that problem is very different; in my setting the target configuration is given as input and there are no fixed blocks. I was not inspired by any game, but it has simple rules, so perhaps it exists. An NP-complete proof should probably use the limit $m$ on the moves, but the lack of fixed structures makes it unmanageable (perhaps the unlimited moves version is easier). Note that even the much simpler "bichromatic monotone" variant (I made a simple online playable version of it) seems hard to solve in polynomial time.  

---

## 0 answers

