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
    @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

3

As noted in the comments, the asymptotic bound is precisely $\Theta(n^3)$ (For the general case, with $m\geq n$, it's actually $\Theta(m^2n)$; for clarity's sake I'm just considering $m=n$ but it's easy to adapt most of these arguments to the general case). The '180 flip' position establishes the lower bound, since there are $n^2-(\frac{n}{3})^2 = \frac{8}{9}n^2$ tiles in the outer third of rows and columns (that is, with $x$ or $y$ coordinate either $\lt n/3$ or $\gt 2n/3$) and each of those tiles must move at least $n/3$ places to get to its final positions. Any one move can only change the distance-from-target of one tile by one unit, so that sets the $O(n^3)$ lower bound.

The upper bound comes from the standard 'fill cells one by one' approach. Since each tile is no more than $2n$ cells from its final position and moving it a single square takes $O(1)$ moves (for instance, to move a cell into an empty square above it and leave the empty square above it, move the empty square D,R,U,U,L) we can fill all but one of the squares in a row in $O(n^2)$ time without having to displace any already-set tiles. The final square in a row takes more care, but that one can be filled by shifting the leftmost tile in a row down, shifting the rest of the row right, setting the final tile into either of the two rightmost squares (without disturbing any of the other cells in the row) and then shifting the rest of the row back; this is a complicated process but only adds $O(n)$ moves per row. A similar approach sets the bottom row once the rest of the puzzle is complete: $O(n)$ moves suffice to move any three tiles from the bottom row into a 'canonical position' in the bottom-right corner, perform a standard 3-cycle on them, and then undo the movements to bring them back to their original locations. Since any even permutation of the tiles in the bottom row can be expressed as a product of $O(n)$ 3-cycles, this adds $O(n^2)$ time to the total effort. In the $m\geq n$ case, the above procedure should yield $O(m^2n)$, the same as your estimate.

'All' that's left at this point is the hardest part of the problem: establishing the constant on the $n^3$ term...

  • 0
    The double sum gives the bound I stated. I didn't know getting the lower bound is known to be hard though! Do you know of any better bound? For example when $m=n=3$ the first move will not decrease the total distance but actually increase it. But this is just an extra 2 moves, whereas I think the best bound would be about twice my bound. For the flip position, it seems as if the optimal solution mostly moves the squares in its own ring, and not between rings. If correct, this gives a lower bound of $O(\frac{8}{3}n^3)$ moves for an $n\times n$ puzzle.2012-05-06
2

The 2x3 puzzle was called the Moving Day puzzle by Sam Loyd. As a graph, there is a high amount of symmetry, as shown below. You are looking for the girth for these graphs. It's best to shrink away the corners, as they add to the size of the graph.

Then just find the Diameter. It won't be high, due to symmetry.

Moving Day Graph