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
    http://mathoverflow.net/questions/96242/sliding-blocks-puzzle2012-05-13

1 Answers 1

1

Hint: consider the configurations with one red square and the rest (except the green) blue. Can you prove that any one can be converted to any other within a polynomial number of moves? Then you are there-if the number of red and blue squares differ, you can't fix that. If they don't, number the red and blue squares in the two configurations. Fix the upper left corner, then the square next to it, and so on. There are less than $n^2$ squares to fix. You still need to prove you won't disturb the ones you have already solved, but that shouldn't be hard except for the last square in a row.

  • 1
    @RossMillikan I think what you're missing is that Xnyyr wants to play the game not on the square itself, but on some subset of the square; this means that the classic solve techniques don't quite work because if you 'remove' the solved squares from the equation, the remaining squares aren't necessarily connected any more.2012-05-06