ハノイの塔とひよこタワーで学ぶ再帰処理

この記事はmediba Advent Calendar 2024の12日目です。

株式会社medibaでバックエンドエンジニアをしているRetchといいます。
社内ではバリバリの本名なのでこっちの名前で呼ばれることはないです。
まあニックネームな人も社内に入るので我を通せばなんとかなると思います。

記事の対象者

再帰処理の初学者。以下の内容がスルッと理解できない人（自分はココ）。

記事のゴール

読み終わったらハノイの塔のパズルを手で解けるようになっている。コードが分かる。以上。

ハノイの塔とは

ハノイの塔はフランスの数学者エドゥアール・リュカ（Édouard Lucas）が1833年に考案した数学パズル。当時発売されたパッケージのパンフレットには以下のような伝説が語られています。

リュカの創作した伝説

• ベトナムの首都ハノイにある架空の寺院で、神聖な司祭たちが64枚の金の円盤を使って「ハノイの塔」を組み替える作業をしている
• 円盤は、3本の柱の間で「ハノイの塔のルール」に従って移動される
• 司祭たちが作業を完了し、すべての円盤が移動し終わると、世界が終末を迎える

終末怖い！となった人、安心してください。
たとえ本当でも後5000億年くらいかかるそうなんで。

ゲームの目的

• 最初の柱に積まれた円盤をすべて、指定された別の柱に移動させる

ハノイの塔のルール

1. 一度に1枚の円盤しか移動できない

2. 小さい円盤の上に大きい円盤を置くことはできない

3. 円盤は3本の柱のいずれかに移動することができる

コード

プログラムで手順を出力すると以下のようなコードになります。
さて、このプログラムの動作を全て頭でイメージできるでしょうか？
(記事後半でも再掲するので読み飛ばしてもらってもOK)

solve.py

N=int(input())
def move(level,from_,to_):
    if level==0: return []
    other = 6-from_-to_
    return move(level-1,from_ , other)+[[from_,to_]]+move(level-1, other, to_)

tejun=move(N,1,3)
for i in tejun:
    print(i[0],i[1])

出来なかった方、この記事を最後まで見ればイメージできるはずです。

ひよこタワー

突然ですが、ブラウザゲームでひよこタワーというものがあります。
絵柄こそ違えど内容は完全にハノイの塔です。
理論値で移動させることが出来れば最高評価でクリアできます。
この記事を読み終わったら是非一度プレイしてみてください。

ちなむと、このゲームの作者は言わずと知れた「寿司打」を作った方です。

再帰について

再帰とは、「大きな問題を小さな同じ問題に分割して解く手法」です。
まずはひよこタワーは2段だったことにして解いてみましょう。

ひよこタワーで実践

赤枠を一つの物体としてみたとき、ゴールに２段のタワーを建てることを考えます。

こうして

こうして

こう！

簡単ですね。

思考ロジック

まあ２段なら余裕で出来る。
そう思えたなら、再帰思考を理解すればハノイの塔はすでに解けたも同然です！

最初の思考

最下段(一番大きいひよこ)を動かすことを考えます。
最下段が動かせる状態は下のような状態以外ありません。

ココでの目的は一番右の巣に大きなひよこを移動することです。
そのため４段のひよこタワーを真ん中に建設する必要がありました。

ネクストステップ

では同様に4段目のひよこを移動するにはどういう状態が考えられるでしょうか？

赤枠を1段として考え、一番下の段なんて無いことにすれば先ほどと同じですね。

ふざけるな、当たり前だろとなった人。その通りです。もう一段思考が必要です。
ここでは真ん中に4段のタワーを作りたいという前提があります。
（最下段を右端に動かしたいので）

そのため赤枠の3段の塔を真ん中に置くことは出来ません。

すなわち3段の塔は右端に置きたい。

ココまで来るとだいぶ見えてきた人もいると思いますが、大事なのは動かしたい対象（青枠）の上にある塔（赤枠）を、動かしたい場所や自分がいる場所、とは別の場所に建てるということです。

再帰的に考える

