12
$\begingroup$

Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of shuffling the green piece with any of its 4 adjacent pieces (if they are within $S$). $S$ consists of squares, squares not in $S$ are static, $S$ can be any subset of squares of the $n^2$ square.

If two board configurations are reachable from eachother, is it possible to obtain an upper bound on the number of moves needed, given only the board size $n$, is it polynomial in $n$?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ So the green piece has the role of an empty space into which one can slide another piece. Nice question. $\endgroup$
    – Johan Wästlund
    Commented May 7, 2012 at 19:16
  • $\begingroup$ It should be polynomial, probably in n^3 moves, most definitely n^6. (I suppress the O().) To move any tile to a given place in the top row (except) for the last 2) should take at most n^2 moves. Although tricky, filling the top row and left column with the desired tiles should take n^3 moves. Now induct down to small n where you did your exhaustive analysis already. Gerhard "Ask Me About System Design" Paseman, 2012.05.07 $\endgroup$
    – Gerhard Paseman
    Commented May 7, 2012 at 19:50
  • $\begingroup$ @Gerhard The problem is that we often have to back track to fill the next column, thus changing the previous filled column. We cant normally enumerate the squares and fix one at a time, without disturbing the previously fixed ones. I think this strategy works when S is the n^2 square though. $\endgroup$
    – Xnyyrznaa
    Commented May 7, 2012 at 19:56
  • $\begingroup$ The above assumes there is enough space at any time to do "cycle" moves. If S is constrained so that one cannot move a cycle of blocks freely, then we need to know more about the region of traversal. As long as S and appropriate subregions always contain a loop, the above analysis should apply, and give you an O(n^4) bound. Gerhard "Ask Me About System Design" Paseman, 2012.05.07 $\endgroup$
    – Gerhard Paseman
    Commented May 7, 2012 at 20:19
  • $\begingroup$ Actually, if S is sufficiently "snaky", you may need n^6. Think insertion sort. Gerhard "A Twisted Imagination Sometimes Helps" Paseman, 2012.05.07 $\endgroup$
    – Gerhard Paseman
    Commented May 7, 2012 at 20:35

1 Answer 1

Reset to default
3
$\begingroup$

Not a solution, just three observations that might trigger other ideas.

  1. The pieces filling $S$ continue to fill $S$ at all times. In other words, the shape of $S$ is fixed, and lattice cells exterior to $S$ are irrelevant as they can never be used.

  2. In order to move a particular tile from one square $a$ to another square $b$, there must be a simple cycle in $S$ on which they both lie. For example, in the first illustration below (where $X$ plays the role of the empty/green square, and $0$ and $1$ are red and blue tiles), the 1 in the lower-left corner cannot reach the upper-right corner because a connecting cycle pinches in the middle and so is not simple.

  3. In some sense the $2 \times n$ example illustrated feels like the worst case for moving one tile from end to end of $S$, and that requires $2 n (n-1)$ moves, if I've counted correctly.


      Sliding Blocks

Update1. Zack Wolske's sequence of moves is more efficient and shows the $2 \times n$ example only needs a linear number of moves. Gerhard Paseman's width-1 ring, however, clearly needs a quadratic number of moves.

Update2. I think the key parameter is, not the OP's $n$, but rather $m=|S|$, the number of cells in $S$. We have examples that require $\Omega(m^2)$ tile moves. Can anyone think of an pair of configurations that requires more than a quadratic number of moves in $m$?

Improve this answer
$\endgroup$
6
  • $\begingroup$ In 3, you only need $n-1 + 5(n-2) + 3 = 6n-8$ moves to go corner to corner as pictured. The first $n-1$ slides the bottom row so that the blank is behind the $1$, and it takes $5$ moves to go from X10 to 0X1 in the bottom row by pushing the 0s around the top row. After $n-2$ of those, the blue 1 is below its goal, and the final $3$ moves it up. $\endgroup$
    – Zack Wolske
    Commented May 8, 2012 at 2:19
  • $\begingroup$ Yes. However it is possible that S is a square ring of squares of width 1 with an extra square in one corner, so that the general case of moving a square from one square to another square involves roughly the square of the number of squares in S. Gerhard "Likes E's of Suppressing O's" Paseman, 2012.05.07 $\endgroup$
    – Gerhard Paseman
    Commented May 8, 2012 at 3:33
  • 4
    $\begingroup$ We should have MO Awards periodically, and you Joseph should get the Best Diagrams Awards everytime. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented May 8, 2012 at 6:16
  • $\begingroup$ @Zach: Yes, your moves are more efficient: Nice! $\endgroup$
    – Joseph O'Rourke
    Commented May 8, 2012 at 11:25
  • $\begingroup$ @Gerhard: Your width-1 ring is a clear example of needing about $n^2/2$ moves to reposition a tile from one corner to the other. Nice example! $\endgroup$
    – Joseph O'Rourke
    Commented May 8, 2012 at 11:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .