用Python實現小遊戲 河內塔 可線上玩 Tower of Hanoi

Victor Freitas on Unsplash

河內塔的遊戲描述

有三個柱子A柱，B柱，C柱。

A柱上有 N 個穿孔圓盤，圓盤的尺寸由下到上依次變小。
要求按下列規則透過合法移動，將所有圓盤移至 C 柱：

1. 每次只能移動頂端的一個圓盤；
2. 大圓盤不能疊在小圓盤上面。

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開始玩)

https://bit.ly/4clCg1q

延伸思考:

如果對程式或者演算法有興趣的同學，
可以試著觀察圓盤的移動規律，想出演算法，寫個解題程式，
能夠用最少的步數，解開河內塔這個遊戲!

很有趣喔~