Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
Warning: Ross' answer is wrong –  user1708 May 6 '12 at 1:08
add comment

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.

share|improve this answer
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. –  user1708 May 5 '12 at 4:26
@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. –  Ross Millikan May 5 '12 at 4:30
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. –  user1708 May 5 '12 at 4:43
@Xnyyr: that is why to start in the corner. It keeps the solved ones out of the way. –  Ross Millikan May 5 '12 at 4:49
@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. –  Steven Stadnicki May 6 '12 at 0:43
show 3 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.