ハノイの塔にチャレンジする

問題

今回はハノイの塔にチャレンジする。この問題は再帰を実装できれば解くことができるとのこと。ハノイの塔については、下記の動画を参考にしました。

• ハノイの塔は最短で何手かかるか？
• コーディングインタビュー解説！ハノイの塔を解き明かせ！
• Tower of Hanoi | GeeksforGeeks
• Towers of Hanoi: A Complete Recursive Visualization

実装

ディスクは3枚の状態で、今回も可視化してイメージをつけてみた。ディスクの動かし方を確認しつつ、再帰のイメージを掴むため。

これを実装するとこうなる。

def move(disk, src, sup, dest):
    if disk < 1:
        return

    move(disk-1, src = src, dest = sup, sup = dest)
    print(f'Disk {disk}: {src} → {dest}')
    move(disk-1, src = sup, dest = dest, sup = src)

if __name__ == '__main__':
    move(3, src='A', sup='B', dest='C')

Disk 1: A → C
Disk 2: A → B
Disk 1: C → B
Disk 3: A → C
Disk 1: B → A
Disk 2: B → C
Disk 1: A → C

まだまだイメージを実装できる力がないと実感。つまり、自分の理解がまだまだあやふやだからなんだろうな・・・。

実装2

もうちょっと図解してディスクの動きのイメージを持ってみる。左からディスクが2枚、3枚、4枚と増やしいるが、一番底のディスク以外をグループと考えると、AからCにディスクを移動させるのは全く動きが同じになる。また、ディスクが4枚のときの、底以外の動かし方は、ディスクが3枚のときの動かし方をすればよく、ディスクが3枚のときの、底以外の動かし方は、ディスクが2枚のときの動かし方をすればよいことになる。

ということは、「底のディスク以外をAからBに移動」「底のディスクをAからCに移動」「底のディスク以外をBからCに移動」という手順になるようにすればディスクをうまいこと動かせる。また、再帰で呼び出す際に数字を上手に減らせば、最初の実装よりも簡素化できそう。

def move(disk, x, y):
    if disk > 1:
        move(disk - 1, x, 6 - x - y)
    print(f'Disk {disk} from {x} to {y}')
    if disk > 1:
        move(disk - 1, 6 - x - y, x)


if __name__ == '__main__':
    move(disk = 3, x = 1, y = 3)

Disk 1 from 1 to 3
Disk 2 from 1 to 2
Disk 1 from 3 to 1
Disk 3 from 1 to 3
Disk 1 from 2 to 3
Disk 2 from 2 to 1
Disk 1 from 3 to 2

この実装の再帰のイメージは下記の通り。