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


1 Answer 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.

  • $\begingroup$ Yea, this seems convincing for most cases, or when S is n^2, but S can be any subset of squares of the n^2 grid, so its not clear to me why (if) we will never have to disturb some already placed pieces. $\endgroup$ May 5, 2012 at 4:26
  • 1
    $\begingroup$ @Xnyyr: that is why I started from a corner. My numbering transforms it to the fifteen puzzle en.wikipedia.org/wiki/Fifteen_puzzle where you do exactly this. The corners are out of the way. You might have to exchange two labels to solve the parity problem, but you have the freedom to do that. $\endgroup$ May 5, 2012 at 4:30
  • $\begingroup$ Well if S is an 9x9 grid, with the middle 7x1 segment of the second row removed, then we cant swap the n+1 th square of first row without disturbing it's n'th square. $\endgroup$ May 5, 2012 at 4:43
  • $\begingroup$ @Xnyyr: that is why to start in the corner. It keeps the solved ones out of the way. $\endgroup$ May 5, 2012 at 4:49
  • 1
    $\begingroup$ @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. $\endgroup$ May 6, 2012 at 0:43

You must log in to answer this question.

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