Sliding Puzzle in Python

As part of making a constructive solution to Enigma 1444 I wrote a some Python code to capture a simple "sliding puzzle" solving algorithm. (You can see my code on the Enigmatic Code site).

This is all very well, but I wanted to see the algorithm in action. So instead of cutting up pieces of paper and sliding them around my desk, I wrote a Tk app using Python.

You need to specify the puzzle dimensions on the command line when you start the program. In this case for a 5×5 grid I used:

python sliding-puzzle.py 5 5

A window should show up with the puzzle in it, and you can interact with it by clicking on a tile (adjacent to the blank square) and it should move appropriately. It will keep track of the number of moves and the elapsed time, and if you select an appropriate Target from the drop-down menu it will tell you when you achieve it as a solution. You can choose from "Normal", which is the tiles in their "natural" position, or "Reversed", which is the tiles in reverse order. Note that it is not possible to solve a grid into the "Reversed" configuration for all puzzle dimensions, but that's what the Enigma is about, so that's the default.

There's a button marked Scramble. If you press that the grid will be placed into a random (but not impossible to reach from the initial position) configuration.

There's also a button marked Solve, which if you click it will start solving the puzzle using the algorithm I wrote for the Enigma puzzle.

When you click Solve the puzzle shows you the piece it is currently trying to place (by highlighting the piece in yellow), and also the position it is trying to place it in (by placing a yellow highlighted border around it). Once a piece is placed it is slightly greyed out. Also the Solve button changes to a Stop button, should you wish to abandon the automated solution.

If the target configuration is not possible, the message area will display Impossible Target, and the app will beep.

• Download sliding-puzzle.py

I used this to demonstrate that the smallest solution for Enigma 1444 - a 10×5 puzzle - is indeed possible 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/s. (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. (Update: I reversed the 10×5 puzzle manually using this program in 824 moves, in 10m27s).

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.

If you like you can specify a target configuration on the command line. For example you can try to solve the puzzle for which Sam Lloyd offered $1,000 by running:

python sliding-puzzle.py 4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14

and then clicking Solve - but you'll find the solution is impossible.

There's still a few rough edges in the program, and it's not particularly efficient, but it's works sufficiently well for me to see my solution to Enigma 1444 working, so I'm unlikely to take it further.

I've tested it on Mac OS X 10.8.3 under Python 2.7.4 and Python 3.3.1 with Tk 8.5.9, and on Linux (Ubuntu 12.04.2) under Python 2.7.3 and Python 3.2.3.