![hanoi towers problem hanoi towers problem](https://www.tutorialcup.com/wp-content/uploads/2020/07/untitled-2-e1593781411787-1024x453.png)
![hanoi towers problem hanoi towers problem](https://old-blog.patrickwu.uk/img/Tower-of-hanoi/tower-02-1.jpg)
Note that the same pattern obtains: at move 8, the (largest, bottom) disk 4 can jump from peg A to peg C because disks 1-3 are all on peg B. Moving on to a stack of n = 4, some practice should get you to a minimum number of 15 steps. The next three moves simply stack the remaining disks on peg C, using A as a temporary peg. What’s more, we only have to move it once! Also, the remaining disks are all on peg B. This is the first disk that is permanently in the right spot. The first thing to notice about the 7-step solution is that, at step 4, we move disk 3 from peg A to peg C. So we can better keep track, let’s also number the disks, starting with 1 for the smallest, top disk, and ending at n for the largest, bottom disk (the reason for doing it this way, as opposed to calling the smallest disk n and the largest disk 1, will become apparent when we get to the function itself). Programmers are interested in efficiency, so we’re really only concerned with the minimum number of moves. How many steps does it take? 14? 11? You should be able to get it down to 7 fairly quickly. Let’s start with a stack of n = 3 disks as our example, using the simpleHanoi() variant. It’s not often that you can hold the steps of an algorithm in your hands. In fact, I strongly recommend that you do this right now. While I’ll be discussing the problem in Lucas’s original terms of disks and pegs, you can physically model the Tower problem with any group of objects of increasing size - say, a stack of books. We’ll get to strictHanoi() after we’ve sorted out simpleHanoi(). The second, stricter variant allows us to move disks only to a neighboring peg. Our first variation - let’s call it simpleHanoi() - will allow us to jump from peg A to peg C, even if we couldn’t land on peg B due to there being a smaller disk on B than the one we are moving. Clarke’s short story The Nine Billion Names of God.)īefore we get started, we need to be more explicit about the rules for moving disks. It’s a good thing they didn’t use a computer to avoid any mistakes! (A good case for keeping monks away from computers is made in Arthur C. Which means the world will be around for quite a while yet, at least if the disks have to be physically manipulated. Now, executing the minimum number of moves for 64 disks, at one move per second, would take something like 585 billion years. Upon completing the task, their reward would be the end of the world. Lucas fancifully set the task to a group of monks in a temple, where they manually move a stack of 64 golden disks from A to C. A larger disk can never be placed on top of a smaller disk.You have to move the disks from A to C, with the order of stacking preserved. Assume n number of disks are stacked by decreasing size on peg A. The problem was first posed by Édouard Lucas in 1883. Then we’ll spend some time understanding how that solution actually works - as we’ll see, getting the answer and knowing how it works can be two very different things.įirst, a little history. So for this puzzle we’ll be deriving the answer from first principles, which is more beneficial (and perhaps easier) than reverse-engineering the solution. The real learning, as I’ve tried to emphasize in every section of this guide to recursion, comes from an ability to work through the process by which we come to the solution.
![hanoi towers problem hanoi towers problem](https://4.bp.blogspot.com/-MiMl_ZKCkKs/Vnk3SyI2D5I/AAAAAAAAAy0/iqw84ovEbGM/s1600/Tower-Of-Hanoi-2-disk.png)
#Hanoi towers problem code
“The code is so short - how hard could it be?” are common Famous Last Words people say when they start digging into the puzzle. In this guide I’ve gone through dozens of algorithms, and I think the Tower problem is still very difficult to understand, partly because the problem and the solution are both easily stated. While I’ve studied recursion for only a brief time, I’ve become more and more surprised that many tutorials on the subject include this as only the third or fourth example (the other two are usually factorials and Fibonacci sequence). Finally, we lay siege to the Tower of Hanoi.