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

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.

  • 0
    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.2012-05-05
  • 1
    @Xnyyr: that is why I started from a corner. My numbering transforms it to the fifteen puzzle http://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.2012-05-05
  • 0
    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.2012-05-05
  • 0
    @Xnyyr: that is why to start in the corner. It keeps the solved ones out of the way.2012-05-05
  • 0
    If you started by fixing the corner, then next you want to fix the second square, then you may have to swap the corner, so we had to disturb it, so how does your method work?2012-05-05
  • 0
    By which I mean, it doesnt work2012-05-05
  • 0
    What do you mean it keeps the solved ones out of the way? If you number the squares starting in upper left corner going right, then fix square 1,2,... we may have to backtrack, right, agree? Your method doesnt work, for my 9x9 example, agree?2012-05-06
  • 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