A Puzzling Diversion
I recently found myself playing with a plastic sliding puzzle, of the kind that children often get as a gift from a party bag. It had an image on it, and 15 pieces that could be slid around to rearrange them into the correct picture. Such puzzles are not just a momentary diversion for small people – adults, and in particular mathematicians, have found this type of object fascinating, and it’s linked to some interesting mathematical ideas.
The general idea of such puzzles is that there’s a square or rectangular region you can move square pieces around in, and it contains one fewer piece than can fit in that space. This means there’s always a gap somewhere in the puzzle, and your options for a move each turn are to move one of the pieces next to that gap, into the gap.
Depending on where the gap is, this means there are either two, three or four options for which move to make on any given turn. Given a square puzzle with 16 spaces and 15 pieces, this gives a reasonable amount of challenge – puzzles with 9 spaces and 8 pieces also exist, and can be completed more easily, but the 15 piece version is a good level of difficulty.
The most mathematical version of this puzzle is of course to dispense with the idea of completing a picture – mathematicians don’t have time for art – and to instead number the pieces from 1 up to 15. The challenge is then to rearrange the pieces so they run in order from 1 in the top left to 15 in space next to the bottom right, with the gap ending up in the bottom right corner.
If you’d like to try this puzzle, and you don’t happen to have been to any children’s birthday parties recently, a version of it can be created using pieces of paper you move around on the table, making sure you only ever make valid legal moves; I’d recommend starting with a solved version and making moves to jumble it up, then going for a cup of tea and seeing if you can repair it when you come back. Alternatively, there’s an online version which will set puzzles for you.
This particular version of the puzzle, often called ‘The 15 Puzzle’, was invented in the 1870s, and became somewhat of a craze in America in the early 1880s, with versions of the puzzle being widely manufactured and sold as a curiosity.
How hard is your puzzle?
As soon as mathematicians get their hands on this kind of puzzle, which can easily be abstracted to a mathematical structure, it opens up all kinds of interesting insights into how such things work. The 15 Puzzle is a nice example of a problem which can be tackled with heuristics – an area of maths and computer science concerned with finding efficient solutions to problems.
Commonly, heuristics involves finding a way to determine how difficult a particular problem is – to give sense of how many moves away from solved you are in a given state of the puzzle, and hence how ‘difficult’ that state is. A simple heuristic for the 15 Puzzle might be to count the number of tiles currently out of place – which is 0 for a solved puzzle, and gets larger the more pieces are out of place. This is easy to compute, but might not give you as much information as you’d like – it would be better to have some notion of how far we need to move the pieces as well.
We could use the conventional metric, or way of measuring distance: a ruler. Also known as the Euclidean metric, this involves measuring the straight-line distance between each square and the place it’s supposed to be in the puzzle. This isn’t quite what we need though, since in this puzzle moves must happen in straight lines, as the squares always stay on the grid.
Luckily, we have a metric for that too! Called the Taxicab metric, this measures the distance between two squares on a grid, essentially by counting the number of squares across and down to travel between the two squares (like a taxicab driving in a city with a grid system – there’s no diagonals to cut across). This will give the same value for any pair of squares, no matter which route you choose (assuming you don’t go out of the way).
For a more detailed heuristic for how difficult a particular starting state for the 15 Puzzle is, measure the Taxicab distance (across and down) from each tile to its correct position, and add them all together. This heuristic is known as an admissible heuristic – that is, it will give you a minimum number of moves needed, and any efficient solution will need at least that many moves.
The more moves you need to do, the harder the problem. Now you can judge how difficult different configurations are, and feel an appropriate amount of pleased with yourself when you solve them!
15…with a twist!
When the 15-puzzle craze was at its height, recreational mathematician Sam Loyd issued a challenge, with an associated $1,000 prize, to anyone who could find a solution to the puzzle from a particular starting state – with all the pieces in their finishing places, except that the 14 and 15 have been swapped. Called the ‘14-15 Puzzle’, this was a popular diversion, and caused quite some consternation among puzzlers.
The reason people found this so frustrating was that while switching two pieces seems like a simple change, it makes a big difference to how difficult the puzzle is to solve. I’ve written previously here about permutations – ways of reordering a set of objects, and assuming you consider the empty space to be a sixteenth object in this puzzle, you can think of all positions in the puzzle as being a permutation of those sixteen things (15 pieces and a space).
The crucial thing in this puzzle is that any move you make swaps two pieces (the piece you’re sliding into the space swaps with the space), and represents what we call a transposition: a permutation that just swaps two of the objects.
It’s known that any permutation can be made up from a combination of transpositions, which means in theory any position you start from should be possible to solve, if you chain the right transpositions together in the right order.
However, permutations divide themselves into two types – called odd and even. If a permutation is odd, it can be written as a combination of transpositions, possibly in multiple different ways – but any way you do this will involve an odd number of transpositions. Similarly, even permutations can only ever be written as a product of an even number of transpositions.
Since the solved version of the puzzle is zero transpositions away from solved – an even number – this means only even permutations of the pieces will actually be solvable. The 14-15 puzzle, exactly one swap away from solved, is clearly an odd permutation, and therefore impossible. Sam Loyd’s $1,000 was safe – although anyone who was keeping up with the latest mathematical literature would have known not to even try, as the impossibility of such a puzzle was proved and published in 1879 by Johnson & Storey, over a decade earlier.
Since I started writing this post, a Numberphile video has covered the topic, which looks at some of the impossible combinations; there’s also a video by James Grime from 2009 in which he offered $1,000 to anyone who can solve the 14-15 Puzzle, but then posted a follow-up explaining why it can’t be done – and giving some solvable starting positions you can have a go at.
Solvable and unsolvable
The division of permutations into odd and even splits the universe of this puzzle in half – solvable starting states, and unsolvable ones. This kind of idea can be applied to other common puzzles as well – for example, the Rubik’s cube famously has over 43 trillion possible positions – but that’s only the solvable ones.
Any state you can reach by taking a solved cube and scrambling it should be solvable (eventually), but if you’re one of those people who cheats by taking the stickers off the cube, beware! Sticking the stickers back on in different places could potentially produce a state which can’t be reached from a solved cube – and the number of possible states reachable by moving around the stickers is significantly larger than 43 trillion, so your chances of guessing right, if moving the stickers around randomly, are tiny.
The easiest, and most fixable way to mess up someone’s Rubik’s cube is if it’s a specialist speed-cuber’s cube, and has flexible joints so the pieces can move around easily. Such cubes are often loosely connected enough that you can rotate one of the corner pieces, without even disconnecting it from the cube. To be clear, I’m not advocating this (if you’re in lockdown and at close quarters with a speed-cuber who holds grudges, it’s definitely not recommended) – merely stating the mathematical possibility.
Turning the corner piece three times puts it back as it was, but moving it once or twice will put the cube in an unsolvable state! This is from a smaller set of unsolvable states than you can get to by moving stickers, and can easily be fixed by rotating the corner piece back again – but not before providing some amusement (and frustration).