k本のハノイの塔の動かし方（Python版） #Python

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

お題

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

塔の数が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()