#ルール
ハノイの塔のルールは以下の通りです。
- 3本の棒と穴の開いた円盤があります。
- 円盤はそれぞれ大きさが異なります。
- 初期状態は、すべての円盤が左端の棒に大きいものが下になるように積み上げられています。
- 円盤は一回に1枚ずつ移動できますが、小さな円盤の上に大きな円盤を乗せることはできません。
これらのルールに従い、すべての円盤を一番右の棒に移動させることができれば完成です。
解き方
どのようにしてこれを解くか、ちょっと考えてみましょう。
棒は左から順に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で公開したものをに大幅に加筆・修正したものです。