解き方

どのようにしてこれを解くか、ちょっと考えてみましょう。

棒は左から順にA,B,Cと呼ぶことにします。Aには、n枚の円盤が積み上げられているとします。
円盤は、半径の小さな順に、円盤1,円盤2,円盤3,円盤4,...円盤nと呼ぶことにします。

それでは、もしAにある上からn-1枚をBに移動できたとしましょう、そうすれば、Aにある一番大きな円盤nをCに移動し、Bに積んである円盤（n-1枚)すべてをCに移動できれば、完成できることになります。

今度は、「もし、n-1枚をBに移動できたとしましょう」というところに注目します。
n-1枚をAからBに移動するのは、以下のようにすればできますね。

(1) n-2枚の円盤をAからCに何らかの方法で移動します。
(2) 円盤n-1をBに移動します。
(3) Cに移動したn-2枚の円盤を何らかの方法でBに移動します。

これを最初n枚すべての移動に当てはめてみると、

(1) n-1枚の円盤をAからBに何らかの方法で移動します。
(2) 円盤nをCに移動します。
(3) Bに移動したn-1枚の円盤を何らかの方法でCに移動します。

と書けます。

枚数と移動元、移動先が異なるだけで同じような処理です。
つまり、(1)から(3)までの処理を n枚、n-1枚、n-2枚、n-3枚とどこまでも再帰的にくりかえしていきます。

そうすると、最後は、1枚の移動にたどり着くわけですが、この１枚の移動は問題なく行えますから、これですべての円盤が移動できることになります。

再帰的処理に慣れていないと、なんだか狐につままれたような説明かもしれませんね。

ここで、最初のn枚の円盤を右端に移動する処理を以下のように定義してみます。

  Move(n, a, b, c)

aからcに移動するわけですが、bも作業域として利用しますので、引数にはbも指定しておきます。
Move(n,a,b,c)の中の処理は、このMoveを使うと、手順で示した先ほどの(1)の処理「n-1枚の円盤をAからBに何らかの方法で移動します」は、

  Move(n-1,a,c,b)

と書けます。(3)の処理「Bに移動したn-1枚の円盤を何らかの方法でCに移動します」は、

  Move(n-1,b,a,c)

と書けます。

ここまでくれば、Moveを擬似コードで書くことができますね。

Move(n, a,b,c) {
    if (n > 0) {
        Move(n-1,a,c,b)
        aに残った一枚をcに移動
        Move(n-1,b,a,c)
   }
}

C#での実装

これをC#で書いてみます。a,b,cは、一番上に積んである円盤の出し入れしかできませんので、データ構造としては、Stackが適当です。
変数名は、a、b、cではなく、s1,s2,s3としています。

private void Move(Stack<int> s1, Stack<int> s2, Stack<int> s3, int n) {
    if (n > 0) {
        Move(s1, s3, s2, n - 1);
        int x = s1.Pop();
        s3.Push(x);
        Move(s2, s1, s3, n - 1);
    }
}

ここでは、Consoleアプリで実装していますが、HanoiSolverクラスは、コンソールアプリに依存していないで、GUIアプリでも利用できると思います。

表示を担当する機能は、すべてHanoiViewクラスに記述しています。

なお、HanoiSolverクラスはIObservableを実装していて、HanoiViewクラスはIObserverを実装していますから、HanoiViewクラスは、移動する途中経過を知ることができます。

using System;
using System.Collections.Generic;
using System.Linq;

namespace TowerOfHanoi
{
    public class HanoiState {
        public int Number { get; set; }
        public Stack<int> StickA { get; set; }
        public Stack<int> StickB { get; set; }
        public Stack<int> StickC { get; set; }
    }

    public class HanoiSolver : IObservable<HanoiState>  {

        private HanoiState _state = new HanoiState {
            StickA = new Stack<int>(),
            StickB = new Stack<int>(),
            StickC = new Stack<int>()
        };

        public HanoiSolver(int n) {
            _state.Number = n;
            while (n > 0)
                _state.StickA.Push(n--);
        }

