9
$\begingroup$

Define an $m\times n$ sliding puzzle to have an $m\times n$ grid of uniquely numbered squares, and the only valid move is to swap the special square numbered 0 with an orthogonally adjacent (up/down/left/right) square, and the puzzle is solved if the squares are rearranged by valid moves into a particular configuration where the special square is in the top-left corner (for example in ascending order when taken row by row then column by column). If given an arbitrary solvable puzzle, can the minimum number of moves in the solution be computed? If not exactly, hopefully a tight asymptotic bound? If it cannot be computed easily for an individual puzzle, what about a global upper bound?

I cannot get anything better than $\lfloor{\frac{m^2}{2}}\rfloor n + \lfloor{\frac{n^2}{2}}\rfloor m - m - n + 2$, which is obtained from considering the total vertical and horizontal distance over all squares excluding the special square, which each move can decrease by at most 1. The worst configuration seems to be when the whole grid is rotated 180-degrees about the centre. This bound is clearly tight for $(m,n)=(2,2)$ but nothing else. Moreover I cannot find a general solution to a solvable puzzle that has the same asymptotic number of moves as that bound, which may well be more interesting than the exact bound itself!

  • 0
    The asymptotic bound is definitely O(mn(m+n)), as your lower bound suggests. The strategy of placing each numbered square one by one, as is my usual route in solving one of these, takes O(m+n) moves to place each of m*n blocks. I don't know about the constant or anything exact, though - this is an interesting problem!2011-12-28
  • 0
    @Lopsy: No I don't think so, because that strategy takes $O((m+n)^2)$ moves per square.2011-12-29
  • 0
    What you are looking for is the diameter on the graph defined on solvable configurations with edges defined by single moves. I'm not sure this point of view will really help though.2011-12-29
  • 0
    @MarcvanLeeuwen: Yes, I am hoping that the local nature of the moves would make the problem tractable, given that it is usually not the case, like the maximum length of an optimal solution for a scrambled Rubik's cube..2011-12-29
  • 0
    @user21820 Where do you get the $O(m+n)^2$ figure for the 'place each square one by one' approach? Placing each square should only take moves proportional to its distance from its target position, which is $O(m+n)$. There are boundary effects for placing the last square in a row or shuffling the last couple of rows, but those costs are asymptotically small compared to the overall $O(n^3)$ cost.2012-04-25

2 Answers 2