The Unsolvable Configuration of the 15
Puzzle and an Interesting Approach to
Abstract Algebra
By Kareem Jaber
Math, to a lot of people, is all about numbers. We’ve spent all of our time in school learning how
numbers work, how to add them and subtract them, how to multiply and divide them. We’ve
learned how they interact with each other in equations, seen how they can transform each otherwith functions, and a lot, lot more. After all, numbers are the language of math, right?
But what if they aren’t? What if we threw away our preconception of what numbers are andwhat we can do with them, and instead look at something more fundamental? The field of
abstract algebra is exactly this: we look at the structure of how systems interact. This way of
thinking gives us access to solving lots of interesting problems that "normal math" can't solve,
and today, we're going to be using some abstract algebra to play with a fun little toy: the 15
puzzle.
This isn’t so much a paper about abstract algebra, it’s more of an opportunity forme to share a playful math experience with you. You shouldn’t try to read thislike a book, but instead use this as a chance to work through a problem, tostruggle a little bit, but to enjoy the struggle, and to appreciate the art ofcuriosity, motivation, and problem solving.
Alrighty, the 15 puzzle is the puzzle to the right with, unsurprisingly, 15 sliding
pieces labeled 1-15. When the puzzle is mixed up, the goal is to push the pieces
around to try to reorder the pieces. If you have one at home, go pull it out, but if
not, try out this online version at https://tinyurl.com/fifteenpuzzleonline (credit
to Simon Fraser University). Mix it up, try to solve it, and get an idea of how
pieces move. Break it down into steps.
This is how I go about solving the 15 puzzle:
Step 1: Get piece 1 in position, then piece 2. Pieces 3 and 4 have to go insimultaneously because of the way pieces move, so place the two pieces next toeach other and use a “snake-like pattern” to put them where they need to go(check out the picture to the right). After this row is complete, don’t touch it
again.
Step 2: Follow the same procedure to get pieces 5 through 8 into their positions. After this row
is complete, don’t touch it again.
Step 3: Get pieces 9 and 13 in position, then don’t touch them. Get pieces 10 and 14 in position,and then the 11, 12, and 15 pieces should be easy to solve.

Solve the puzzle a few times. Try to see how fast you can do it. My record is a bit under 20
seconds!
Here’s my real challenge. Let’s say that I took your puzzle (that you just solved) but shuffled it alittle differently than normal: I broke your puzzle, took out the 14 and 15 pieces, swapped them,and put them back. Now your goal is to solve it.
[Note: if you’re using the online version, you can’t physically switch the 14 and 15 pieces.
Instead, try going from the solved state to the configuration where the 14 and 15 are switched.]

I’ll wait. Go try it.
…
If you’re having some difficulties, try for a little longer.
…
Hmm. I’m going to take a guess and say that you didn’t solve it yet. You should feel a little bit
suspicious about this situation. Something seems off.
…
You still haven’t solved it? “Maybe it’s impossible!” you might say. Who knows? Maybe it ispossible, or maybe it isn’t, but you’ve just made a big step in the problem solving process:you’ve made a claim. You’re arguing that the challenge I just gave you, solving thisconfiguration with the 14 and 15 pieces swapped, is impossible. Now our goal is to prove thisclaim. But where are we going to start? Will the solution just magically pop into our heads? In
problem solving, proving a claim requires motivation. We need to find a foothold to push offof, something tangibly different that we can notice behind the structure of the solved
configuration and the 15-14 (shuffled) configuration. Take some time to play around with the
15-14 configuration and focus on what feels fishy about the situation at hand.
…
How about this, let’s try to take a look at a configuration similar to this: swap the
13 and 14 pieces, and then swap the 14 and 15 pieces, like this. Can you solve
this configuration? If so, why?
…

Keep trying this out. Try seeing if you can solve some other shuffled combinations, like these:
Left: swap 12 with 15
Middle: swap 9 with 10, and11 with 12
Right: change 9-12 row to
12, 9, 10, 11

Which ones are solvable? What about their structure makes them different than the ones that
can’t be solved? Do certain shufflings “collapse” into others? Keep exploring and making
observations.
…
The structure of the 15 puzzle seems to be intrinsically built upon “moves,” the action ofswapping the empty space with a piece next to it. Can we extend this concept to our weird
shufflings of the puzzle by allowing illegal moves, switches that swap any two pieces, not justthe empty space and an adjacent piece? What we are doing here is another powerful tool inmathematics: we are generalizing a concept to describe the things we see around us. Let’s create
a new concept that allows us to extend the idea of a move and describe the nature of ourshufflings:-

