[Pythonプログラミング]ハノイの塔を解くプログラム : 乙Py先生のプログラミング教室

今回はハノイの塔を解くプログラムについてです。

解説動画はこちら

ハノイの塔（Tower of Hanoi)とは

古来からあるパズルゲーム

以下のルールに従って
すべての円盤を右端の杭に移動させられれば完成です。

・3本の杭と、大きさの異なる複数の円盤から構成

・初期配置は左端の杭に昇順で積み重ねられている

・1回に1枚ずつ移動させるられるが
　小さいものの上に大きな円盤を乗せることはできない

ハノイの塔は
「再帰的な方法」で解くことができる古典的な問題です。

ディスクの数 n、出発点の棒 source
目的地の棒 target、および補助の棒 auxiliaryとします。

基底条件として、ディスクが1枚だけの場合は
sourceからtargetに直接移動

それ以外の場合は、再帰的に以下のステップを実行：

n-1枚のディスクをsourceからauxiliaryに移動

残りの1枚のディスクをsourceからtargetに移動

n-1枚のディスクをauxiliaryからtargetに移動

配置するディスクの数 n を変更することで
他のケースも同様に解くことができます。

ハノイの塔を解くコード

# ハノイの塔を攻略
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"{n}を{source}から{target}に移動")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"{n}を{source}から{target}に移動")
    hanoi(n-1, auxiliary, target, source)

n = 3
hanoi(n, 'A', 'C', 'B')

1をAからCに移動

2をAからBに移動

1をCからBに移動

3をAからCに移動

1をBからAに移動

2をBからCに移動

1をAからCに移動

ハノイの塔を描画するコード

widgetsを使ってstepごとの画像を描画しています。

# ハノイの塔を描画する
import ipywidgets as widgets
import matplotlib.pyplot as plt
import numpy as np

data,img_data = [],[]

# ディスクの色リスト
colors = ['red', 'green', 'blue', 'purple', 'yellow', 'silver', 'orange', 'pink']

# 棒の位置
positions = {'A': 0, 'B': 1, 'C': 2}

# ハノイの塔を攻略
def hanoi(n, source, target, auxiliary):
    if n == 1:
        data.append([n,source,target])
        return
    hanoi(n-1, source, auxiliary, target)
    data.append([n,source,target])
    hanoi(n-1, auxiliary, target, source)

# ディスクを描画するための関数
def draw_towers(state, step):
    fig, ax = plt.subplots()
    ax.set_xlim(-1, 3)
    ax.set_ylim(0, 5)
    ax.set_xticks([0, 1, 2])
    ax.set_xticklabels(['A', 'B', 'C'])
    ax.set_yticks([])
    for tower in 'ABC':
        for j, disk in enumerate(state[tower]):
            color = colors[disk - 1]
            width = 0.2 * disk
            height = 0.5
            ax.bar(positions[tower], height, bottom=j * height, width=width, color=color, edgecolor='black')
    ax.set_title(f'Step {step}')
    fig.canvas.draw()
    img_data.append(np.array(fig.canvas.renderer.buffer_rgba()))
    plt.close(fig)

# 初期状態
n = 4  # ディスクの数
hanoi(n, 'A', 'C', 'B')
towers = {'A': list(range(n, 0, -1)), 'B': [], 'C': []}
draw_towers(towers, 0)

# 各ステップごとに状態を描画
for step, (disk, source, target) in enumerate(data):
    towers[target].append(towers[source].pop())
    draw_towers(towers, step+1)

# img_data に保存された画像を表示するためのウィジェット
def show_image(step):
    plt.imshow(img_data[step])
    plt.axis('off')
    plt.show()

slider = widgets.IntSlider(value=0, min=0, max=len(img_data)-1, step=1, description='Step:')
widgets.interactive(show_image, step=slider)