3
$\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, 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 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$?

  • 0
    Warning: Ross' answer is wrong2012-05-06
  • 0
    http://mathoverflow.net/questions/96242/sliding-blocks-puzzle2012-05-13

1 Answers 1