By 15 Puzzle, I mean the game where you try to slide numbered tiles into some kind of order in a four-by-four square.
Let’s say you’ve put the the first two rows in order, i.e., 1 through 8. You now want to put 9 - 15 in order in the bottom rows. What’s the maximum number of moves you’ll have to make? I’m usually pretty good at combinatorics, but I’m having trouble setting this up as a solvable problem.
I’ll consider sliding one tile or a row of tiles (or a partial row) to be a single move.
In general this sort of question of finding the shortest move sequence, even for a puzzle with nice group-theoretic properties like this puzzle or Rubik’s cube, seems to be hard to solve analytically. (According to the Wikipedia page, Ratner & Warmuth proved that the question is NP-hard even for the n*n generalization of the 15 puzzle.) It’s easy to write a breadth-first search routine, of course, but memory limitations rapidly become a problem. (They aren’t an issue in your particular problem, of course.)
You can find trivial bounds: a lower bound based on how many states you can possibly reach in n moves (and counting the total number of states in the puzzle), and an upper bound based on your most efficient algorithm for solving the puzzle, applied to the worst possible starting case. Unfortunately these bounds don’t usually agree, and you need more powerful arguments to get better bounds.
[I haven’t posted my bounds, since you might want to work them out on your own; but I can give them if you want.]
For an example of an explicit solution algorithm, try to count how many moves are required, in the worst case, to place the 9 and 13 (the left column); next, how many moves are required to place the 10 and 14, once the 9 and 13 are placed; and finally, how many moves are required to move the 11, 12, and 15 into their positions.
Or, in this case, you can do a breadth-first search and find the exact answer by brute force. The search space is small enough that you don’t need to worry about optimization; just use your favorite language.
Isn’t it impossible to solve one backwards (that is to say descending order)?
That’s correct, in the sense that a starting configuration all in row-major ascending order followed by an empty tile in the bottom right, can’t be transformed to a configuration in row-major descending order with an empty tile in the bottom right.
It’s not too hard to see why this is the case. First, think of the squares on the board as colored black and white like a chessboard. With every move, clearly, the color of the location of the blank square switches. So, if a sequence of moves takes the blank square from the bottom right all over the place and then back to the bottom right, it must have an even length.
The other thing to look at is the number of out-of-order pairs of distinct tiles on the board at any given moment (where the blank square is considered to come, in the ordering, after all the numbers, as it does in the starting configuration); it’s easy to see that every move either increases or decreases this number by one. Thus, after an even sequence of moves from the starting configuration, there should be only an even number of such out-of-order pairs.
However, examining the reverse configuration in mind, we see that there are 15*14/2 = 105 many out of order pairs, an odd number, despite the blank square having returned to the bottom right. Thus, we see that this configuration cannot be achieved by sliding tiles in the desired manner.
Sorry, this was incorrectly worded. Any move changes this number by an odd amount. (A horizontal slide will increase or decrease this number by one; however, a vertical slide may produce larger changes, though still odd-sized ones).