show/hide this revision's text 3 added 280 characters in body

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

Update


      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$?
show/hide this revision's text 2 added 233 characters in body

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

Update. 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.
show/hide this revision's text 1

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