Let’s call a move any action that is allowed in the normal 15 puzzle game: changing thepositions of the empty space and a piece next to it.
Let’s call a switch any action that swaps any two pieces or swaps any piece with theempty space. Notice how all switches are moves, but not all moves are switches, kind oflike how all squares are rectangles, but not all rectangles are squares. Switches are ourgeneralized concept of moves.

Here are some examples for us to get an idea of the terms we defined:
This is a move and a switch.

These are switches, but not moves.

We can describe the 15-14 configuration by starting with the solved configuration and one
switch between the 14 and 15 pieces. For some reason, we can’t seem to find a sequence ofmoves to bring the 15-14 configuration to the solved configuration. Why? What is intrinsicallydifferent about a move and a switch in terms of their structure? What always changes when you
make a move? How about with a switch? What sometimes changes? What stays the same?
Again, take some time to think about this before moving on.
One thing moves always change is the position of the empty space. Every time you make a
move, you are swapping the empty space with a piece next to it. Switches, however, don’t
always have to move the empty space, and don’t always have to move a piece with one next to it.
The structure of moves seems very restricted, while the structure of switches seems very loose.
Let’s focus on the empty space because it seems very
fundamental to the structure of moves. The position of
the empty space doesn’t move between the solved
configuration and the 15-14 configuration. If we assume
we can get from one configuration to the other by only
using moves, how many moves would we need? How
many moves do we need to bring the empty space back towhere it was in the beginning?
…
Every time we swap the empty space with the piece above it, we’re eventually going to have toswap the empty space with the piece below it to “cancel out” the move up. And every time weswap the empty space with the piece to the left of it, we need to swap it with the piece to theright of it to “cancel out” the move left. This means that moves come in pairs, that we must
make an even number of moves to bring the empty space back to where it was before. Thismeans that hypothetically, if we could go from the solved configuration to the 15-14
configuration, it would take an even number of moves.
The same is not true for switches. We can make one switch, an odd number of switches, to getfrom the solved configuration to the 15-14 configuration, just like this:We’ve finally found a foothold, a hint of motivation: parity (the math-y word for oddness andevenness) is fundamentally different for moves and switches. While it takes an even number ofmoves to leave the empty space untouched, switches do not have this restriction.
Look at some of the other “shufflings” that we took a look at earlier. Keep track of how many
switches it takes to shuffle them, and whether or not the empty space was moved in the process.

Think about the parity of the number of moves it would (hypothetically) take to bring the
shuffled configuration to the solved configuration.
We’ve made a lot of observations. We’ve explored the structure of the 15 puzzle and foundsome motivation to start attacking our problem. Let’s do a quick recap:-

We think that the 15-14 configuration is unsolvable using only moves
We think that it has something to do with the structure of moves and switches
We found some interesting differences in parity between moves and switches

With our newfound motivation, we’ll try to reword our original question using our new terms
and come up with a more general statement to prove. If you analyzed the other shufflings fromearlier, you might have noticed that the shufflings with an odd number of switches seem
unsolvable for the same reason as the 15-14 shuffling: we need an even number of moves to keep
the empty space in the same place.
With this, let’s make a leap of faith that might seem out of nowhere. We’re going to claim:
If you can go from the solved state to a configuration in the 15 puzzle with an odd numberof switches, then you can’t get to the same configuration from the solved state with an evennumber of switches.
We don’t know if this is true, but we definitely have some reasonable suspicion to believe that it
is. Whenever we have a shuffling requiring an odd number of switches and leaving the empty
space where it is, we can’t seem to find an even number of switches to bring the puzzle back tothe solved state.
Also, make sure you see that proving this claim also proves that the 15-14 configuration is
unsolvable. Shuffling the puzzle to the 15-14 configuration requires an odd number of switches,
while solving the configuration using only moves requires an even number of switches(remember, all moves are switches). Again, reread this until you are comfortable with ourstatement and understand where this seemingly random leap of faith comes from.
This claim is a big one, and something that doesn’t look easy to prove. So just like earlier, let’s
explore a bit and simplify the problem down to its core. As we do that, try to look ahead andbuild a game plan on how our proof will go.
Think back to our earlier findings. We are still working with the structure of the 15 puzzle justlike we were doing earlier, so we don’t want to forget what was important to us. One of thethings that stood out the most was the concept of parity and keeping the empty space in the sameplace. Let’s dig deeper into the root of this problem by looking at the parity of the action that
does nothing. If we start in the solved configuration, perform a bunch of switches, and end up
back at the solved configuration, how many switches did we make? Was it an odd or evennumber of switches?
Play with this for a while. Try to get a feel for this concept and find some patterns.

