LoginSignup
6

More than 1 year has passed since last update.

posted at

updated at

k本のハノイの塔の動かし方(Python版)

本記事は、「データ構造とアルゴリズム Advent Calendar 2020」 1日目の記事です。
2日目の記事は @okateim 氏による「「4人のロシア人の方法」を用いた編集距離計算の高速化」です。

お題

「ハノイの塔」で塔の本数をk本に拡張せよ

参考:ハノイの塔 - Wikipedia

塔の数が3本のとき

ディスクの枚数をnとします。
塔が3本のときの最小手数は、$2^n - 1$であることがよく知られています。
また、そのときの動かし方は1通りに決まります。
この動かし方のコードは再起関数で次のように書けます。

def hanoi(n, pos):
    if n == 1:
        yield pos[0], pos[-1]
        return
    yield from hanoi(n - 1, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(1, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(n - 1, pos[1:-1] + [pos[0], pos[-1]])

コードの解説

hanoi(n, pos)は、「どの塔からどの塔に移動するか」を返すジェネレーター(forで使える関数)です。引数は以下の通りです。
- n:ディスクの枚数。
- pos:利用可能な塔のインデックスのリスト。このリストの先頭の塔のn枚のディスクを最後の塔に移動します。

4枚のディスクを塔0から塔2へ動かす方法は、下記のように書きます。

for i, j in hanoi(4, [0, 1, 2]):
    print(f'{i} -> {j}')

出力は以下のようになります(改行を変えてます)。

0 -> 1  0 -> 2  1 -> 2  0 -> 1  2 -> 0
2 -> 1  0 -> 1  0 -> 2  1 -> 2  1 -> 0
2 -> 0  1 -> 2  0 -> 1  0 -> 2  1 -> 2

ディスクが1枚のときは、「移動元、移動先」を返して終了します。

ディスクが2枚以上のときは、以下を実行します。

    yield from hanoi(n - 1, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(1, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(n - 1, pos[1:-1] + [pos[0], pos[-1]])

上記は、わかりにくいですが下記の処理です。

  • ステップ1)pos[0]からpos[1]n - 1枚移動
  • ステップ2)pos[0]からpos[-1]1枚移動
  • ステップ3)pos[1]からpos[-1]n - 1枚移動

簡単に説明します。
pos[0]にある最下段のディスクは、その上にあるn - 1枚のディスクをどかさないと移動できません。
そこで、ステップ1でn - 1枚どけます。ステップ2で最下段のディスクを動かし、ステップ3で残ったディスクを動かします。

塔の数がk本のときの方針

しばらく考えましたが、どうすればよいかわかりませんでした。
仕方がないので、考えやすいように下記を仮定することにしました。

命題

n枚をk本で動かしたいとき、以下の3ステップで最短手数で動かせる
- m枚を別の塔にどかす
- 下に残ったn - m枚を移動先に動かす
- 残りm枚を移動先に動かす

この命題は証明できていませんが、結果はうまくいっているようです。
mは、後で求めます。

最短手数

n枚をk本で動かすときの最短手数の数式はわかりませんでした。
しかし、動的最適化で以下のように計算できます。

from functools import lru_cache

@lru_cache(maxsize=1024)
def nmove(n, k):
    k = min(n + 1, k)
    if k == 2:
        return 1 if n == 1 else float("inf")
    elif k == 3:
        return 2 ** n - 1
    elif k == n + 1:
        return 2 * n - 1
    return min(nmove(i, k) * 2 + nmove(n - i, k - 1) for i in range(1, n))

解説

  • 塔の本数がn + 1を超えていても使わない塔がでてきます。そこで、塔の数は無駄がないようにk = min(n + 1, k)とします。これで無駄な計算が減ります。
  • k == 2のとき
    • ディスクが1枚なら1回で移動できます。
    • ディスクが2枚以上なら移動できません。移動回数として∞(float("inf"))を返します。
  • k == 3のときは、2 ** n - 1です。この処理はなくても動きますが、高速になります。
  • k == n + 1のときは、2 * n - 1です。これは各ディスクを空いている塔に退避すれば良いからです。
  • それ以外のときは、先ほどの命題を使ってしらみつぶしに調べます。

塔の数がk本のとき

命題を使えば以下のようになります。

def hanoi(n, pos):
    if n == 1:
        yield pos[0], pos[-1]
        return
    k = len(pos)
    m = min((nmove(i, k) * 2 + nmove(n - i, k - 1), i) for i in range(1, n))[1]
    yield from hanoi(m, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(n - m, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(m, pos[1:-1] + [pos[0], pos[-1]])

塔が3本のときにステップ1でn - 1本移動していたのが、m本の移動に変わっただけで、ほぼ同じコードになっています。
最短手数になるmも、nmoveを使えばしらみつぶしで求められます。

全コード

4枚のディスクを4本の塔で動かすコードは以下のようになります。

from functools import lru_cache

@lru_cache(maxsize=1024)
def nmove(n, k):
    k = min(n + 1, k)
    if k == 2:
        return 1 if n == 1 else float("inf")
    elif k == 3:
        return 2 ** n - 1
    elif k == n + 1:
        return 2 * n - 1
    return min(nmove(i, k) * 2 + nmove(n - i, k - 1) for i in range(1, n))

def hanoi(n, pos):
    if n == 1:
        yield pos[0], pos[-1]
        return
    k = len(pos)
    m = min((nmove(i, k) * 2 + nmove(n - i, k - 1), i) for i in range(1, n))[1]
    yield from hanoi(m, pos[:1] + pos[2:] + pos[1:2])
    yield from hanoi(n - m, pos[:1] + pos[2:-1] + pos[-1:])
    yield from hanoi(m, pos[1:-1] + [pos[0], pos[-1]])

for i, j in hanoi(4, [0, 1, 2, 3]):
    print(f'{i} -> {j}')

出力は以下のようになります(改行を変えてます)。

0 -> 1  0 -> 3  0 -> 2  3 -> 2  0 -> 3
2 -> 0  2 -> 3  0 -> 3  1 -> 3

可視化

塔の番号だけだとあっているかわかりにくいですね。
可視化しました。

$ pip install k-peg-hanoi
$ hanoi 4 4
   =
  ===
 =====
=======
0------------------------------

  ===
 =====
=======    =
1------------------------------

 =====
=======    =              ===
2------------------------------

=======    =     =====    ===
3------------------------------

                  ===
=======    =     =====
4------------------------------

                  ===
           =     =====  =======
5------------------------------

  ===      =     =====  =======
6------------------------------

                         =====
  ===      =            =======
7------------------------------

                          ===
                         =====
           =            =======
8------------------------------

                           =
                          ===
                         =====
                        =======
9------------------------------

最短手数の表

k\n 6 7 8 9 10
3 63 127 255 511 1023
4 17 25 33 41 49
5 15 19 23 27 31
6 13 17 21 25 29
7 11 15 19 23 27
8 11 13 17 21 25

以下で作成しました。

print("k\\n|6|7|8|9|10")
print(":--|:--|:--|:--|:--|:--|")
for k in range(3, 9):
    print(k, end='|')
    for n in range(6, 11):
        print(nmove(n, k), end='|')
    print()

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
6