**From New Scientist #2605, 26th May 2007**

You may be familiar with the 15-tile puzzle that starts as shown, with one gap, after which you can slide into the gap any one of the tiles adjacent to it.

Continuing in this way you can rearrange the tiles into all sorts of orders.

My nephew is so good at his 15-tile puzzle that I have given him a larger version. It is again a rectangle, with more than two tiles along each side, the tiles are numbered 1, 2, 3 …, and it starts with them in the natural order and with the gap in the bottom right-hand corner.

My nephew has mastered the new version. For example, in less than quarter of an hour he can rearrange the tiles into their reverse order, ending up with … 3, 2, 1 and gap in the bottom row. He has also looked into the properties of the numbers on the tiles and has noted, for example, that their sum is divisible neither by 2 nor by 3.

How many tiles are there in his new version of the puzzle?

[enigma1444]

### Like this:

Like Loading...

By analysis we can place certain conditions on the dimensions of the puzzle. This Python program considers

m×npuzzles for increasingm+n, and outputs those that match the conditions. By default it outputs the first 10 values it finds. I’m assuming that we want the smallest puzzle (by number of tiles) that satisfies the conditions. It runs in 40ms.Solution:The new version of the puzzle has 49 tiles (in a 5×10 grid).It’s all very well to solve the problem analytically, but I like constructive solutions, so I thought I would write a program to determine the moves to invert an

m×npuzzle.This program encapsulates a simple solving strategy (so it won’t find the shortest possible sequence of moves – but that’s an NP-hard problem), but even so it ended up being more fiddly than I’d imagined at the outset.

For a 5×10 puzzle it reverses the squares in 1394 moves (or 1300 if asked to reverse a 10×5 grid), so to solve the puzzle using this strategy in “less than quarter of an hour” (i.e. 900 seconds) you would have to be making moves pretty quickly (or use a cleverer strategy), but it would be possible.

The next smallest solution is 97 tiles in a 7×14 grid. This program takes 3872 moves (or 3828 for the 14×7 grid) to solve that, so it’s unlikely you would be able to use this strategy to solve larger puzzles in the required time.

By considering the distances that each square has to move in order to invert the grid we can place a lower bound of 357 moves on the 5×10 puzzle, and 1003 moves on the 7×14 puzzle, so it’s possible that a larger puzzle could be solved manually in 15 minutes.

Here are the number of moves this program generates for the first ten possible solutions.

I coded up a simple Tk UI to see this code in action (and allow you play with general

m×npuzzles). Rather than post the code here (adding the UI makes it about twice as long), you can download it from my blog [ jimpulse.blogspot.co.uk/2013/04/sliding-puzzle-in-python.html ] which also contains a description of how the code operates.You can use the program to slide tiles around yourself, or get the algorithm given above to solve a puzzle.

I used this program to demonstrate that it is indeed possible to reverse a 10×5 puzzle in less than 15 minutes, and this is the configuration that the program is set to solve by default. Just fire it up, hit “Solve” and sit back and enjoy the show. It takes 1300 moves and on my machine it runs in about 4 minutes.

The default animation speeds mean you would have to pretty nimble-fingered to keep up with the program in real life (or use a cleverer algorithm to solve puzzles in fewer moves), as it makes around 5 moves per second. (There are command line parameters if you want to change the speed of moves). I manually reversed a 5×5 puzzle in 3 minutes (three times slower than my program), so a 10×5 puzzle should certainly be possible in under 15 minutes by hand, even using this simple algorithm.

The next smallest solutions are also solved in less than 15 minutes by the program (but only just). A 14×7 puzzle is solved in 3828 moves, and a 11×10 puzzle is solved in 4122 moves. These both take about 14 minutes. After that a 22×5 solution is solved in 6344 moves and takes about 21 minutes.