Now that we have developed a fundamental understanding of how different counting systems, especially binary, work, we can begin to understand the optimal solution to the Towers of Hanoi.
One by One
Because binary digits are restricted to just one of two values, counting in binary has a particularly interesting rhythm. Understanding this rhythm is crucial in solving the Towers of Hanoi problem. This online binary counter is particularly useful in visualizing this rhythm. Beginning from zero, continue to count up, adding one with each step. Keep track of the index of the value that switches to a 1 at each step:
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, …
Solution to the Towers of Hanoi
Interestingly enough, the most optimal solution to the Towers of Hanoi comes from following this rhythm exactly. To tie the two together, first assign numeric indices to the disks: 0 is the smallest, 1 the next smallest, and so on. Then, simply follow the pattern, at each step moving the disk whose index matches the next number in the sequence.
For example, consider the 3 disk problem:
- 0: move disk 0 to the right peg
- 1: move disk 1 to the middle peg
- 0: move disk 0 to the middle peg
- 2: move disk 2 to the right peg
- 0: move disk 0 to the left peg
- 1: move disk 1 to the right peg
- 0: move disk 0 to the right peg
And then we are done! There are some beautiful symmetries to this pattern. Also interesting is the fact that, for a setup with n disks, the optimal solution requires exactly 2^n – 1 moves.
Why Does This Work?
In so few words: recursion! Both the rhythm of binary counting and the problem of the Towers of Hanoi are self-similar problems. The idea of self-similarity ties directly into recursion: the full process, whether that’s counting up to a certain number or solving a problem with a certain number of disks, involves completing a smaller version of the process.
In the Towers of Hanoi, consider again the 3 disk problem. If we were somehow able to move the stack of the 2 smallest disks as a single unit, then the problem would reduce to three steps:
- Move the 2-disk unit off of the third disk
- Move the third desk to the right peg
- More the 2-disk unit onto the third disk
So, through a recursive approach, the problem becomes much simpler to solve.
In the process of binary counting, return to the counter visualizer. Count up to the number 7 (111 in binary). Notice that we count up to the number 3 (11 in binary), roll over to 4 (100 in binary), and then count up three more to get to 7 (111). This exactly mirrors the recursive pattern in the Towers of Hanoi!
Conclusion
Oftentimes in mathematics, and in problem solving in general, finding an inventive way to connect and reduce one problem to another can make understanding optimal solutions much easier. The Towers of Hanoi, though it may appear as a confusing game at first, cleanly works in parallel to just counting up by one in binary.
References
- https://www.khanacademy.org/computing/computer-science/algorithms/towers-of-hanoi/a/towers-of-hanoi
- https://www.mathsisfun.com/games/towerofhanoi.html
- https://www.youtube.com/watch?v=2SUvWfNJSsM
