正在加載......


象棋專欄:棋盤上的數學遊戲-騎士旅遊(Knight's Tour)    首頁 > 象棋專欄


棋盤上的數學遊戲-騎士旅遊(Knight's Tour)

本會專任教師 黃偉倫老師 

一隻馬能否跳遍空棋盤上的每一個交叉點?答案是肯定的,稍具象棋知識的人,都能準確回答這個問題。但是若進一步要求:是否能找到一條路徑,讓馬跳遍空棋盤上所有交叉點的過程中,任意一個交叉點只允許被馬踩過一次?後面這個問題,恐怕要難倒許多人了。

這個古老難題,在西方稱之為「騎士旅遊(Knight's Tour)」,早在十六世紀時,瑞士數學家貝爾特蘭德(Bertrand)即提出這個問題。著名的大數學家歐拉(Euler)在1759年開始研究它,並獲得了一般解法。在研究騎士旅遊的基礎上,由愛爾蘭數學家哈密爾頓(Hamilton)於1862年將其一般化提出:是否能在有n個節點的圖上,找出一條通路,經過每個節點一次,並且只能一次。時至今日,哈密爾頓的這個難題(屬於「圖論」的領域)仍未完全解開。

底下我們借用一張空的半盤象棋棋盤(9 × 5大小),來做一趟騎士旅遊吧!

只要掌握簡單的基本原理,看似非常困難的題目,

你(妳)將可以輕輕鬆鬆在5分鐘之內解開!

參考作法:

 

步驟1:按圖示把棋盤劃分為兩個區塊:右邊為5 × 5的正方形、

左邊為4 × 5的長方形。

 

 

步驟2:先填右邊的正方形。在右上角交叉點寫上數字1,然後按

馬步前進到數字2,緊接著是數字3…,過程中盡量按照

時針的方向前進,並且優先選擇能夠跳到角落的走法。

右側完成圖如下。

步驟3:重複步驟2,但是改填左邊的長方形。左側完成圖如下。

 

 

步驟4:現在相當於棋盤上有兩條錯綜複雜的〝繩子〞,我們所需要

做的是,找出這兩條〝繩子〞的連接處

 

請見下圖說明,綠15接到橘1,橘20接回綠16。

於是我們的答案就呼之欲出了。

 

綠1 → 綠2 → 綠3 → …… → 綠15橘1 → 橘2 →

橘3 → …… → 橘20 → 綠16 → …… → 綠25

 

完成稿:下圖是半張空白象棋棋盤的騎士旅遊解答之一。有興趣的人

可以接著挑戰全盤空白棋盤(9 × 10)的騎士旅遊。

  中華民國象棋文化協會 電話:02-2365-6585 傳真:02-2365-5787 
地址:10646臺北市大安區羅斯福路二段91號4樓之1 (古亭捷運站3號出口直走步行約1-2分鐘)

版權所有2015中華民國象棋文化協會 All Rights Reserved.