{"id":450,"date":"2021-03-30T19:00:00","date_gmt":"2021-03-30T18:00:00","guid":{"rendered":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/?p=450"},"modified":"2022-01-24T13:34:03","modified_gmt":"2022-01-24T13:34:03","slug":"tower-hanoi","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/lidia-andre\/2021\/03\/30\/tower-hanoi\/","title":{"rendered":"Tower of Hanoi"},"content":{"rendered":"\n

I remember my parents taking my brother and I to Pavilh\u00e3o do Conhecimento, a science museum in Lisbon, to spend a day there at least once a year when we were little. And I remember that I loved those days. There were a lot of things we could do there, from playing “grown-ups” to solving “little” mathematical problems (and here I say little because they were easy enough for a kid to solve without getting frustrated). One of the problems available for us to solve was the Tower of Hanoi consisting of only 3 discs. In this post I will talk briefly about this problem and why it may be hard to solve.<\/p>\n\n\n\n

Problem<\/h3>\n\n\n\n

The Tower of Hanoi problem consists of 3 rods and n <\/span> discs of different sizes. Roughly, the goal of the problem is to move the stack of discs from the leftmost rod to the rightmost rod. However, as all problems, some rules have to be followed:<\/p>\n\n\n\n

  1. We can only move one disc at a time<\/li>
  2. We can also only move a disc if it is the uppermost disc on a stack<\/li>
  3. Finally, we cannot place a larger disc on top of a smaller one. In other words, we will always need to have cone-shape towers<\/li><\/ol>\n\n\n\n

    So, the simple example I had in my visits to Pavilh\u00e3o do Conhecimento can be solved as shown in the figure below:<\/p>\n\n\n\n

    \"\"
    Image taken from here<\/a><\/figcaption><\/figure><\/div>\n\n\n\n

    We can see that 7 <\/span> steps were required to solve this simple example. This corresponds to 2^n-1 <\/span>. You can start to see why this may be difficult to solve in some situations. Imagine if you had 10 <\/span> discs, you would solve the problem in 1023 <\/span> steps. You may argue it’s doable but you would need a lot of patience to spend time moving pieces 1023 <\/span> times. <\/p>\n\n\n\n

    So, what can be done to efficiently determine the steps to take with a fairly large number of discs? Well, we can construct an algorithm. If we think about it, we can solve the Tower of Hanoi problem for n <\/span> discs by solving it for n-1 <\/span> discs. And we can solve the problem with n-1 <\/span> discs by solving it for n-2 <\/span> disks. And you get the idea: each smaller stack is a sub-problem of the original. For this motive, we can solve the problem by using a recursive algorithm<\/span>. So, to move n <\/span> discs from the leftmost rod, say A <\/span>, to the rightmost rod, say C <\/span>, the algorithm can be <\/p>\n\n\n\n

    1. Move n-1 <\/span> discs from A <\/span> to B <\/span> (steps 1 to 3 on the image)<\/li>
    2. Move the last, and larger, disc from A <\/span> to C <\/span> (step 4 on the image)<\/li>
    3. Move n-1 <\/span> discs from B <\/span> to C <\/span> (steps 5 to 7 on the image)<\/li><\/ol>\n\n\n\n

      Note that step 1 can be solved taking the exact three steps, and so on.<\/p>\n\n\n\n

      Conclusion<\/h3>\n\n\n\n

      It may seem a simple enough problem to solve but, in reality, as the complexity of the algorithm is proportional to 2^n <\/span>, it will take a long time to solve when the number of discs is large. <\/p>\n\n\n\n

      I hope you found this post interesting! If so, you can read more about the Tower of Hanoi problem here:<\/p>\n\n\n\n