Home           About           Downloads

15 Puzzle solver

This program depicts a method for solving the 15 puzzle.

I wrote this to see if the explicit method I was using to solve this puzzle could be encoded, and whether there were puzzle instances my method would not work on.

A ran a separate testbed app that did thousands of runs to determine the success rate of various methods for solving this puzzle. For each run, a random instance of the puzzle was produced by making over 100 random moves. In this way, it is clear that the instance of the puzzle would be solvable.

An earlier method I used worked ~80% of the time for 100,000 runs. The method I present here was successful for all 100,000 runs, and then millions of runs after that.

When you step through the algorithm, you'll be able to clearly see the method for solving the puzzle.

Description of the method:

1) Move 1 into position
2) Move 2 into position
3) Get 4 out of the way
4) Move 3 to the top right
5) Move 4 below the 3
6) Slot in 3 and 4 in consecutive moves

Top row is done. Top row tiles are never touched again.

7) Move 5 into position (never touching the top row)
8) Move 6 into position
9) Move 8 out of the way
10) Move 7 to the top right
11) Move 8 below the 7
12) Slot 7 and 8 in consecutive moves

Top 2 rows are done. Top 2 rows are never touched again.

13) Move 10 out the way
14) Move 9 into position
15) Move 10 next to the 9
16) Slide 9 and 10 in consecutive moves so they are out of the way
17) Move 11 next to 10
18) Move 12 next to 11
19) Move 9,10,11,12 in 4 consecutive moves so that they are in a solid block to the left
20) Rotate the remaining tiles (13,14,15) until the 13 touches the 12
21) Rotate all 8 tiles until they are all in position

And now the puzzle should be solved.

Here are the controls:

'c' runs the algorithm continuously until the puzzle is solved
'p' pauses the continuous run
's' Moves one tile (steps the algorithm until it moves a tile)
'r' Generates a new puzzle
'q' or Esc closes the program

Notes on the implementation:

This program is another demonstration of the value of moving an algorithm into an updatable object that can be queried. By this I mean that instead of implementing your algorithm in a function, you implement it as a state machine, with the various states corresponding to different stages of the algorithm. Local variables of the function become member variables of this object, and any recursive function calls are handled by using a stack. In this way, it is possible to observe the operation of the algorithm, and perhaps do other things in the meantime.

From the caller, its the difference between doing this:


and this:

Algorithm a;

You can see where the second approach would have many advantages.


Picture Logic solver

This program solves picture logic puzzles, and demonstrates the algorithm for a single solving pass on an individual row or column in detail.

PictureLogic.exe generates a random image, and solves it by repeatedly applying the solving passes alternately on all columns and rows.

PictureLogic_RowColAlgorithm.exe demonstrates the algorithm for applying a single solving pass to a row or column.

Controls for both PictureLogic.exe and PictureLogic_RowColAlgorithm.exe are:

'c': Commences or resumes continuous updating of the solving algorithm
'p': Pauses the continuous run.
's': Update the solver one step.
'r': Generate a new puzzle instance.
'q' or Esc: Closes the program.

For the algorithm demonstration program, there is some basic logic guiding the generation of the puzzle instances, but it can still generate unsolvable instances. However, the algorithm will detect these.

Screen layout for PictureLogic.exe:

The only thing displayed is the picture logic puzzle. This consists of the grid and block sizes, as you would see in any puzzle book.

Screen layout For PictureLogic_RowColAlgorithm.exe:

The puzzle instance is displayed in the 1D grid at the bottom: Solid rectangles indicate a cell that must be filled, hollow rectangles indicate a cell that must remain empty. Above this 1D grid are the block sizes.

Just above the puzzle instance is a 1D grid is where the results of the solving pass will appear at the end of the run.

The algorithm will enumerate every possible placement of the blocks in this 1D space during the course of the algorithm, and you can see the results of its work in the middle of the window.

At the top of the window are grids describing the "invariant" cells - the cells that stay the same for all possible placements of the blocks. These are then referred to to generate the result of the solving pass.

I hope these programs are interesting for you, and perhaps teach you about this puzzle and one way of solving it, and perhaps show the benfit of encapsulating an algorithm into an object so that you may query it and control its execution from the outside.


Domino placement game

This is an implementation of the domino placement puzzle. In this version, you are able to explore the puzzle in a new way - the program plays the puzzle with you!

When you place a domino, the AI propagates the constraints of your new placement, allowing you to see the logical effects of your placement. You can very quickly see whether you'd get to a dead end or a solution with a particular placement, and there are unlimited levels of undo.

You can have your puzzle loaded from a file, or watch as the placer generates a new puzzle for you.

Screen layout:
The left grid shows the puzzle.
The right grid is the solving area.
The middle column shows all unplaced dominos.


Clicking once between 2 cells is sufficient to describe a domino placement.

Left mouse in between 2 cells in the right grid will place a domino there.
Right mouse in between 2 cells will reveal all the other places that same domino could be placed.

Mouse wheel when the mouse is over the center column to scroll the available dominos awaiting placement.
Right click on one of these available dominos to see where it could be placed.

Press 'u' to undo your last placement (there are unlimited undo levels).
Press 'l' to load the next level in the level file. (It loads from board_in_dominosa.txt).
Press 'r' to reset the solution board and begin the puzzle again.
Press 'n' to generate a new puzzle.

The puzzles in board_in_dominosa.txt are in the format that dominosa.exe uses when you save a puzzle. Dominosa.exe comes from Simon Tatham's Portable Puzzle Collection, available from http://www.chiark.greenend.org.uk/~sgtatham/puzzles/