Clearly, we can perform the action of doing nothing, which we’ll call the identity action, withzero switches. We can also do the identity action with two switches (by repeating the same
switch twice), four switches (by repeating the same switch four times), six switches, and any
even number of switches. We can never do the identity action with one switch, since the twopieces we switched would not be in their original places, and it would be reasonable to guess that
we can never perform the identity action with an odd number of switches. But before we go
through the trouble of showing this, let’s think about what would happen if this statement wastrue.
Take a few minutes to think through how we could use this fact, that the identity action can only
be done with an even number of switches, to progress through this problem. How can weconnect the identity action back to the 15-14 configuration?
When playing with the identity action earlier, you might have realized that finding a series ofmoves that do the same thing as “doing nothing” feels a lot like shuffling the puzzle and thensolving it. Assuming that the identity action can only be done in an even number of swaps (thething that we skipped proving for now), let’s try applying this idea to the 15-14 configuration.
We know we can get to the 15-14 configuration from the solved configuration in one swap (anodd number of swaps): just swap the 14 and 15 pieces. Now, we know that if it is possible tosolve the 15-14 configuration using only moves, it would require an even number of moves, or
equivalently, an even number of switches (because all switches are moves).
It took an odd number of switches to shuffle the puzzle to the 15-14 configuration, and an evennumber of switches to solve the puzzle. Since an odd number plus an even number is still an odd
number, this means that we just did the identity action with an odd number of switches. This
is HUGE. Take a second to let that sink in and realize the power of that statement.
We contradicted ourselves! We assumed that the identity action could only be done with an evennumber of switches, and then showed that if the 15-14 configuration can be solved using only
moves, the identity action could be done with an odd number of switches. This means one of
two things:
The identity action can be written as an odd number of switchesOR
The 15-14 configuration can’t be solved by only using moves
So, if we can actually prove that the identity action cannot be written as an odd number ofswitches, then the 15-14 configuration has to be unsolvable! I think that this is a beautiful lineof logic, so take a second to appreciate what we did together.
Homestretch! Let’s show that the identity action can only be written as an even number ofswitches, and never as an odd number of switches. This is a really neat argument, so check thisout:
Let’s say I started with a solved puzzle, closed my eyes, made a bunch of switches, opened myeyes, and saw that the puzzle was still solved. I don’t know how many switches I made, or if it’san odd or even number of switches, and neither do you, so let’s just give it a letter placeholder:
N. I made N switches and the solved puzzle remained solved. I argue that I could have done thisin N-2 switches.
To show this, let’s keep track of a piece. I’ll keep track of the “1” piece, but it doesn’t reallymatter what piece we keep track of. Somewhere in our N switches, we’ll switch the “1” piece
for the very last time, let’s say with the “2” piece (but again, it could be any piece). What could
have been the switch that happened right before switching 1 with 2? There are four possibilities:-

CASE 1: I could have switched 1 with 2 again
CASE 2: I could have switched 1 with any other number but 2, which we’ll just say is the“3” piece
CASE 3: I could have switched 2 with any other number but 1, which we’ll just say is the“3” piece
CASE 4: I could have switched any other two numbers, which we’ll just say are the “3”and “4” pieces

CASE 1: If we switch 1 with 2, and then immediately switch 1 with 2 again, the switches“cancel” each other out, so we could get rid of these two switches and be left with N-2 switches.
CASE 2: If we switch 1 with 3, and then switch 1 with 2, we could do this instead: we could
switch 1 with 2, and then switch 3 with 2. This means we touch the “1” piece for the last time
one switch earlier. We’ll come back to this in a second.

CASE 3: If we switch 2 with 3, and then switch 1 with 2, we could do this instead: we could
switch 1 with 3, and then switch 2 with 3. Again, this means we touch the “1” piece for the lasttime one switch earlier.

