[Haskell] Haskellでハノイの塔を解く

Haskellのお勉強でハノイの塔を解く

Haskellの勉強がしたい … と思い、Haskellでハノイの塔を解く処理を書いてみました。Haskellの文法をそっくり忘れていましたが、思い出しつつ書きました。

まずはコードを載せます。

main = do
    print $ hanoi 3 "a" "b" "c"
    -- ["a -> b","a -> c","b -> c","a -> b","c -> a","c -> b","a -> b"]

hanoi :: Int -> String -> String -> String -> [String]
hanoi 0 _ _ _ = []
hanoi n a b c = r1 ++ r2 ++ r3
    where
        r1 = hanoi (n-1) a c b
        r2 = [a ++ " -> " ++ b]
        r3 = hanoi (n-1) c b a

ハノイの塔のルール

まずはハノイの塔についてですが、Wikipediaを見れば早いのでどうぞ。ルールだけ引用すると以下の通りです。

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

ハノイの塔のアルゴリズム

このゲームを解くためには円盤の移動を繰り返す必要があります。この移動を再帰アルゴリズムとして実装してやります。

前提条件として、杭を便宜上左から順に “a”, “b”, “c” と呼ぶこととします。
そして円盤n個をそっくり “a” から “b” へ移動させる関数を考えてみます。

円盤が2つの場合

まず円盤が2つの場合を考えてみます。杭 “a” から杭 “b” に2つの円盤を移動させるには、以下の順番で動かします。

1. 円盤1を a -> c へ移動させる
2. 円盤2を a -> b へ移動させる
3. 円盤1を c -> b へ移動させる

円盤が1つの場合

次に円盤が1つの場合を考えます。これは単純に移動させるだけです。

1. 円盤1を　a -> b へ移動させる

円盤が0の場合

円盤がない場合は当然移動の必要はありません。

円盤がnの場合

上記例を踏まえた上で、円盤の数がnの場合の処理を考えてみます。ですがここでは具体例としてn=3の場合を考えてみます。
ここで具体的な手順ではなく、おおまかな考え方をしてみます。

1. 円盤1,2を a -> c へ移動させる
2. 円盤3を a -> b へ移動させる
3. 円盤1,2を c -> b へ移動させる

ここでの手順1について考えてみると、円盤が2の場合の処理と同じなことに気が付きます。手順3は手順1と同じ動作(単に移動先が違うだけ)です。
円盤3は一番大きいものなので上に円盤1も円盤2も乗せることができる、つまり円盤3は無視して一時置き場として利用できます。

さらにこれを円盤の数がnの場合について考えてみると次のようになります。

1. 円盤[1..n-1]を a -> c へ移動させる
2. 円盤nを a -> b へ移動させる
3. 円盤[1..n-1]を c -> b へ移動させる

再帰関数として実装する

まずハノイの塔を解くための関数 hanoi の説明をします。引数は4つ取ります。
第1引数のIntが円盤の数nです。第2引数から第3引数までの文字列が杭の名前です。
それぞれ左から “a”, “b”, “c”とか適当に名前をつけて渡してやればよいです。

第2引数が円盤の移動元、第3引数が円盤の移動先、第4引数が移動の最中に使う一時置き場です。

戻り値はとくになくてもいいのですが、移動処理代わりのログ(文字列のリスト)を返すようにしています。

見やすくするために r1, r2, r3と分けて移動結果を取りそれを連結させています。

注意点

注意点として、実際には移動の処理はありません。移動部分の処理代わりの文字列でのログを書き出しているだけです。

C#でも書いてみる

ちなみにC#でも書いてみました。大体同じような流れでしょうか。

using System;
using System.Collections.Generic;

namespace Hanoi
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(string.Join(", ", hanoi(3, "a", "b", "c")));
            Console.ReadKey();
        }

        private static List<string> hanoi(int n, string a, string b, string c)
        {
            var result = new List<string>();
            if (n > 0)
            {
                result.AddRange(hanoi(n - 1, a, c, b));
                result.Add($"{a} -> {b}");
                result.AddRange(hanoi(n - 1, c, b, a));
            }
            return result;
        }
    }
}