        public void Solve() {
            OnChanged();
            Move(_state.StickA, _state.StickB, _state.StickC, _state.Number);

            foreach (var observer in _observers) {
                observer.OnCompleted();
            }
        }

        // 当プログラムの核となるメソッド        
        private void Move(Stack<int> s1, Stack<int> s2, Stack<int> s3, int n) {
            if (n > 0) {
                Move(s1, s3, s2, n - 1);
                int x = s1.Pop();
                s3.Push(x);
                OnChanged();
                Move(s2, s1, s3, n - 1);
            }
        }

        // 状況変化を知らせるために購読者に通知する
        private void OnChanged() {
            foreach (var observer in _observers) {
                observer.OnNext(_state);
            }
        }

        private List<IObserver<HanoiState>> _observers = new List<IObserver<HanoiState>>();

        // 購読する場合に呼び出すメソッド
        public IDisposable Subscribe(IObserver<HanoiState> observer) {
            _observers.Add(observer);
            return observer as IDisposable;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

namespace TowerOfHanoi {
    class HanoiView : System.IObserver<HanoiState> {
        // 初期状態時にもOnNextが呼ばれるので0ではなく、-1にしておく。
        private int count = -1;

        // IObserver<T> インターフェース
        public void OnCompleted() {
            Console.WriteLine($"\n{count}手で移動完了");
        }

        // IObserver<T> インターフェース
        public void OnError(Exception error) {
            Console.WriteLine("{0]", error.Message);
        }

        // IObserver<T> インターフェース
        public void OnNext(HanoiState value) {
            count++;
            DisplayState(value);
        }

        private void DisplayState(HanoiState value) {
            var t1 = TowerToString(value.Number, value.StickA);
            var t2 = TowerToString(value.Number, value.StickB);
            var t3 = TowerToString(value.Number, value.StickC);
            for (int i = 0; i < t1.Length; i++) {
                Console.WriteLine($"{t1[i]} {t2[i]} {t3[i]}");
            }
            Console.WriteLine();
        }

        private string[] TowerToString(int n, IEnumerable<int> tower) {
            // 塔の下から組み立てる　
            // 幅2の円盤だけがあるときは、tower は、{ 2 } となり、Count() == 1 になので注意する。
            var rewot = tower.Reverse().ToArray();
            var list = new List<char[]>();
            for (var i = 0; i < n; i++) {
                var w = i < rewot.Length ? rewot[i] : 0;
                var s = new string(' ', n - w) + new string('=', w * 2 + 1) + new string(' ', n - w);
                list.Add(s.ToArray());
            }
            list.Add(new string(' ', n * 2 + 1).ToArray());
            foreach (var floor in list) {
                floor[n] = '|';
            }
            // 最後に逆転させる。1階が配列の一番最後に来るようにする。
            return list.Select(f => new string(f)).Reverse().ToArray();
        }
    }
}

using System;

namespace TowerOfHanoi {
    class Program {
        static void Main(string[] args) {
            int n = 6;
            var solver = new HanoiSolver(n);
            solver.Subscribe(new HanoiView());
            solver.Solve();
        }
    }    
}

結果

n == 3 の時の実行結果

   |       |       |
  =|=      |       |
 ==|==     |       |
===|===    |       |

   |       |       |
   |       |       |
 ==|==     |       |
===|===    |      =|=

   |       |       |
   |       |       |
   |       |       |
===|===  ==|==    =|=

   |       |       |
   |       |       |
   |      =|=      |
===|===  ==|==     |

   |       |       |
   |       |       |
   |      =|=      |
   |     ==|==  ===|===

   |       |       |
   |       |       |
   |       |       |
  =|=    ==|==  ===|===

   |       |       |
   |       |       |
   |       |     ==|==
  =|=      |    ===|===

   |       |       |
   |       |      =|=
   |       |     ==|==
   |       |    ===|===


7手で移動完了

この記事は、Gushwell's C# Programming Pageで公開したものをに大幅に加筆・修正したものです。