CASE 4: If we switch 3 with 4, and then switch 1 with 2, we could just do them in reverse order:
switch 1 with 2 and then switch 3 with 4. We touch the “1” piece for the last time one switch
earlier.
For CASE 2, CASE 3, and CASE 4, let’s run this casework again, but this time, the “1” piece istouched for the last time one switch earlier. Again, either:
CASE 1: the last switch where we touch the “1” piece and the switch before that are the same,so they cancel each other out, getting rid of two switches and letting us do the identity action in
N-2switches
CASE 2-4: the last switch where we touch the “1” piece and the switch before are not the same,
and we run our argument again and touch the “1” piece one switch earlier.
We can keep doing this over and over and over again, until we end up at CASE 1. But what if
we never get to CASE 1? This means that we keep moving the last time we touch the “1” piece
until the last and only time we touch it is the first switch in the sequence. If we only touch the“1” piece one time and never make another switch to put it back where it originally was, thiscan’t equal the identity action, so this can never happen!
We just showed that if the identity action can be done in N switches, it can also be done in N-2
switches. This means that the identity action can NEVER be done with an ODD number ofswitches, because we could keep decreasing the number of switches by two until we are left with
one switch equaling the identity permutation (which is impossible)! So by our contradiction
argument earlier, the 15-14 configuration can’t be solved in an even number of switches, so it
can’t be solved by only using moves! BOOM!
That was A LOT. The best learning in math doesn’t just come from solving a problem, but
walking back through it, retracing your flow of logic, and enjoying the beauty of the path you
took to get to your solution. Try to think through it yourself, and when you’re ready, let’s walkthrough it together:-

We played with the 15 puzzle and got an idea of how to solve it using normal moves-

We started questioning whether the 15-14 configuration and other similar configurations
could be solved, and developed a claim
Our exploration motivated us to define the concept of moves and switches, and explore
their structures until we uncovered their differences in parity
We took an educated leap of faith to generalize our question into a form we could workwith
We simplified the problem by focusing on the identity action and showing that it could
only be represented by an even number of switches
By cleverly contradicting ourselves, we showed that it is impossible for the 15-14
configuration to be solved in an even number of switches
We realized that since all switches are moves, if we can’t solve a configuration in an evennumber of switches, we can’t solve the configuration in an even number of moves.

Notice that the way our “formal” solution flows doesn’t follow the flow of our thought process!
The journey of discovery is one of the most amazing things in math, and this quote very nicely
summarizes how I feel about this:“Perhaps I can best describe my experience of doing mathematics in terms of a journey
through a dark unexplored mansion. You enter the first room of the mansion and it’scompletely dark. You stumble around bumping into the furniture, but gradually you learn
where each piece of furniture is. Finally, after six months or so, you find the light switch,
you turn it on, and suddenly it’s all illuminated. You can see exactly where you were.
Then you move into the next room and spend another six months in the dark. So each ofthese breakthroughs, while sometimes they’re momentary, sometimes over a period of aday or two, they are the culmination of—and couldn’t exist without—the many months ofstumbling around in the dark that proceed them.” - Andrew Wiles
A lot of this problem was abstract algebra in disguise. Through the lens of the 15 puzzle, we
explored the concept of symmetry groups, systems that allow us to perform actions thatrearrange objects. The 15 puzzle can be seen as a list of 16 objects (with the empty space being
viewed as “piece 16”). The “switches” that we explored are known as “transpositions” inabstract algebra terminology, and our “shufflings” are known as “permutations.” So I could havejust opened this paper with:“Theorem: Any permutation can either be represented by an odd number or an even number oftranspositions.
Proof: Consider a string of N transpositions equivalent to the identity permutation…”
But then we miss the fun to be had exploring problems, developing conjectures, jumbling up
your thoughts, and feeling the thrill of putting all the pieces together (quite literally).
I hope you enjoyed our journey. Keep playing with the 15 puzzle, there’s a lot more questions tobe asked and interesting properties to be discovered. What other configurations can’t be solved?
How many can’t be solved, and how many can? How would this puzzle change if there were 24

pieces on a 5x5 grid, or 99 pieces on a 10x10 grid? What if I took my puzzle and bent it into acylinder, like this, so that the “1” piece was able to switch with the empty space?

Credit: Henry Segerman, Oklahoma State University

Happy puzzling and see you next time!
Applicant W8