河內塔的遊戲描述
有三個柱子A柱，B柱，C柱。
A柱上有 N 個穿孔圓盤，圓盤的尺寸由下到上依次變小。
要求按下列規則透過合法移動，將所有圓盤移至 C 柱：
- 每次只能移動頂端的一個圓盤；
- 大圓盤不能疊在小圓盤上面。
N=3的遊戲範例
場景:
使用者輸入一個層數n
電腦填充A柱，讓A柱填滿n~1的正整數，每個數字就對應到圓盤的大小。
接著讓使用者扮演玩家，每次可以移動一個柱子頂端的一個盤子到另一個柱子。
如果玩家最後成功把n個圓盤依序從大到小疊好，搬到終點的C柱，則玩家獲勝。
螢幕會秀出成功的提示訊息，並且顯示玩家花了幾步抵達終點。
上層思考邏輯與框架
讓使用者輸入層數n，接著讓電腦建立遊戲場景，填充A柱。
遊戲開始後，讓玩家自由選擇要從哪個柱子開始移動圓盤到另一個柱子。
移動的過程中，電腦會判斷玩家的操作是否合法(也就是大圓盤不可以疊在小圓盤之上)。
如果合法，就把對應的圓盤移動過去。
過程中會統計移動步數。
若玩家最後成功把n個圓盤依序從大到小疊好，搬到終點的C柱，則玩家獲勝。
螢幕會秀出成功的提示訊息，並且顯示玩家花了幾步抵達終點。
中層功能元件分析
1.怎麼接收使用者輸入?
python提供內建的input("提示訊息")的標準輸入function，
接收到的預設型別是字串。
接收層數時，記得要轉型成整數integer在儲存在變數n裡。
n = int( input("Please input level number of hanoi tower: ") )
接收移動圓盤的柱子時，直接接收字串即可。
src 代表要從哪個柱子拿起最上面的圓盤。
dest代表這個圓盤要放到哪個柱子。
src = input("Pick a tower to pick disk: ")
dest = input("Pick a tower to place disk: ")
2.怎麼建立遊戲場景，填充A柱?
遊戲場景總共有三個柱子A 柱, B柱, C柱，分別對應到三個堆疊。
# A柱, B柱, C柱
place = [ [], [], [] ]
# A柱對應到place[0]
# B柱對應到place[1]
# C柱對應到place[2]
mapping = {'A': 0, 'B': 1, 'C':2}
電腦根據n值，把A柱從下往上填滿n~1的正整數，
總個n個圓盤，數字的大小就代表圓盤的大小。
同時，會初始化步數為0。
之後步數會隨著玩家的操作而跟著累加上去。
def initialize(n, src):
# 起點柱填充正整數 n ~ 1 ，代表碟子的大小
place[ mapping[src] ] = [i for i in range(n, 0, -1) ]
# 初始化總步數 = 0
move_disk.step = 0
return
3.怎麼建立C柱的解答?
目標是把所有的圓盤搬到C柱，從下往上 由大到小疊好所有的圓盤。
終點C柱的解答其實也是從下往上疊滿n~1的正整數，
我們只要把A柱一開始的樣子複製一份，就可以當作最終C柱的解答。
final_state = place[ mapping['A'] ].copy()
4.如何建立循環(相當於程式語言中迴圈的邏輯)?
如果 還有C柱還沒和解答的樣子相等:
則繼續遊戲...
對應到python的程式碼，就是while 的迴圈與流程控制
while place[ mapping['C'] ] != final_state:
src = input("Pick a tower to pick disk: ")
dest = input("Pick a tower to place disk: ")
move_disk(src, dest)
showStatus()
5.怎麼移動圓盤到另一個柱子?
從使用者指定的src柱子移動到另一個dest柱子。
移動成功之後，步數step累加1
移動的時候，電腦會檢查是否為合法操作:
5-1.搬移的起點柱src不可以是空的。
5-2.大的圓盤不可以疊在小的圓盤之上。
def move_disk(src, dest):
# src柱不可以是空的
if not place[ mapping[src] ]:
print(f"Tower {src} is empty!")
return
# 大的圓盤不可以疊在小的圓盤之上。
if place[ mapping[dest] ] and ( place[ mapping[src] ][-1] > place[ mapping[dest] ][-1] ):
print(f"Cannot place larger disk over smaller disk!")
return
# update總步數
move_disk.step += 1
cur = place[ mapping[src] ].pop()
place[ mapping[dest] ].append( cur )
print(f"Step {move_disk.step}: Move disk {cur} from {src} to {dest}.")
return
6.怎麼顯示當前的遊戲狀態?
依序把A柱、B柱、C柱的狀態顯示在螢幕上即可。
def showStatus():
print(f"Status is shown as folloing.")
print(f"A: { place[0]} ")
print(f"B: { place[1]} ")
print(f"C: { place[2]} ")
print()
return
7.遊戲成功後，怎麼顯示玩家勝利的訊息?
當C柱的狀態等於解答，也就是玩家成功把n個圓盤從大到小疊好後，
輸出玩家獲勝的訊息，並寫顯示玩家總共用了幾步完成遊戲。
total_step = move_disk.step
print(f"Good job, you finish the game with {total_step} steps.")
return total_step
底層的完整實作: 小遊戲 河內塔 Tower of Hanoi
# A柱, B柱, C柱
place = [ [], [], [] ]
# A柱對應到place[0]
# B柱對應到place[1]
# C柱對應到place[2]
mapping = {'A': 0, 'B': 1, 'C':2}
def showStatus():
print(f"Status is shown as folloing.")
print(f"A: { place[0]} ")
print(f"B: { place[1]} ")
print(f"C: { place[2]} ")
print()
return
def move_disk(src, dest):
if not place[ mapping[src] ]:
print(f"Tower {src} is empty!")
return
if place[ mapping[dest] ] and ( place[ mapping[src] ][-1] > place[ mapping[dest] ][-1] ):
print(f"Cannot place larger disk over smaller disk!")
return
# update總步數
move_disk.step += 1
cur = place[ mapping[src] ].pop()
place[ mapping[dest] ].append( cur )
print(f"Step {move_disk.step}: Move disk {cur} from {src} to {dest}.")
return
def initialize(n, src):
# 起點柱填充正整數 n ~ 1 ，代表碟子的大小
place[ mapping[src] ] = [i for i in range(n, 0, -1) ]
# 初始化總步數 = 0
move_disk.step = 0
return
def play(n):
# 填滿起點A柱
initialize(n, src='A')
showStatus()
# 設定解答狀態
final_state = place[ mapping['A'] ].copy()
while place[ mapping['C'] ] != final_state:
src = input("Pick a tower to pick disk: ")
dest = input("Pick a tower to place disk: ")
move_disk(src, dest)
showStatus()
total_step = move_disk.step
print(f"Good job, you finish the game with {total_step} steps.")
return total_step
if __name__ == "__main__":
n = int( input("Please input level number of honoi tower: ") )
play(n)
試玩畫面
線上執行 與 試玩(在新的頁面按Run開始玩)
延伸思考:
如果對程式或者演算法有興趣的同學，
可以試著觀察圓盤的移動規律，想出演算法，寫個解題程式，
能夠用最少的步數，解開河內塔這個遊戲!
很有趣喔~
