10
$\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!

$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$
    – Lopsy
    Dec 28, 2011 at 18:31
  • $\begingroup$ @Lopsy: No I don't think so, because that strategy takes $O((m+n)^2)$ moves per square. $\endgroup$
    – user21820
    Dec 29, 2011 at 2:06
  • $\begingroup$ 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. $\endgroup$
    – Marc van Leeuwen
    Dec 29, 2011 at 15:05
  • $\begingroup$ @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.. $\endgroup$
    – user21820
    Dec 29, 2011 at 15:53
  • $\begingroup$ @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. $\endgroup$
    – Steven Stadnicki
    Apr 25, 2012 at 17:11

2 Answers 2

Reset to default
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ You, and Lopsy, are right. I was very blur and I did not realise that the empty square could be moved in front, though that is how I do solve the puzzle. However, can you get a better lower bound on the number of moves needed? $\endgroup$
    – user21820
    May 2, 2012 at 9:44
  • $\begingroup$ Well, it would be relatively straightforward to find a more precise bound for the number of moves in the flip position; I just wanted an estimate to show the right order, but you could explicitly do the double-sum. On the other hand, that position probably has a move count pretty close to its bound, because (at least for $m=n$) it can be decomposed into a set of cycles (concentric rings around the center). It's not clear that there's an easily-definable position with a greater total displacement than that position, though, or how lower bounds could be much-improved (the problem is known-hard) $\endgroup$
    – Steven Stadnicki
    May 2, 2012 at 15:34
  • $\begingroup$ 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. $\endgroup$
    – user21820
    May 6, 2012 at 4:38
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .