Towers of Hanoi–WPF Style (part 1)

February 11, 2012

3 comments

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:

image

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):

  1. Move N-1 discs from pole 1 to pole 2 (while observing the rules)
  2. Move the remaining disc (the largest one) from pole 1 to pole 3
  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:

  1. sealed class HanoiMove {
  2.     public readonly int From;
  3.     public readonly int To;
  4.  
  5.     public HanoiMove(int from, int to) {
  6.         From = from; To = to;
  7.     }
  8.  
  9.     public override string ToString() {
  10.         return string.Format("Move {0} to {1}", From, To);
  11.     }
  12. }

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:

  1. class HanoiTower {
  2.     public int Discs { get; private set; }
  3.  
  4.     public HanoiTower(int discs) {
  5.         Discs = discs;
  6.     }
  7.  
  8.     public IEnumerable<HanoiMove> Solve() {
  9.         return MoveDiscs(Discs, 1, 3, 2);
  10.     }
  11.  
  12.     private IEnumerable<HanoiMove> MoveDiscs(int discs, int from, int to, int via) {
  13.         if(discs == 1) {
  14.             yield return new HanoiMove(from, to);
  15.             yield break;
  16.         }
  17.         foreach(var move in MoveDiscs(discs – 1, from, via, to)) {
  18.             yield return move;
  19.         }
  20.         foreach(var move in MoveDiscs(1, from, to, 0)) {
  21.             yield return move;
  22.         }
  23.         foreach(var move in MoveDiscs(discs – 1, via, to, from)) {
  24.             yield return move;
  25.         }
  26.     }
  27. }

MoveDiscs is the key method returning an IEnumerable<HanoiMove>. Don’t you just love those yields?

Let’s run with N=4 (15 moves):

  1. var tower = new HanoiTower(4);
  2. foreach(var move in tower.Solve())
  3.     Console.WriteLine(move);

image

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.

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

3 comments

  1. HartwellSeptember 28, 2012 ב 04:19

    Hi to every single one, it’s genuinely a pleasant for me to pay a quick visit this website, it consists of important Information.

    Reply
  2. ����ͥ� ؔ��August 17, 2013 ב 03:45

    Jonathan Whan, assistant superintendent for instruction and scholar providers, claimed the district will use caution though researching the onetoone application for your potential.

    Reply