Sliding blocks puzzle 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$?
 A: Not a solution, just three observations that might trigger other ideas.


*

*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.

*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.

*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.
      
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$?
