# The 15 puzzle – solving the unsolvable 19th century Rubik’s square

oh you're probably all familiar with this puzzle here so we've got a picture distributed on 15 tiles and we've got an empty square and this is empty square can push those tiles around in a box and if you just persistent enough what

You'll be able to do is reconstruct the picture like so this puzzle here is actually what I'm going to talk about today which sounds a bit boring but I mean obviously the title promises a lot more right promising a Rubik's Square

And subtly through is a 19th century and something that's unsolvable but we're going to solve it anyway so okay it's not just clickbait I can justify every single one of those points and so let's just go for it

So 19th century let's just turn this into its 19th century counterpart so made from wood and instead of a picture we've got the tiles numbered from 1 to 15 in natural order yes now put it next to rubik's cube because we're heading

For something rubik's so compare this to the rubik's cube well how do you play this well these days you just shuffle it up give it to somebody and say solve it restore it same thing with the rubik's cube we just shuffle it up give it to

Somebody solve it so very similar other similarities well rubik's cube costs a huge huge puzzle craze in 1980 they were turned into a big huge rubik's cube at the time i was around was amazing now then wasn't the first puzzle craze of

This type funnily enough exactly 100 years earlier in 1880 this guy here caused the first real huge you know mechanical puzzle puzzle craze what was so difficult about this one here well let's have a look at a newspaper from

The time so here center stage is the 15 puzzle it was caught resumed in that was the 3rd of March 1882 have a close look what's shown here is actually a little bit different what I've showed you before at the 1415

Swapped over and it's really this swap here that caused the craze so what you were given is a box with the tiles like this and people ask you solve it legal moves again and people just couldn't do it just couldn't do it as hard as they

Tried they couldn't do it well some people claimed they had done it but they had never been able to produce any you know written up solutions that other people could follow and verify their solutions now people started offering

Prizes so the first prize that was offered was a set of false teeth worth $25 I was done by a dentist dr. Charles purvey from Rochester in Massachusetts later on he even upped the price to Woking added another $100 so you could

Win okay let us go back to rubik's cube and this puzzle now they actually look a little bit different right they look a little bit different so what we're given here is well the puzzle not in its soft configuration all right so that it was

Just given from somewhere and you're supposed to solve it now now Carly oh I've got by my son Carla here again who's going to assist me so Carly you see this one here you see this one here if we want to fix up the cube so that it

Looks pretty much like that one here what would we do so what we have to do is we have to take like two pieces the same kind like those two edge pieces swap them like so and

Now give that to somebody like ow and ask them to solve it and actually a lot of you watching here will know this if you give something like this to a friend they won't be happy because they will not be able to solve it and you might

Also suspect at this point well this one can't probably solve and you're right this puzzle cannot be solved of course you know people at the time that was the first time they they encountered a puzzle like this they didn't didn't

Didn't know this or answer them you know just kept trying so for six months that puzzle craze went on all around the world okay so we've got our Rubik's square I think you know I can recall as a Rubik's

Square right and obviously 19th century is justified unsolvable Bella just claimed it what I really want to do now is actually prove it to you so basically what we did in 1880 run a huge experiment like millions of people

Trying to find a solution nobody could do it now is that a proof not really not really there's gazillions of configurations of this puzzle here and just gazillions of ways of kind of going through this

Configurations to try and find a solution so just because a couple of million people tried this doesn't mean it can't be done all right so what I want to show you now is there's just kind of three very simple kind of

Observations and those observations are going to say once and for all this can't be done so there's something very powerful so that's why I do mathematics because I really interesting this all stuff right okay so let's just go for it

Carly are you ready okay now have a look at this white square okay I'm going to manipulate the pieces in the box and you're just going to watch the white squares and you know see tell me what you see

Okay let's go so push them around what's this the white square door it just kind of goes for a walk and this four times four grid all right it's the first thing to kind of note down second one is it actually makes sense to consider that

Length square here as a as an additional 16 style okay so let's see what happens when we actually make a move here okay so we make a move what happens well basically two tiles swap places not so the empty table and that charges four

Places so a move corresponds to swap a special kind of swap all right so these two things we keep in mind so basically when we're solving or trying to solve a disposal we're doing this with using special swaps of pieces okay now we want

To solve this guy here okay solve this guy here cally so we're starting out with the white square here in that corner right then we want to solve this if there's a solution right if at the end of whatever

We're doing here the 14 and 15 are swapped over where's the white square it's in the same place exactly so if there is a solution that corresponds to kind of a walk-off this white square which starts and ends there all right

Okay now let's just go for walk like this okay let's go for walk like this and let's see I'm going to use these I'm a little friend here my wife's actually dentist so I thought I'd give it a bit of a dentist theme here so you know she