現在分かっていること

• 5段目を右端に移動させたい
• 5段目を移動させるために真ん中に4段の塔を建てたい
• 真ん中に4段目のひよこを移動させたいので右端に3段の塔を建てたい

ここで、大事な事実としてN段の塔について、その一番下のひよこを移動させるとき、ひよこは必ず左にいます。（Nは任意の数）

そしてN段目の塔の土台を移動させるとき、必ずN-1段の塔が完成しています。（そうでないと土台を動かせないのは最初の2段だけの塔として考えてみるで言った通り）

つまり

3段の塔を右端作るとき、2段の塔が既に完成している。
そして3段の塔の一番下の土台となる3段目のひよこは左端にいる。
2段の塔が左端にあると土台のひよこが移動できない。
3段の塔は右端に作りたい。

これらをまとめると2段の塔は真ん中につくりたいことになる。
では1段の塔はどこに作りたいだろうか。

答え(ほぼ同じことの繰り返し)

2段の塔を右端作るとき、1段の塔が既に完成している。
そして2段の塔の一番下の土台となる2段目のひよこは左端にいる。
1段の塔が左端にあると土台のひよこが移動できない。
2段の塔は真ん中に作りたい。

これらをまとめると1段の塔は右端につくりたいことになる。

コード (再掲)

ここまでくれば関数の動きはともかく、何をしたいかは見えてくるのではないだろうか。

solve.py

N=int(input())
def move(level,from_,to_):
    if level==0: return []
    other = 6-from_-to_
    return move(level-1,from_ , other)+[[from_,to_]]+move(level-1, other, to_)

tejun=move(N,1,3)
for i in tejun:
    print(i[0],i[1])

move関数が何をしているのか

ハノイの塔を解くうえで理解すべき部分は以下の１文のみ！

return move(level-1,from_ , other)+[[from_,to_]]+move(level-1, other, to_)

move関数は

• タワーの高さ(level)
• 現在の位置(from_)
• 移動させたい位置(to_)

を引数に持ちます。

例えばタワーの高さ(level)=1のとき、答えは[from_, to_]のみとなります。

# 具体例：高さ1のハノイの塔を1から3の柱へ移動させる
move(1,1,3)
# 1 3 が出力される、これは1の柱から円盤を3の柱へ移すことを意味する

雑に言うと
まずこれをして、

move(level-1,from_ , other)

次にこれをして

[[from_,to_]]

最後にこれをする

move(level-1, other, to_)

ということです。

コード全体の流れ

まず、N-1の高さの塔をfromからotherに移す（ひよこタワーではN=5）

move(level-1,from_ , other)

最下段のひよこを目的の場所に移す。

[from_,to_]

N-1段のひよこを

move(level-1, other, to_)

これは最初にした2段の説明と変わりませんね。

再帰的な部分

関数を再度呼び出している部分を少し追ってみます。（最初に関数を呼んだときlevel=5とする）

# move(level, from_, to_)なので
# from_ = from_ (level=5のときのfrom_)
# other = to_   (level=5のときのto_)
# となる
move(level-1,from_ , other)

そして[from,to]をしたあとに、move(3,other,to_)すると4段を作れますね。

ここで説明は終わりとですが、再帰処理の雰囲気が掴めたらOK。

証明について

詳しい証明は調べれば分かるので割愛します。
数学的帰納法を用い、Kで成り立つと仮定し、K+1において以下の操作：

move(level-1, from_, other) + [[from_, to_]] + move(level-1, other, to_)

でかかる手数が成立することを示せば良いです。（K=level-1としたとき）

素晴らしいサイト

改めて参考にしたページなどを掲載しておきます。

おまけ

昔はPyPyの再帰が遅いみたいな話あったけど、最近は

import pypyjit
pypyjit.set_param('max_unroll_recursion=-1') # sys.setrecursionlimitは相変わらず必要

を使えばよくなったの嬉しい。
（使えるの知っただけなので、修正入ったのか最初からあったのかは知らない）

発言は個人の見解に基づくものであり、所属組織を代表するものではありません