|What is the 15 Puzzle?
||The fifteen puzzle has 15 pieces, which are numbered from 1 to 15 and
which lay in a square frame.
You cannot take away the pieces; you slide them by using a free square.
At the beginning the 15 numbers are mixed (left). You must order the numbers
by sliding (right).
Solution of the Puzzle top
||You don't need special advice to find a solution. Everybody, who has
some patience, can arrange the pieces in the right order.
To get to know the puzzle and to practice, it is best to build a model.
You can move the numbers easily. The pieces don't get stuck while moving.
You draw a 4x4 square freehand on a piece of cardboard, cut out 15 suitable
cards from paper, label them and lay them on the squares (left).
||The usual method is moving the numbers from 1 to 15 one after the other,
line after line.
You must not destroy a line. You must keep the order of the numbers
Then the next numbers follow...
||You start with moving 1 to the left-hand corner above.
Therefore you must make a gap in front of the 1, so that 1 can go forward.
You quickly notice, that it is good to take other numbers with you, too.
||This is a main move, the circle: A number is going around in a 2x2
Here you can see, how 7 is going to its right place.
If 7 is going around the other way, 8 is also on the right place.
||Sometimes you don't have a 2x2 square for moving a piece (1).
You can see with 8 how to move the incomplete line to the left and down
and then 8 up in a 2x2 square (2,3,4).
||If you have solved the third line, sometimes the fourth line is also
solved and you are finished.
Otherwise the numbers of the last line aren't in the right order (1).
It is helpful to compress the third line into a 2x2 square (2). Then
it is easy to order the last three numbers 13,14 15.
||The solution is more systematical, if you know how to move the pieces
inside a 2x3 rectangle.
You always can succeed in moving any two numbers (here a and b) to the
left, also changed (book 09).
There are many programs of the 15 puzzle on the net, especially one made
by Karl Hörnell. You can play them online or offline.
||If you have solved the puzzle, your next problem can be to order it
with as few moves as possible.
I have written a small program in Visual Basic V3, which simulates
and counts the moves.
The pieces are already mixed from the start.
You can download the program. You need
You can also download programs to find out as few moves as possible.
I used Ken'ichiro Takahashi 's program (thanks, URL below) to solve the
pattern on this website. You need at least 59 moves: 9, 1, 6, 9, 1, 14,
12, 1, 2, 15, 11, 5, 1, 2, 15, 7, 9, 4, 10, 3, 13, 9, 3, 10, 8, 6, 14,
15, 4, 3, 7, 11, 5, 1, 2, 4, 3, 8, 6, 14, 15, 12, 4, 3, 8, 6, 14, 15, 12,
8, 6, 7, 11, 6, 7, 11, 10, 14, 15.
The problem of counting the moves of a solution with as few moves as
possible is difficult (12). You can only guess the lower bound of
moves. Today it is known that you can solve the 15 puzzle with at least
80 moves (12). Thus computers can manage the huge number od cases. If they
look for a solution, they can stop after 80 moves, because solutions with
more moves are not interesting. This speeds up the programs.
Some Mathematics top
Look at a 2x2 square for the sake of simplicity.
Only three pieces are used. The free square is always at the bottom
||There are three possibilities under these circumstances to alter the
position of a piece by sliding. You can write them as 123, 312 and 231.
How do the permutations differ?
||You can make 3! = 6 changings (permutations) with three numbers. There
are still the possibilities 132, 213 and 321. They bring you to the positions
of the pieces on the left, which don't appear in the puzzle.
You form all the pairs within the permutations, where the bigger number
is in front of the smaller one (inversions).
12 13 23
31 32 12
23 21 31
2 pairs: 31 32
2 pairs: 21 31
These permutations are called even, because the number of pairs is even.
(The even permutations make the alternate subgroup with the order 3
of the symmetric group. The basic set must have an order.)
The other permutations are odd:
13 12 32
21 23 13
32 31 21
1 pair: 32
1 pair: 21
3 pairs: 32 31 21
You can transfer these facts to the 4x4 square.
There are 15 pieces, so you have 15! = 1 307 674 368 000 permutations.
Only half of them are even and will appear as positions.
If you also count the empty square, you have 16! = 20 922 789 888 000
Sliding Block Puzzles
I thought that this was intented for making the puzzle insoluble. Now in
August 2004 Martin Beckenkamp sent me an email that a 15puzzle is installed
at his handy [England: mobile (phone), USA: cell (phone) ;-)] and shows
"solved", if the numbers have this order
01 02 03 __
||I found an insoluble 15puzzle in Italy, where the numbers 14 und 15
This puzzle is insoluble. The permutation (1,2,...,13,15,14) is odd
because of the pair (15,14). You can't change it by sliding to the even
04 05 06 07
08 09 10 11
12 13 14 15
You can reach this order with the Italian puzzle above, where 14 and 15
Most 15 puzzles, which you can buy nowadays,
have picture pieces instead of numbers. You must find the completed picture.
Two examples follow: Ads of Mc Donald's and Kaiser Bier.
Hint: You can take off the tiles with some
power. You must slightly lift the middle pieces at the beginning.
The Eight Puzzle top
Henry Ernest Dudeney invented this problem. He needed
36 moves. Martin Gardner asked readers of the American magazine "Scientific
American" for solving the puzzle in less steps. He got many solutions.
Order the numbers going backwards to the normal
order 1 to 8 with a free place on the bottom right.
||Result: You only need 30 moves. - There are 10 solutions. Two solutions
(on the left and in the centre) form a pair and are reverse. You recognize
this, if the moves run backwards (on the right).
||The corresponding 15 puzzle is insoluble.
But if 1 and 2 change their places, it is soluble. You need at least
70 moves (Ken'ichiro Takahashi): 2, 5, 9, 13, 14, 10, 11, 7, 3, 1, 6, 11,
10, 15, 7 ,3, 1, 6, 5, 9, 13, 14, 15, 7, 3, 1, 6, 5, 9, 13, 14, 15, 12,
8, 4, 14, 15, 12, 8, 4, 12, 8, 7, 3, 1, 6, 5, 9, 13, 15, 14, 2, 15, 14,
2, 12, 8, 2, 11, 10, 2, 7, 3, 2, 6, 5, 9, 13, 14, 15.
Block Puzzles with Different Tiles top
This sliding block puzzle is called Dad's Puzzle.
||Many puzzles followed the 15 puzzle in the19th
century. You also had to move pieces, but pieces with different sizes.
You must transport the left top corner square
to the left bottom corner.
You need at least 59 moves (solution in book 07).
Tower of Babylon (German:
The "Tower of Babylon" is one of the many puzzles that followed Rubik's
cube. In principle it is a sliding puzzle.
You must order 36 balls, so that there are 6 balls
with the same colour in a column and ordered by shades. You can easily
move them horizontally. They are fastened in a ring. Moving vertically
is only possible with a trick: You can push a ball at the bottom to the
middle (left arrow), so it disappears. Then the balls move down and form
a gap at the top (right arrow). If you hold the tower horizontally, you
can move the gap to another place. This is enough to solve the puzzle.
This is a stupid work because of the many balls.
My tower has a screw at the top, so that I can
easily put the tower into pieces and arrange the balls properly ;-). It's
a pity I have lost the ball-bearing between the slices :-(.
The 15 Puzzle on the
Alexander Bogomolny (cut-the-knot)
Loyd's Fifteen, History,
Ed Pegg Jr. (MAA online)
14-15 puzzle /
The 15 Puzzle (The
possible puzzle; The impossible puzzle)
Karl Hörnell's Applet Center
The 15 Puzzle
Ken'ichiro Takahashi (takaken)
(00) ermann Schubert: Mathematische Mußestunden, Walter de Gruyter
Verlag Berlin 1941 (1.Auflage 1897)
(01) W.Ahrens: Mathematische Unterhaltungen und Spiele, Leipzig 1918
(02) G.Kowalewski: Mathematica delectans, Band 1 , Leipzig 1921
(03) G.Kowalewski: Alte und neue Spiele, Leipzig 1930 (Nachdruck: Martin
Sändig, Walluf 1978 (ISBN 3-500-19830-9)
(04) Martin Gardner: Mathematical Puzzles & Diversions, New York
(05) Walter Lietzmann: Lustiges und Merkwürdiges von Zahlen und
Formen, Göttingen 1961
(06) Bruno Kerst: Mathematische Spiele, Berlin 1933 (Nachdruck: Martin
Sändig, Wiesbaden 1968)
(07) Martin Gardner: Mathematisches Labyrinth, Braunschweig 1979 (ISBN
(08) Michael Mrowka: Zauberturm, Teufelstonne und Magische Pyramide,
Niedernhausen/Ts.1981 (ISBN 3-8068-0606-3)
(09) Monika Dewess und Günter Dewess: Summa Summarum, Thun; Frankfurt
am Main, 1986 (ISBN 3-87144-898-2)
(10) Johannes Lehmann (Hrsg.): Rechnen und Raten , Köln 1986 (ISBN
(11) L. Edward Hordern: Sliding Piece Puzzles, 249pp, hb, Oxford, England,
1993, Oxford University Press
(12) F. R. W. Karlemo and P. R. J. Östergård : On sliding
block puzzles, Journal of Combinatorial Mathematics and Combinatorial Computing
34 (2000), 97-107
(13) Jerry Slocum & Dic Sonneveld: The 15 Puzzle, Slocum Puzzle
Foundation, 257 South Palm Drive, Beverly Hills, CA 90212, 2006
Thank you Gail from Oregon Coast for supporting me in my translation.
Feedback: Email address on my main page
page is also available in German.
2000 Jürgen Köller