Liked it better this way okay so this is actually one of her toys in our office okay so we chase this thing around now round trip okay so let's just go one two three four one round trip another one one two three four five six seven eight

Another round trip and actually we could kind of go on forever here and do lots and lots of different round trips and we could actually find that all these trips have something in common well the number changes but all the numbers we get

Actually going to be even numbers yeah so if there is a solution here if there is a solution it's going to consist of an even number of moves or even above swaps okay now I'm actually not going to prove this I'm going to assign this as

Homework for you so you know you go and think about this and tell me in the comments you know an argument for why we always get an even number of steps in a in a round trip like this starting here ending there I'll give you a hint okay

I'll give you a hint this is my hint okay go for it and you know see who is the first two to come up with an argument all right now we just need one more ingredient and we're ready to kind of put it all together and and kind of

See at a glance that it's really not possible and that's something pretty deep in mathematics it's hardly anybody knows about it's a sort of incarnation of being in Yang and mathematics so yin and yang comes up as like odd and even

Numbers it comes up as right-handed left-handed but it also comes up in the mathematics of permit Asians of shuffles of messes so let's go for it so what I've done here just taking the

Box tossed out the tiles and put them back in in random order alright ok and now we're going to fix this using swaps but we're not going to restrict ourselves to these special swaps involving the white square any swaps of

Two pieces are ok ok so let's just fix this one it's actually very easy you can fix any any permutation any mess any any shuffle of the pieces if you don't restrict yourself to doing these special swaps so for example the one has to go

There so what I do is swap those two guys alright the to us to go there and obviously I do this 3 4 5 6 7 and so on so then the last swap is just this empty tile and the 15 and we're done and overall it's taking us thirteen swaps to

Do this ok 30s was pretty good now we could try to do this again yeah so same starting position if we tried it again you know kind of really going wild and you know just put somebody in charge who doesn't know anything maybe eventually

They solve you know the puzzle this way and it'll come up as a different number that number will be also odd in fact whatever you try here as as long as you come up with a solution it's always going to involve an odd number of

Switches and so that's that's the yin-yang of permutations any permutation whatsoever again of pieces shuffle up and you solve it with switches here you solve it with switches then depending on the permutation you always take an even

Number of switches to solve it or you always take an odd number of switches to solve it if it's an even number then we called a permutation an even permutation if it's odd we call an odd permutation now I'm not going to prove this either

I've already done this so I mean check it out in that video up in the corner it's actually very nice video if I may say so we'll just use this okay so there's odd an even permutation lets us have

Look at our or real puzzle okay now from before we know that if there is a solution if there's a solution here it's going to take an even number of swaps which means well for one of those things to have any chance of being solvable it

Has to be an even permutation all right an even permutation now let's have a look is this an even permutation well obviously not right because you can just fix it with one swap and one is odd so

That's an odd permutation done case solved now what about a Rubik's Cube alright so here's a Rubik's Cube okay and here is a you know a regular position that can be solved with moves now you could try and

Actually solve this also with you know what with the stage kind of yank out two pieces at a time swap them over and do this over and over again until the whole thing is restored you can do this right and it turns out it will take you an

Even number of swaps I mean I haven't checked this but I know it because every single legal configuration of a Rubik's Cube is an even permutation it will take you an even number of this you know yanking out and swapping operations to

Fix any of them right so basically all legal configurations of a Rubik's Cube are even even permutations and then of course this one's not because you can fix it by just doing one swap which is an odd one okay okay now we still want

To solve it anyway so we've just shown conclusively it can't be done all right and now we're going to show that we can do it anyway actually this this whole thing is not by me or anybody actually

Came up in 1880 during that craze so one thing that happened was that people actually started making these puzzle variations of the puzzles so just to just spice up things a little bit they for example made them from round pieces

Like this and they thought well that doesn't change anything about the puzzle but actually it does so just want to show you how that works so I'm going to use one of those 1818 puzzles and using around pieces here the 14/15 is switched

And we're now going to solve it okay so this thing I can actually be solved the one with squared pieces campus off and was round pieces can be solved why because you get an additional degree of freedom in here in your puzzle you can

Move pieces in a strange way so what we do is you give the box a quarter twist then give all the pieces a twist and then we solve and actually showed us like in front of your eyes we'll just do it so here we go first draw it's done

Second draw is done and third draw is done in the fourth row is done just like that so you can actually solve it this way there's another really nice solution which goes like this so again 14:15 switched so what you can also do is you

Notice that the six and the nine turn into each other when you turn them around so you just turn them and now you can actually solve the puzzle if you if you start like this and what if you've got a box like this try it it's really

Fun well that's basically it right it's basically it now did dr. Pillai have to make his false T's for the person who invented this method I don't think so