ハノイの塔 - 再帰・非再帰（Python編）

ルール

以下ハノイの塔 - Wikipediaより

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

1. 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
2. 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
3. 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

考え方

• 各円盤の杭を回る方向が交互になる
• 再帰コードは、ある局面における3つの円盤（n, n-1, n-2）の動きを繰り返す処理
• 非再帰コードは、円盤の移動方向が交互になる特徴を利用して、円盤の移動可否を判定しながら移動を繰り返す処理
• 移動回数は2^n - 1

再帰コード

# coding: utf-8

def hanoi(disk_number, f, t, w, tower_dict):

    if disk_number > 0:
        hanoi(disk_number-1, f, w, t, tower_dict)
        tower_dict[t].insert(0, tower_dict[f].pop(0))
        print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
        hanoi(disk_number-1, w, t, f, tower_dict)


if __name__ == '__main__':
    disk_number = int(input())
    tower_dict = {'left': [i for i in range(1, disk_number+1)], 'center': [], 'right': []}
    print((tower_dict['left'], tower_dict['center'], tower_dict['right']))
    hanoi(disk_number, 'left', 'right', 'center', tower_dict)

非再帰コード

def hanoi(tower_list, pile_list, disk_number):
    cnt = 0
    passed_list = [tower_list[:]]

    while True:

        for disk in range(1, disk_number+1):

            # 今の円盤が杭の一番上になければ次の円盤に移動
            if tower_list.index(tower_list[disk-1]) != disk-1:
                continue

            idx = pile_list.index(tower_list[disk-1])

            # 右回り（left -> center -> right -> left ...の順で回る）
            if (disk_number % 2 == 0 and disk % 2 == 1) or (disk_number % 2 == 1 and disk % 2 == 0) :

                if idx+1 >= len(pile_list):
                    idx = -1

                if pile_list[idx+1] not in tower_list or tower_list.index(pile_list[idx+1]) > disk-1:
                    tower_list[disk-1] = pile_list[idx+1]
                    passed_list.append(tower_list[:])
                    cnt += 1


            # 左回り（left -> right -> center -> left ...の順で回る）
            else:

                if 0 >= idx:
                    idx = len(pile_list)

                if pile_list[idx-1] not in tower_list or tower_list.index(pile_list[idx-1]) > disk-1:
                    tower_list[disk-1] = pile_list[idx-1]
                    passed_list.append(tower_list[:])
                    cnt += 1

            if tower_list == ['r'] * disk_number:
                return cnt, passed_list

if __name__ == '__main__':
    disk_number = int(input())
    pile_list = ['l', 'c', 'r']
    tower_list = ['l'] * (disk_number)

    cnt, passed_list = hanoi(tower_list, pile_list, disk_number)

    print(passed_list)

おまけ（非再帰のテストコード）

# coding: utf-8

import unittest


class HanoiTest(unittest.TestCase):

    def setUp(self):
        self.pile_list = ['l', 'c', 'r']

    def test_first(self):
        disk_number = 3
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l'],
            ['r', 'l', 'l'],
            ['r', 'c', 'l'],
            ['c', 'c', 'l'],
            ['c', 'c', 'r'],
            ['l', 'c', 'r'],
            ['l', 'r', 'r'],
            ['r', 'r', 'r']
        ])

    def test_second(self):
        disk_number = 4
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l', 'l'],
            ['c', 'l', 'l', 'l'],
            ['c', 'r', 'l', 'l'],
            ['r', 'r', 'l', 'l'],
            ['r', 'r', 'c', 'l'],
            ['l', 'r', 'c', 'l'],
            ['l', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'r'],
            ['r', 'c', 'c', 'r'],
            ['r', 'l', 'c', 'r'],
            ['l', 'l', 'c', 'r'],
            ['l', 'l', 'r', 'r'],
            ['c', 'l', 'r', 'r'],
            ['c', 'r', 'r', 'r'],
            ['r', 'r', 'r', 'r']
        ])

    def test_third(self):
        disk_number = 5
        tower_list = ['l'] * (disk_number)
        cnt, passed_list = hanoi(tower_list, self.pile_list, disk_number)
        self.assertEqual(cnt, 2 ** disk_number - 1)
        self.assertEqual(passed_list, [
            ['l', 'l', 'l', 'l', 'l'],
            ['r', 'l', 'l', 'l', 'l'],
            ['r', 'c', 'l', 'l', 'l'],
            ['c', 'c', 'l', 'l', 'l'],
            ['c', 'c', 'r', 'l', 'l'],
            ['l', 'c', 'r', 'l', 'l'],
            ['l', 'r', 'r', 'l', 'l'],
            ['r', 'r', 'r', 'l', 'l'],
            ['r', 'r', 'r', 'c', 'l'],
            ['c', 'r', 'r', 'c', 'l'],
            ['c', 'l', 'r', 'c', 'l'],
            ['l', 'l', 'r', 'c', 'l'],
            ['l', 'l', 'c', 'c', 'l'],
            ['r', 'l', 'c', 'c', 'l'],
            ['r', 'c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'c', 'l'],
            ['c', 'c', 'c', 'c', 'r'],
            ['l', 'c', 'c', 'c', 'r'],
            ['l', 'r', 'c', 'c', 'r'],
            ['r', 'r', 'c', 'c', 'r'],
            ['r', 'r', 'l', 'c', 'r'],
            ['c', 'r', 'l', 'c', 'r'],
            ['c', 'l', 'l', 'c', 'r'],
            ['l', 'l', 'l', 'c', 'r'],
            ['l', 'l', 'l', 'r', 'r'],
            ['r', 'l', 'l', 'r', 'r'],
            ['r', 'c', 'l', 'r', 'r'],
            ['c', 'c', 'l', 'r', 'r'],
            ['c', 'c', 'r', 'r', 'r'],
            ['l', 'c', 'r', 'r', 'r'],
            ['l', 'r', 'r', 'r', 'r'],
            ['r', 'r', 'r', 'r', 'r']
        ])

参考

ハノイの塔 - Wikipedia
ハノイの塔を攻略せよ
ハノイの塔を再帰で解く