【Java】ハノイの塔を解く

　再帰的なアルゴリズムの用例としてよく使われる「ハノイの塔」を解いてみよう。実際試しに「15パズル」と同じ幅優先探索でもやってみたが、円盤の数(N)が12くらいで重くなる(約3秒)。今回の再帰は深さ優先探索というより、解法手順を直接的に操作するような方法となる。こちらの方は円盤20枚ギリギリ行けるようだ(21枚で約4秒)。

●ハノイの塔 再帰的解法

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;

public class TowerOfHanoi {

    public static void main(String[] args) throws Exception {
        new TowerOfHanoi();
    }

    int N = 4;        //円盤の数
    Hanoi hanoi;
    List<String> list = new ArrayList<String>();    //手の記録

    public TowerOfHanoi() throws Exception {
        hanoi = new Hanoi(N);
        list.add("(init) " + hanoi.toString());    //初期位置:[0]

        recursive(N, 0, 2);    //A → C へ

        int i = 0;
        for (String e : list) {
            System.out.println((i++) + " : " + e);
        }
    }

    //再帰的解法
    void recursive(int n, int from, int to) {
        if (n > 0) {
            int work = 3 - (from + to);
            recursive(n - 1, from, work);
            hanoi.move(from, to);
            String log = String.valueOf((char)('A' + from)) + " -> " + String.valueOf((char)('A' + to));
            log += " " + hanoi.toString();
            list.add(log);    //手の記録
            recursive(n - 1, work, to);
        }
    }

    //ハノイの塔 状態保持クラス
    class Hanoi {
        int n;    //円盤の数

        @SuppressWarnings("unchecked")
        Deque<Integer>[] stack = new Deque[3];    //塔ごとの円盤の状態
        {
            for (int i = 0; i < 3; i++) {
                stack[i] = new ArrayDeque<Integer>();
            }
        }

        //コンストラクタ
        public Hanoi(int n) {
            this.n = n;

            while (n > 0) {
                push(0, n--);    //初期位置は左(0)に固定
            }
        }

        //円盤を追加(塔:0～2/円盤:1～n)
        void push(int to, int no) {
            stack[to].addLast(no);
        }

        //円盤を取り出す(塔:0～2)
        int pop(int from) {
            return stack[from].removeLast();
        }

        //円盤の移動(塔:0～2)
        void move(int from, int to) {
            push(to, pop(from));
        }

        //塔の円盤(スタック)の状態を文字列にする
        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder(n * 9);
            for (int i = 0; i < 3; i++) {
                if (i > 0) {
                    sb.append(",");
                }
                if (stack[i].isEmpty()) {
                    sb.append("[]");
                    continue;
                }

                int j = 0;
                Iterator<Integer> it = stack[i].iterator();
                sb.append("[");
                while (it.hasNext()) {
                    int v = it.next();
                    if (v == 0) {
                        break;
                    }
                    if (j++ > 0) {
                        sb.append(",");
                    }
                    sb.append(v);
                }
                sb.append("]");
            }
            return sb.toString();
        }
    }
}

0 : (init) [4,3,2,1],[],[]
1 : A -> B [4,3,2],[1],[]
2 : A -> C [4,3],[1],[2]
3 : B -> C [4,3],[],[2,1]
4 : A -> B [4],[3],[2,1]
5 : C -> A [4,1],[3],[2]
6 : C -> B [4,1],[3,2],[]
7 : A -> B [4],[3,2,1],[]
8 : A -> C [],[3,2,1],[4]
9 : B -> C [],[3,2],[4,1]
10 : B -> A [2],[3],[4,1]
11 : C -> A [2,1],[3],[4]
12 : B -> C [2,1],[],[4,3]
13 : A -> B [2],[1],[4,3]
14 : A -> C [],[1],[4,3,2]
15 : B -> C [],[],[4,3,2,1]

　ハノイの塔はスタック構造の用例としても良いので、各塔の円盤の状態を Deque（デック：双方向キュー）で実装（ArrayDeque）してある。Java には Stack というクラスもあるが、Vector クラスの拡張のため、現在では非推奨となっている（Vector を使う場合も、普通は ArrayList などを使う）。Deque（デック）はスタックらしいメソッド：push()、pop()、peek() なども持っているのだが、前方から追加・削除を行うので、パズルの状態を正確に再現するため、クラス内で後方から追加・削除できるメソッドに変えてある。スタックは通常の配列でも簡単に実装できるので、自分の好きなように修正しても良いだろう。また、toString() メソッドで状態を文字列に変換できるようにしてあるが、ここを修正すれば表示形式も変更できる。手の記録は再帰部分で List に追加しているだけだ。

　塔の円盤の状態を保持するクラスや手の記録をする部分を付け加えているので長く感じるが、パズルを解く中核は以下の部分になる。

void recursive(int n, int from, int to) {
    if (n > 0) {
        int work = 3 - (from + to);
        recursive(n - 1, from, work);
        hanoi.move(from, to);
        recursive(n - 1, work, to);
    }
}

　この再帰が何をしているのか、簡単に図にしてみよう。多少仮想的な概念を説明しているので、実際の手ではないので注意して欲しい。

　まずは円盤２枚で考えてみよう。

　実は最短の手で移動するにはパターンがあって、移動元と移動先以外の１本の塔を作業用としたとき、「移動元→作業用、移動元→移動先、作業用→移動先」(A→B, A→C, B→C)と移動すると良いのである。

　次に円盤３枚で考えてみよう。ただしここでは本当に３枚で移動するのではなく、一番下の円盤と、それ以外の円盤をまとめたものを移動すると考えてみよう。まとめた部分を▲で囲むと以下のような感じになる。

　では円盤４枚（ｎ枚）では？。動きとしては２枚にしているようなものなのでもちろん変わらない。

　つまりよく考えれば、円盤の枚数を n 枚とするとき、その上にある ▲(n - 1) 枚も同じように「A→B」へ動かし、一番下の n を移動先へ、そしてまた ▲(n - 1) 枚を「B→C」へ移動すれば良いということがわかる。それが４枚のとき上の３枚を、３枚のとき上の２枚を・・・と入れ子になっているというわけだ。よって再帰が適用できる。もちろん１枚のときは、ただ移動先へ直接移動させれば良い。

　それと、これまでの図にも色分けされているのだが、改めて移動元と移動先、作業用の関係がどうなっているか考えてみよう。色だけを見てみれば、パターン化されているのがわかる。

　それら移動元を「from」、移動先を「to」、作業用を「work」とすると以下のように書けることがわかる。これで再帰部分が完成だ。見比べてみよう。

void recursive(int n, int from, int to) {
    if (n > 0) {
        int work = 3 - (from + to);
        recursive(n - 1, from, work);
        hanoi.move(from, to);
        recursive(n - 1, work, to);
    }
}

　ここでは操作手順での解法しかしてないので、数学的な証明やまだ疑問に思うことがあるなら参考ページを載せておこう。ハノイの塔は色々研究されているので、ググればもっと出てくるだろう。

（参考）
・ハノイの塔に挑戦
・2.2 ハノイの塔

　余談だが、参考資料や Wikipedia にも載っているが、最短手数は2ⁿ-1 となり、円盤が 64 枚のとき、18446744073709551615 手となる。１回の移動に１秒かかるとすれば、約 5845 億年かかるそうだ(笑)。そのとき世界は崩壊し終焉を迎えるというおとぎ話もある。

（関連記事）
【Java】８クイーンを解く[８クイーン問題]
【Java】15パズルを解く [A*(A-star)アルゴリズム]