ハノイの塔とは通常、以下のルールに従うゲームです。
- 棒が3本あり、そのうち1本に、互いにサイズの異なるいくつかの円盤が刺さっているところから始まる
- 1手で円盤を1個だけ動かすことができる
- 初期状態と最終状態を含め、ゲーム中のどの瞬間にも小さい円盤の上に大きい円盤が乗っていてはならない
- 初期状態と異なる棒にすべての円盤を移動させることができればゲームクリア
- ゲームクリアまでの手数をなるべく少なくすることが目的
この通常ルールの最短手数はよく知られており、円盤の数 n 枚に対して (2のn乗-1)手です。これについての解説は探せばいくらでも出てくるので省略します。
では、上記のルールの「棒が3本あり」を「棒が4本あり」に変えたらどうなるのか、というのが今回の問題です。
上 k 枚と下 n-k 枚に分けて動かすことを考えます。
つまり、最初にすべての円盤が棒Aにあったとして、「棒Cに上を移動」→「棒Bに下を移動」→「棒Bに上を移動」とすることで棒Bへの移動を完了させる、という方針です。
上 k 枚の移動は k 枚による棒4本ハノイの塔と見なせます。
一方、下 n-k 枚の移動は棒Cが塞がれているので、棒3本ハノイの塔の手数、すなわち (2の(n-k)乗-1) 手となります。
これら2つから得られる和を n 未満の k すべてに対し考えて導出し、その最小値を取ることで手数の上限(これだけ手数をかければ必ずクリアできる、という数値)が得られます。
棒3本円盤 n 枚のハノイの塔の手数を T_3(n) = 2 ** n - 1、棒4本円盤 n 枚のハノイの塔の手数を T_4(n) = 2 ** n - 1とすると
T_4(n)=min(2*T_4(k)+T_3(n-k)for k in range(n))
というわけです。
n が小さい場合は、一番乗りして好きに使える棒があるので、T_4(0)=0, T_4(1)=1, T_4(2)=3, T_4(3)=5まではすぐにわかります。これらをわざわざ再計算する必要はありません。
以上を踏まえた手数の上限を求めるコードがこちら。
from functools import cache
@cache
def T_4(n):return~-(max(1,2*n)*(n<4)or min(2*T_4(k)+2**(n-k)for k in range(n)))
本体は3行目です。3行目を素直に実行させると計算量がとんでもないことになるので、1,2行目で「1度計算した値をキャッシュとして保存しておき、2度目以降はキャッシュの値を読み出す」という宣言をしています。
実行例:
from functools import cache
@cache
def T_4(n):return~-(max(1,2*n)*(n<4)or min(2*T_4(k)+2**(n-k)for k in range(n)))
print([T_4(n)for n in[10,100,1000,10000]])
# [49, 172033, 932385860354049, 374931278650296101567069263458900577819295745]
なお、この「上限」は、かなり大雑把に求めたものです。
「上下に分けた後、上を動かしている間は決して下を動かしてはならない。逆も同様。」という、かなり強い制約を勝手に課しています。
最短手数であるという誤解はなさいませんよう。