I remember many years ago (at least 15), I was learning Prolog. I used the “Turbo Prolog” package from (what was once) Borland. One of the nice examples there was a solution of the Towers of Hanoi, with a simple animation that showed the steps graphically. This was all textual graphics (today’s Console windows), but it was impressive (at least it impressed me). Prolog was used to show off its AI capabilities, which are, in fact, a recursive, backtracking engine.
No matter; we can do it in C#.
Towers of Hanoi
The story of the Towers originate from an old legend (there are various versions), but may favorite is this: a group of monks were given a task (by an ancient prophecy), to transfer 64 giant discs (with sizes starting from large at the bottom to small at the top) from one large pole to another, using a third pole as an intermediary, all while observing 2 rules:
1. Only one disc can be moved at a time.
2. Under no circumstance should a larger disc lie on top of a smaller one.
When they succeed, the world would come to an end, and the monks would be granted eternal life.
Although this may be an old legend, it’s not far off the truth. It can be shown that the minimal number of moves is 2^N –1 (2 to the Nth power minus 1) where N is the number of discs. If N=64, this results in 18,446,744,073,709,551,615 moves. Assuming the monks work at a pace of one disc per second (highly unlikely), they would still need around 585 billion years to complete the task. This is a very long time – just as a quick comparison: the age of the universe is estimated at 13.7 billion years. Now it’s obvious why it’s fair to assume the world would end by then.
Even with a million moves per second, we would still need 585 thousand years!
Still, we can use a smaller N to solve the problem in our lifetime.
Here’s a starting point (this app is developed in the second part) where N = 5:
A recursive solution
The Towers of Hanoi problem has a simple iterative solution (or at least is simple once you know of it…), but we’ll take the recursive solution approach.
To move N discs from pole 1 to pole 3 (using pole 2 as an intermediary):
- Move N-1 discs from pole 1 to pole 2 (while observing the rules)
- Move the remaining disc (the largest one) from pole 1 to pole 3
- Move N-1 discs from pole2 to pole 3
Recursively, we would end up with N=1, for which a trivial transfer can be made.
Let’s create a .NET class that solves the problem. Its output should be a set of moves. Let’s first define a move:
A very simple class.
Now for the fun part: solving the problem. The result should be a collection of HanoiMove objects, but we don’t want to calculate everything in advance – this may take too much time and even result in OutOfMemoryException. The easiest approach is with the yield keyword. This is one of my favorites, no doubt:
MoveDiscs is the key method returning an IEnumerable<HanoiMove>. Don’t you just love those yields?
Let’s run with N=4 (15 moves):
Not easy to visualize, right?
In the second part we’ll see how to use the preceding code in a WPF application (and maybe even Silverlight) to visualize everything.