こんばんは。
肩こりがひどい人なので最近ストレッチをしているのですが、
伸ばし過ぎてむしろ体が痛くなりました私です。
今日はハノイの塔で遊びます。
ハノイの塔 - Wikipedia
インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールの説明は省略）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。
まぁいいでしょう。
ハノイの塔って何するの？
簡単にルール説明をします。
①3本の棒と、大きさの違う穴のあいた円盤をいくつか用意します
②いちばん左の棒に小さい円盤が上になるように全部積みます
③円盤を1枚ずつ移動できますが、小さい円盤の上に大きい円盤を乗せることはできません
④すべての円盤をいちばん右の棒に移動させましょう
ためしに3枚でやってみます。
7手で移動できましたね。
アルゴリズムを考える
さて、アルゴリズムを考えなければいけないのですが、
さっきの3枚での移動の3手目と4手目をちょっと見てみます。
一番大きい円盤をAからCに移動するために、
上の2枚を真ん中の棒に集めていますね。
当然4枚でも同じことをしなくてはなりません。
真ん中に3枚で、一番大きいのをAからCに移動ですね。
ということはです、
【3枚を移動する場合】
①上の2枚をA⇒Bに移動
②一番下をA⇒Cに移動
③上の2枚をB⇒Cに移動
【4枚を移動する場合】
①上の3枚をA⇒Bに移動
②一番下をA⇒Cに移動
③上の3枚をB⇒Cに移動
というルールがあることに気付きます。
「4枚を移動する場合」①と③はまさに「3枚を移動する場合」ですから、
再帰処理を使えばうまくいきそうなことがわかります。
プログラムにする
さて、ではプログラムにしたいわけですが、
ネットで見かけるサンプルのプログラムは、
「A⇒C、A⇒B、C⇒A...」
とかで、実際にどんな感じで移動されていくかがよくわからないのが残念です。
なので、コンソールにちゃんと見えるように作るのを今回の目的にします。
正直、どう移動するかだけ表示するなら数行のプログラムで書けます。
とりあえず、円盤はLIFOになりそうですからスタックの構造としてDequeで確保しておきましょう。
（Dequeは双方向なのでキューにもスタックにも使えます）
class Hanoi { /** 円盤の数 */ private final int num; /** 棒A */ private final Deque<Integer> a = new LinkedList<>(); /** 棒B */ private final Deque<Integer> b = new LinkedList<>(); /** 棒C */ private final Deque<Integer> c = new LinkedList<>(); /** * コンストラクタ * * @param num 円盤の数 */ public Hanoi(int num) { this.num = num; IntStream.rangeClosed(1, num).forEach(a::add); } }
n個の円盤をaからcに移動するメソッドをこんな感じになりますね。
/** * n個の円盤をAからCに移す処理 * * @param n 移動しようとしている塔の高さ * @param a 移動元の棒 * @param b 今回移動の対象にならない棒 * @param c 移動先の棒 */ void move(int n, Deque<Integer> a, Deque<Integer> b, Deque<Integer> c) { if (n > 0) { // n-1個の円盤をAからBに移す // Aに一つだけ残った円盤をCに移す // n-1個の円盤をBからCに移す } }
で、再帰を使うのこんな感じになるわけですね。
/** * n個の円盤をAからCに移す処理 * * @param n 移動しようとしている塔の高さ * @param a 移動元の棒 * @param b 今回移動の対象にならない棒 * @param c 移動先の棒 */ void move(int n, Deque<Integer> a, Deque<Integer> b, Deque<Integer> c) { if (n > 0) { // n-1個の円盤をAからBに移す this.move(n - 1, a, c, b); // Aに一つだけ残った円盤をCに移す c.push(a.pop()); // n-1個の円盤をBからCに移す this.move(n - 1, b, a, c); } }
で、他はおまけなのですが、全体像はこんな感じです。
思ったよりコンソールにきれいに表示するのが難しかったので、だいぶダサいです。
public class Main { public static void main(String[] args) { Hanoi hanoi = new Hanoi(3); hanoi.doExecute(); } /** * ハノイくん */ private static class Hanoi { /** 円盤の数 */ private final int num; /** 棒A */ private final Deque<Integer> a = new LinkedList<>(); /** 棒B */ private final Deque<Integer> b = new LinkedList<>(); /** 棒C */ private final Deque<Integer> c = new LinkedList<>(); /** * コンストラクタ * * @param num 円盤の数 */ public Hanoi(int num) { this.num = num; IntStream.rangeClosed(1, num).forEach(a::add); } /** * n個の円盤をAからCに移す処理 */ public void doExecute() { this.show(); this.move(num, a, b, c); } /** * n個の円盤をAからCに移す処理（再帰） * * @param n 移動しようとしている塔の高さ * @param a 移動元の棒 * @param b 今回移動の対象にならない棒 * @param c 移動先の棒 */ private void move(int n, Deque<Integer> a, Deque<Integer> b, Deque<Integer> c) { if (n > 0) { // n-1個の円盤をAからBに移す this.move(n - 1, a, c, b); // Aに一つだけ残った円盤をCに移す c.push(a.pop()); this.show(); // n-1個の円盤をBからCに移す this.move(n - 1, b, a, c); } } /** * 描画する */ private void show() { // 描画用に変換 List<String> listA = this.toDisplayList(a); List<String> listB = this.toDisplayList(b); List<String> listC = this.toDisplayList(c); // zip作ってもいいけど面倒なので… for (int i = 0; i < listA.size(); i++) { System.out.println(listA.get(i) + " " + listB.get(i) + " " + listC.get(i)); } System.out.println(); } /** * 描画用の文字列リストに変換する */ private List<String> toDisplayList(Deque<Integer> stack) { // 円盤を描画し、中央揃えにする（2倍しているのは奇数だとずれちゃうから） List<String> list = stack.stream().map(i -> Util.bidiPad(Util.repeat("*", i * 2), num * 2)) .collect(Collectors.toList()); // ずれちゃうのでリストを埋めておく return Util.fillListFront(list, Util.repeat(" ", num * 2), num); } } /** * いろいろ */ private static class Util { /** * リストを指定した要素で手前から埋める */ private static <T> List<T> fillListFront(List<T> list, T fillObj, int size) { List<T> tmp = new ArrayList<>(Collections.nCopies(size, fillObj)); tmp.addAll(list); return tmp.subList(tmp.size() - size, tmp.size()); } /** * 文字列を指定回数繰り返す */ private static String repeat(String str, int cnt) { return Stream.generate(() -> str) .limit(cnt) .collect(Collectors.joining()); } /** * 文字列を指定した文字数に両側から半角スペースでパディングする */ private static String bidiPad(String str, int cnt) { String half = repeat(" ", (cnt - str.length()) / 2); return half + str + half; } } }
実行してみる
5だとこんな感じ。
**
****
******
********
**********
****
******
********
********** **
******
********
********** **** **
******
******** **
********** ****
******** **
********** **** ******
**
********
********** **** ******
**
******** ****
********** ******
**
******** ****
********** ******
**
****
********** ******** ******
** ****
********** ******** ******
**** **
********** ******** ******
**
****
********** ******** ******
**
**** ******
********** ********
**** ******
********** ******** **
****
******
********** ******** **
**
****
******
********** ********
**
****
******
******** **********
****
******
** ******** **********
****** ****
** ******** **********
**
****** ****
******** **********
**
****
****** ******** **********
** ****
****** ******** **********
**** **
****** ******** **********
**
****
****** ******** **********
**
**** ********
****** **********
**
**** ********
****** **********
**
********
****** **** **********
** ********
****** **** **********
******
** ********
**** **********
******
********
** **** **********
****
******
********
** **********
**
****
******
********
**********かわいい。
