How to solve the nxn puzzle

Usually it's easy to order all the rows except the last one. For most players the real problem of solving the nxn puzzle starts when only the last row is unordered.

The problem of the last row is that since the tiles cannot jump over each other, the last row cannot be reordered without touching the second to last row. So ordering the last row cannot be done independently of the ordering of the second to last row. Obviously any solving method needs to give an algorithm to order the two last rows in one operation. Below are presented two such methods using an 8x8 puzzle as an example. These same methods work on any nxn puzzle.

Method 1

Imagine we have ordered all the rows exept the last one. Now what shall we do? We need to break our second to last row in order to finish the puzzle. We can push the second to last row to the left and "fold" it by flipping the first of every two tiles down (see the tiles with white numbers in the image below; these are the tiles that belong to the second to last row). At this phase we don't care about the order of the tiles that belong to the last row.

After the tiles of the second to last row are placed like this, the tiles belonging to the last row are also brought from right to left along the second to last row and folded down, but in inverse order — starting with the 2 greatest numbers (the greatest first) and leaving the smallest numbers to the right. If the playing level n (in this example 8) is an odd number (3, 5, 7 etc.), the highest number of the second to last row and the highest number of the last row make a couple, in this order, so that the number belonging to the last row lands on top of the other number when folded. The last 3 tiles on the right are ordered by rotating them and the empty tile in the 2x2 corner area.

Now see the image below again. The second to last row (49—56) has been pushed from right to left and folded down. After that the tiles belonging to the last row have been brought from right to left in inverse order and folded down.





After the position in the image above all that needs to be done is to unroll the folding and to rotate the two last rows clockwise moving the tiles in the following order (each tile obviously moving where the empty tile is):
1) 57, 58, 59
2) 57, 58, 59, 60, 61
3) 57, 58, 59, 60, 61, 62, 63
4) 57, 58, 59, 60, 61, 62, 63, 56, 55
etc...

Note that each moving sequence ends in a position where the tile number 57 has the empty tile on its left side.

The tile number 57 needs to make 8 moves to get to where it belongs: to the left bottom corner. First it goes one step down and then 7 steps to the left.

So there will be 8 move sequences and each sequence (except the last one) has 2 tiles more to move than the previous one, the first sequence having 3 tiles to move.

The last sequence will move only the tiles that belong to the last row — really just moving the empty tile from the left corner to the right corner; at that point the second to last row is already ready and the last row is ordered, too, but the empty tile needs to be brought to the right corner.

So all in all the number of moves needed for this unfolding in this 8x8 puzzle is 3 + 5 + 7 + 9 + 11 + 13 + 15 + 7 = 70. The general formula for the number of moves needed for this unfolding in an nxn puzzle is ( n + 2 ) * ( n - 1 ).

Method 2

Method 2 is like method 1 except that the tiles are brought from right to left in a different order. Instead of bringing first the tiles that belong to the second to last row and then the tiles that belong to the last row (in inverse order), the tiles are brought to the left in such an order that there will be no need for the unfolding afterwards.

Since the tile in the bottom left corner will be 57 and the tile above it will be 49 when the puzzle is solved, these two tiles are the first two that are brought from right to left along the second to last row (57 first since it will be folded down). The next pair will be 58 and 50, the next after that is 59 and 51 etc.

Comparing the methods 1 and 2

Let's consider the starting point for both methods being when all but the last 2 rows are arranged. In both methods the tiles are brought along the next to the last row from right to left in a certain order and then folded down. Since the order of the tiles in the last 2 rows is random (within the range of solvability) at the starting point of these methods, there is no difference in efficiency of the methods at this phase.

However, there is a difference between the methods after the tiles are brought along the next to the last row and folded down. Using the method 1 one still has to roll out all the folded tiles and rotate the 2 last rows clockwise before the puzzle is solved. Using the method 2 there is no need for this unrolling and rotating, because the puzzle is solved as soon as all the tiles are folded down.

So the conclusion is that the method 2 is more efficient – it clearly uses less moves ( ( n + 2 ) * ( n - 1 ) moves less, to be exact). When trying to solve the puzzle in shortest possible time (counted in seconds and not moves) one factor to consider is that the method 2 requires to memorise or calculate the numbers of the first 2 tiles that are to be brought to the left along the next to the last row. On a 15 puzzle (4x4) this time to calculate or memorise could be significant, but on a 224 puzzle (15x15) it would be relatively much less, because it's really just the first two tile numbers that require time as they later on constitute an anchor point for the rest of the tiles: just add the numbers by 1 to find out which 2 tiles shall be brought home next.

It's fully possible to play 4 moves per second, at least when playing on the lower levels. In a 4x4 puzzle the method 2 uses 18 moves less than method 1, so the time saving could be around 4-5 seconds. If it takes more than this to memorise or calculate the order of the method 2, one might be better off using method 1, assumed that there is no need to stop thinking when using that method.

On the other hand, in a 15x15 puzzle the method 2 uses 238 moves less than method 1. That means about one minute in time even if the player make 4 moves per second. Most players perhaps wouldn't need a whole minute to calculate which numbers are the beginning numbers in the last two rows and so the method 2 could be recommended.