# coding: utf-8
 
# ハノイの塔のパズルを解く関数。
# 3本の棒のリストを引数にとり、左端の棒から右端の棒へ最小手数ですべての円盤を
# 移してゆく過程を標準出力する。
# 円盤は整数で表し、棒の状態はリストで表す。
# 例えば [[1,2], [], []] は左端の棒に大きさ1と2の円盤2枚が積み上げられており、
# 中央と右端の棒は空いていることを表す。
def hanoi(rods):
    # 引数startが表す棒から、引数endが表す棒へ、円盤を1枚移す補助関数
    def transfer_a_disk(start, end):
        rods[end].insert(0, rods[start].pop(0))
 
    # 3本の棒にそれぞれ始点、中継点、終点の役割を与え、部分問題に
    # 分解する際に役割を入れ替えるところが要点
    def rec_hanoi(n, start, reray, end):
        if n == 1:
            transfer_a_disk(start, end)
            print rods
        else:
            rec_hanoi(n-1, start=start, reray=end, end=reray)
            transfer_a_disk(start, end)
            print rods
            rec_hanoi(n-1, start=reray, reray=start, end=end)
 
    # 初期状態の出力と部分問題への分解開始
    print rods
    rec_hanoi(len(rods[0]), start=0, reray=1, end=2)
 
 
 
# 左端の棒にn枚の円盤を積み上げた状態の、3本の棒のリストを返す
def create_testdata(n):
  return [range(1, n + 1), [], []]
 
 
 
# 実行
hanoi(create_testdata(1))
print
hanoi(create_testdata(2))
print
hanoi(create_testdata(3))
print
hanoi(create_testdata(4))
 

IyBjb2Rpbmc6IHV0Zi04CgojIOODj+ODjuOCpOOBruWhlOOBruODkeOCuuODq+OCkuino+OBj+mWouaVsOOAggojIDPmnKzjga7mo5Ljga7jg6rjgrnjg4jjgpLlvJXmlbDjgavjgajjgorjgIHlt6bnq6/jga7mo5LjgYvjgonlj7Pnq6/jga7mo5LjgbjmnIDlsI/miYvmlbDjgafjgZnjgbnjgabjga7lhobnm6TjgpIKIyDnp7vjgZfjgabjgobjgY/pgY7nqIvjgpLmqJnmupblh7rlipvjgZnjgovjgIIKIyDlhobnm6Tjga/mlbTmlbDjgafooajjgZfjgIHmo5Ljga7nirbmhYvjga/jg6rjgrnjg4jjgafooajjgZnjgIIKIyDkvovjgYjjgbAgW1sxLDJdLCBbXSwgW11dIOOBr+W3puerr+OBruajkuOBq+Wkp+OBjeOBlTHjgagy44Gu5YaG55ukMuaemuOBjOepjeOBv+S4iuOBkuOCieOCjOOBpuOBiuOCiuOAgQojIOS4reWkruOBqOWPs+err+OBruajkuOBr+epuuOBhOOBpuOBhOOCi+OBk+OBqOOCkuihqOOBmeOAggpkZWYgaGFub2kocm9kcyk6CiAgICAjIOW8leaVsHN0YXJ044GM6KGo44GZ5qOS44GL44KJ44CB5byV5pWwZW5k44GM6KGo44GZ5qOS44G444CB5YaG55uk44KSMeaemuenu+OBmeijnOWKqemWouaVsAogICAgZGVmIHRyYW5zZmVyX2FfZGlzayhzdGFydCwgZW5kKToKICAgICAgICByb2RzW2VuZF0uaW5zZXJ0KDAsIHJvZHNbc3RhcnRdLnBvcCgwKSkKCiAgICAjIDPmnKzjga7mo5LjgavjgZ3jgozjgZ7jgozlp4vngrnjgIHkuK3ntpnngrnjgIHntYLngrnjga7lvbnlibLjgpLkuI7jgYjjgIHpg6jliIbllY/poYzjgasKICAgICMg5YiG6Kej44GZ44KL6Zqb44Gr5b255Ymy44KS5YWl44KM5pu/44GI44KL44Go44GT44KN44GM6KaB54K5CiAgICBkZWYgcmVjX2hhbm9pKG4sIHN0YXJ0LCByZXJheSwgZW5kKToKICAgICAgICBpZiBuID09IDE6CiAgICAgICAgICAgIHRyYW5zZmVyX2FfZGlzayhzdGFydCwgZW5kKQogICAgICAgICAgICBwcmludCByb2RzCiAgICAgICAgZWxzZToKICAgICAgICAgICAgcmVjX2hhbm9pKG4tMSwgc3RhcnQ9c3RhcnQsIHJlcmF5PWVuZCwgZW5kPXJlcmF5KQogICAgICAgICAgICB0cmFuc2Zlcl9hX2Rpc2soc3RhcnQsIGVuZCkKICAgICAgICAgICAgcHJpbnQgcm9kcwogICAgICAgICAgICByZWNfaGFub2kobi0xLCBzdGFydD1yZXJheSwgcmVyYXk9c3RhcnQsIGVuZD1lbmQpCgogICAgIyDliJ3mnJ/nirbmhYvjga7lh7rlipvjgajpg6jliIbllY/poYzjgbjjga7liIbop6Pplovlp4sKICAgIHByaW50IHJvZHMKICAgIHJlY19oYW5vaShsZW4ocm9kc1swXSksIHN0YXJ0PTAsIHJlcmF5PTEsIGVuZD0yKQoKCgojIOW3puerr+OBruajkuOBq27mnprjga7lhobnm6TjgpLnqY3jgb/kuIrjgZLjgZ/nirbmhYvjga7jgIEz5pys44Gu5qOS44Gu44Oq44K544OI44KS6L+U44GZCmRlZiBjcmVhdGVfdGVzdGRhdGEobik6CiAgcmV0dXJuIFtyYW5nZSgxLCBuICsgMSksIFtdLCBbXV0KCgoKIyDlrp/ooYwKaGFub2koY3JlYXRlX3Rlc3RkYXRhKDEpKQpwcmludApoYW5vaShjcmVhdGVfdGVzdGRhdGEoMikpCnByaW50Cmhhbm9pKGNyZWF0ZV90ZXN0ZGF0YSgzKSkKcHJpbnQKaGFub2koY3JlYXRlX3Rlc3RkYXRhKDQpKQo=