Many will be familiar with this puzzle which exists also as an online game; its rules are simple: you can only move one disc at a time and cannot place a disc over a smaller one. The objective is to move all discs from the C to the A position.
The entertainment value of such puzzles lies in the utter uselessness of the objective, and while it is deceivingly simple, attempting to solve it without a method leads to failure; I found an extremely elegant, recursive way to solve it and to calculate the number of moves it will take.
Obviously, moving the topmost disc from C to anywhere requires one move; moving the top two involves three moves:
- move the smallest disc to B
- move the second-smallest disc to A
- move the smallest disc from B to C
Since we know this, we can immediately determine that moving the top THREE discs requires 7 moves:
In fact, moving the top “n” discs always requires 2n-1 moves, allowing us to say that moving all 8 discs can be achieved in 28-1=255 moves.
The things I HAVEN’T demonstrated are WHY the number of moves is always a power of 2 minus 1 and whether this is the MINIMUM number of moves to achieve the solution.