Towers of Hanoi

Definition

The Towers of Hanoi is a mathematical puzzle. In legend, the monks of Hanoi were commanded by god to solve this problem with 64 golden disks It is as follows: You have 3 poles, and a number of disks. Your task is to move all of the disks from the first pole to the last pole. Only one disk may be moved at a time, and big disks cannot be placed on top of a small disk.

Recursive Solution

The solution can be found using recursion as follows. Lets say we have 4 disks. We know that if we can move 3 of the disks to the middle pole, then we can move the bottom one over, and then move the 3 disks back on top of it. But we do not know how to move 3, but we know that if we know how to move 2 disks, than we can move the bottom one over, and the 2 back on top of it. But we do not know how to move 2, but we do know that if we can move one to the middle, then we can move the bottom one over, and put the one in the middle back on top. And we know how to move one, so then we know how to move all of them.

Runtime

The Towers of Hanoi has a runtime of O(2n). This solution takes much longer the greater the number of disks used. As can be seen by Mr. Markowitz's story with his unnamed friend from college who did not realize this, this has a potential for an overflow error if the number of disks is too large for a computer to compute, or just takes years to figure out by the monks at the Tower of Hanoi.

Visuals

Three Rings

Towers1

2n-1

Towers2
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License