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!