ハノイの塔を再帰で解く

再帰的プログラミングの例として有名なハノイの塔のパズルを解くプログラムをC#で書いてみました。

■ルール
ハノイの塔のルールは以下の通りです。

・3本の棒と穴の開いた円盤があります。
・円盤はそれぞれ大きさが異なります。
・初期状態は、すべての円盤が左端の棒に大きいものが下になるように積み上げられています。
・円盤は一回に1枚ずつ移動できますが、小さな円盤の上に大きな円盤を乗せることはできません。

これらのルールに従い、すべての円盤を一番右の棒に移動させることができれば完成です。

TextBoxに円盤の数を入れて、Startボタンを押してください。解答が見られます。アニメーションも付けたかったのですが、そこまで時間的余裕がないのでやってません。

■解き方
どのようにしてこれを解くか、ちょっと考えてみましょう。
棒は左から順にA,B,Cと呼ぶことにします。Aには、n枚の円盤が積み上げられているとします。
円盤は、半径の小さな順に、1,2,3,4,...Nと呼ぶことにします。
もし、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枚の移動にたどり着くわけですが、この1枚の移動は問題なく行えますから、これですべての円盤が移動できることになります。

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

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

aからcに移動するわけですが、bも作業域として利用しますので、引数にはbも指定しておきます。
Move(n,a,b,c)の中の処理は、このMoveを使うと、先ほどの(1)の処理は、

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

と書けます。(3)の処理は、

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

と書けます。

■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#で書いてみます。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);
    }
}

実際のコードでは、GUI側に状態変更の通知をするために、OnChangedメソッドを実装し、イベントを発行しています。

ここでは、Silverlightで実装していますが、Hanoiクラスは、WindowsFormsでもWPFでもコンソールアプリでも利用できます。
なお、GUIのハングアップを防ぐために、Taskクラスを利用して非同期処理をしています。.NET Framework3.5以前の環境で動作させたいときには、BackgroundWorkerなど他の実装に変える必要があります。

以下に、C#のコードとXAMLを示します

■Hanoi.cs
using System;
using System.Linq;
using System.Collections.Generic;

namespace Hanoi {
    public class HanoiArgs : EventArgs {
        public List<int> StickA { get; set; }
        public List<int> StickB { get; set; }
        public List<int> StickC { get; set; }
    }

    public class Hanoi {
        private Stack<int> StickA = new Stack<int>();
        private Stack<int> StickB = new Stack<int>();
        private Stack<int> StickC = new Stack<int>();
        private int count;

        public event EventHandler<HanoiArgs> Chenged;

        public Hanoi(int n) {
            count = n;
            while (n > 0)
                StickA.Push(--n);
        }

        public void Solve() {
            OnChanged();
            Move(StickA, StickB, StickC, count);
        }

        // 当プログラムの核となるメソッド        
        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() {
            if (Chenged != null)
                Chenged(this, new HanoiArgs {
                    StickA = StickA.Reverse().ToList(),
                    StickB = StickB.Reverse().ToList(),
                    StickC = StickC.Reverse().ToList()
                });

        }
    }

}


■MainPage.xaml.cs
using System.Collections.Generic;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Shapes;
using System.Threading.Tasks;

namespace Hanoi {
    public partial class MainPage : UserControl {
        public MainPage() {
            InitializeComponent();
        }

        private Hanoi hanoi;
        private RectangleFactory rectFactory;
        private TaskScheduler uiTaskScheduler = TaskScheduler.FromCurrentSynchronizationContext();

        private void button1_Click(object sender, RoutedEventArgs e) {
            int n = int.Parse(textBox1.Text);
            rectFactory = new RectangleFactory(n, (int)this.grid1.ActualWidth - 2);
            hanoi = new Hanoi(n);
            hanoi.Chenged += hanoi_Chenged;
            Task.Factory.StartNew(() => hanoi.Solve());
        }

        // 状態が変化した
        void hanoi_Chenged(object sender, HanoiArgs e) {
            var progressTask = new Task(() => {
                PrintStack(e.StickA, grid1);
                PrintStack(e.StickB, grid2);
                PrintStack(e.StickC, grid3);
            });
            // UIへの操作を行うので、uiTaskSchedulerを指定する。
            progressTask.Start(uiTaskScheduler);
            // あえてSleepを入れて描画の変化がわかるようにする。
            System.Threading.Thread.Sleep(800);
        }

        private void PrintStack(List<int> list, Grid grid) {
            // いったんブロックはすべて消去してから、再度新たなブロックを描画する。
            grid.Children.Clear();
            int bottom = 0;
            foreach (var size in list) {
                var rect = rectFactory.GetRectangle(size);
                rect.Margin = new Thickness(0, 0, 0, bottom);
                bottom += (int)rect.Height + 1;
                grid.Children.Add(rect);
            }
        }
    }

    class RectangleFactory {
        private int interval;
        private int maxWidth;
        private int minWidth;

        // コンストラクタ
        // 個数と最大幅から、各ブロック(Rectangle)の幅の差を求める
        public RectangleFactory(int n, int maxWidth) {
            this.maxWidth = maxWidth;
            this.minWidth = 20;
            this.interval = (maxWidth - minWidth) / (n - 1);
        }

        // sizeには、1からブロックの数までの値が渡ってくる
        // このsizeの値に応じたRectangleを生成する。
        // sizeの値が大きいほど幅が広い。
        public Rectangle GetRectangle(int size) {
            Rectangle rect = new Rectangle();
            rect.Width = this.minWidth + size * interval;
            rect.Height = 20;
            rect.Fill = new SolidColorBrush(Colors.LightGray);
            rect.Stroke = new SolidColorBrush(Colors.Black);
            rect.HorizontalAlignment = System.Windows.HorizontalAlignment.Center;
            rect.VerticalAlignment = System.Windows.VerticalAlignment.Bottom;
            int bottom = size * ((int)rect.Height + 1);
            rect.Margin = new Thickness(0, 0, 0, bottom);
            return rect;
        }
    }
}


■MainPage.xaml
<UserControl x:Class="Hanoi.MainPage"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
    xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
    mc:Ignorable="d"
    d:DesignHeight="160" d:DesignWidth="280">

    <Grid x:Name="LayoutRoot" Background="White">
        <Button Content="Start" Height="23" HorizontalAlignment="Left" Margin="79,8,0,0" 
                Name="button1" VerticalAlignment="Top" Width="75" Click="button1_Click" />
        <TextBox Height="24" HorizontalAlignment="Left" Margin="20,7,0,0" Name="textBox1" 
                 VerticalAlignment="Top" Width="54" Text="3" />
        <Grid Margin="15,40,15,15">
            <Grid.ColumnDefinitions>
                <ColumnDefinition Width="*"/>
                <ColumnDefinition Width="*"/>
                <ColumnDefinition Width="*"/>
            </Grid.ColumnDefinitions>
            <Rectangle Fill="#FF808080" HorizontalAlignment="Center" Stroke="Black" 
                       Width="3"/>
            <Rectangle Fill="#FF808080" HorizontalAlignment="Center" Stroke="Black"
                       Width="3" Grid.Column="1"/>
            <Rectangle Fill="#FF808080" HorizontalAlignment="Center" Stroke="Black" 
                       Width="3" Grid.Column="2"/>
            <Grid Name="grid1" />
            <Grid Name="grid2" Grid.Column="1"/>
            <Grid Name="grid3" Grid.Column="2"/>
        </Grid>
    </Grid>
</UserControl>