Algorithms, OS X Apps & Tower of Hanoi: Solving the "Tower of Hanoi". Part 1 - Intro

 This time we're gonna be going over something quite different and it's called the towers of Hanoi now I've been wondering what's the Tower of Hanoi also called Brahmas Tower or the Tower of Rama sorry or lucas's Tower well simply put the Tower of Hanoi is just a puzzle but I really want to get into the details in this part one but I have to do that on the Mac since there's a demonstration of this puzzle on my Mac so we'll do that in just a minute but first let me explain the Tower of Hanoi is a simple puzzle it and the reason I just said that it's also called Lucas's tower is because it was invented by a French mathematician called Edouard Lucas in 1883 now this puzzle is a bit complicated so what I've done is I've created my own algorithm now again I haven't seen this online yet but if you do find this please notify me in the comments or email me at tanjung mini gmail.com further info will be at the end of the video and mostly the end of the series but anyway continuing now I'm done I've created my own algorithm and so I've implemented this in the new language that so that Apple is created called Swift so now I'm in part one going to be explaining the actual game to you and also again this algorithm uses trees as you know if you've been watching my channel for a while I do like trees quite a bit now rhythms anyway continuing I they're just really nice to code in but anyway apart from that getting back on topic in part what I'm gonna be explaining the game the rules and a simple demo play then in part 2 and once we explain the algorithm in part 3 I'll go more in depth with maybe a little UI for it and in part 4 I'm not exactly sure that's just going to be an extra part for extra information so without further ado let's get to the Mac part of this video so we can actually start with the rules and a sample demo play of this puzzle so welcome back to the Mac part now I'm gonna be teaching you the rules for this game how you can calculate the number of moves and I'm also going to be teaching a little human algorithm that you can use to solve the Tower of Hanoi by yourself again I wouldn't really recommend programming this algorithm in but let we'll get to that right after these okay so again the object or point of the game is to get these three blocks or these three disks they can't least can be as many disks as you want but I'm using three as an example first from Tower one to tower three now the thing is you can only move one disk at a time and the disk that you move must be at the top of a stack also you can place smaller disks on top of bigger disks but you cannot place bigger disks on top of smaller disks so now let's talk about now that we've seen all the rules let's talk about how we would see a little human algorithm implementation of this how would I come up here and bring these three disks from Tower one to tower three well first let me just do it for you so you get a feel for the game then I'll explain the algorithm so I'm going to do this over here it's over here move this back over here to the end move this to the front of this to the end and move this to the end as well and as you can see I have solved it in the minimum number of moves again minimum number of moves is something that I will explain in just a second however look at this I know I've managed to move these three disks from Tower one to tower three now we do the same thing for four as you can see it's progressively getting solved and it's starting to take a bit of shape as you can see now I've deconstructed the whole thing you're like what just happened why did you deconstruct it well this is why because we need this orange block to go up here then it's as simple as this and it's done now you may or may not have noticed a pattern in what I just did now let's go back to three disks and now let me explain the algorithm that I'm using to solve this that's really quick and easy to grasp it first of all what we want to do is we want to see the number of disks that we have in this case it's three and three is an odd number now there's going to be a pattern that I'm going to use right now pattern is 3 2 1 3 2 1 3 2 1 and keeps going on 3 2 1 3 2 1 3 2 1 now the reason we're using this algorithm is because we want to see first of all what move are we currently doing well if we take a move what will this number become over here the moves number in this case will be 1 and 1 is an odd number and on odd turns we're going to use this specific pattern so we want to take the smallest disk and move it in accordance to that pattern the pattern is as we know 3 2 1 that means if it's on 1 move it to 3 if it's on 3 move it to 2 and if it's on - move it to 1 then repeat that and repeat that again and repeat that again until we solve but there's a catch watch this I'll I see that this is an odd turn with odd disks so I'm going to take the smallest disk that we have on the board and move it over here now we're at an even turn so we have to do something else we cannot move the smallest disk anymore we have to give a chance to other disks so now in order to solve this problem we just see what's the only thing we could do right now there are actually three things we could do we could move this back but that's pointless we could move it over here but that's again pointless or we can this disk over here which has reasoning so I'm going to take this disk and put it right on there now get in one move three which is odd so I'm going to take this and our pattern is 3 2 O 3 2 2 so I'm going to take a smaller disk smallest disk sorry and move it from tower 3 to Tower 2 now we're on an even turn 4 so we take the only possible move which is moving this orange disk over here and do it then we say ok odd turn 5 so I see ok smallest disk is over here 3 2 1 1 ok 1 good now it's the only possible move we know it's moving this green disk on top of the orange and then simply we can see I mean we could just move this over here but let's see what our pattern says because it's moved 7 which is odd so move 7 is odd and 3 2 1 that means 1 2 3 ok so I have to move this falseness from tower one to tower 3 and we win in exactly 7 moves now I might be wondering why how did we know that the minimum number of moves will be 7 well it's this simple all we need to do 2 to the power number of disks minus 1 so in this case 2 to the power 3 which is 8 minus 1 7 that's going to be the minimum number of moves it's physically impossible to get lower moves in that now for 2 to the power 4 that's 16 minus 1 that's 15 so we will have at minimum 15 moves now let's try to solve for okay so as you can see it's telling us that we have 15 minimum moves and now this is even so the pattern won't work here we have to use instead a different pattern which will be two three one not three two one two three one instead so if it's on one and move it to two if it's on - move it to three and if it's on three move it back over to one let's get started so by it I'm talking about the smallest disk so as you can see we are on an odd turn so we take the smallest disk we go to our pattern and our pattern says three two one I mean sorry two three one so we move it from Tower one it's a tower - let me see it with the only possible movement and that's to move this green block over here then our pattern again is 2 3 so 2 2 3 this is the only possible move 2 3 1 so I move the smallest disk over to 1 then this is the only possible move to 3 1 that means from 1 over back to 2 then this is the only possible move to 3 1 again so 2 to 3 this is the only possible move then from 3 over to one of course then this is the only possible move oh then 1 to 2 as we know due to our pattern then this is the only possible move and then finally 2 to 3 so technically we win in exactly 15 moves so as you can see this algorithm is amazing it helped us solve 3 & 4 disks in exactly 15 moves now that would actually be it for this video but just to show you that it really does work I'm going to do this with one last set of disks five disks so now as you can see the minimum moves will be 31 because 2 to the power 5 is 32 minus 1 31 okay so now we know this is odd so we have to follow 3 2 1 so let's move ours I'm not going to talk through this because you should know the pattern by now I'm just going to do it in my head and let's see if you can follow along so small is just 2 3 possible move only possible move from 3 to 2 only possible move from 2 to 1 only possible move from sorry ok so up from 1 2 3 yes then this is the only possible move then 3 2 2 and then this is the only possible move then again 2 to 1 and then this would be the only possible move then 1 2 3 this would be only possible move and then 3 to 2 and now as you can see move for disks over to tower 2 and then we still have this one disk left over in Tower one that we can move over here now we just need to move these three disks oh I mean 4 disks over here and then we would have been done so now let's do this now from tower to over the tower 1 because we're on an odd turn then this is the only possible move from tower one to tower 3 then this is the only possible move from tower 3 to tower 2 then this is the only possible move from tower to tower 1 this is the only possible move from tower one to tower 3 then this from Tower 3 to Tower 2 then this from tower to tower 1 and this and then from tower one to tower 3 and we have solved five disks completing this part of this series I hope you enjoyed if you did please leave a like and as you can see we've solved it in exactly 31 moves we made a perfect game hope you enjoyed if you have any questions suggestions concerns leave it in the comments you can even email me at sad you manage email comm if you want to if you have any more questions or you can also tweet me at Taji Manny on Twitter and you can also subscribe to my channel if you like my cotton you want to see more of it right here just plainly to the channel and want to receive notifications of whenever I upload a new video I will be very soon actually releasing part two and three of these of the series and that's going to be it goodbye