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

本記事は、「[データ構造とアルゴリズム Advent Calendar 2020](https://qiita.com/advent-calendar/2020/str)」 1日目の記事です。
2日目の記事は @okateim 氏による「[「4人のロシア人の方法」を用いた編集距離計算の高速化](https://qiita.com/okateim/items/a1b0523c1c862009e81f)」です。

## お題

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

参考：[ハノイの塔 - Wikipedia](https://ja.wikipedia.org/wiki/ハノイの塔)

## 塔の数が3本のとき

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

```py
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へ動かす方法は、下記のように書きます。

```py
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枚以上のときは、以下を実行します。

```py
    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本で動かすときの最短手数の数式はわかりませんでした。
しかし、動的最適化で以下のように計算できます。

```py
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本のとき

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

```py
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本の塔で動かすコードは以下のようになります。

```py
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
```

## 可視化

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

```bash
$ 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|

以下で作成しました。

```py
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()
```