主頁棋人棋事.騎士觀光


原作:Frederic Friedel
略有刪改

你有沒有想過,馬在六十四格,能從一格出發而走遍所有格,每個格子只落腳一次,是有沒有可能的呢?西方人把這個問題稱為「騎士觀光」(The Knight's Tour)。

這個問題老早已被人解決了,不過答案卻多得驚人。最早的答案見於九世紀的一份阿拉伯資料中。作者提供的兩個答案,都出自兩個 Shatranj 玩家 Mani 和  al-Adli,而 Shatranj 是西洋棋的雛型:

兩人都注意到,馬可以在十六格中完成騎士觀光:左方先剷除外框的四十八格,再跳入中心,而右方就把棋盤分為四個十六格,然後逐一完成。

後來,一位 Shatranj 高手根據  al-Adli 的圖創出了「閉路走法」:馬可以踏遍棋盤之餘回到起點格。如圖:

兩個圖都很有美感,左圖呈軸向對稱,右圖呈四角對稱。

一七九五年,德國數學家歐拉(Euler)首位正式研究這謎題,並把成果呈給柏林科學研究院。 研究所曾說過提供獎金四千法郎,給能夠寫出最好的騎士觀光的研究的人,但歐拉始終沒有被獎,可能是因為當時歐拉已經是柏林數學研究院院長,認為獎給他並不恰當。以下是歐拉的一些成果:

到底有多少答案呢?就算是今天最快的電腦,也不可一下子算出來。一九九五年 Martin Löbbing 和 Ingo Wegener 聲稱運用二十個 Sun 工作室,用了四個月的時間,得出了 33,439,123,484,294。九七年,Brendan McKay 用另一個方法(把棋盤分為兩半),得出 13,267,364,410,532。假如電腦一分鐘算出一萬個答案,那起碼要二十五年才可以算出 McKay 的答案。

除了「閉路走法」,還有甚麼答案?如何得出?我們可以借用幻方

如果把馬的路線以數字表達,那些數字就會組成一個半幻方。在一個半幻方中,數字不無論直橫中加起來也是相等。後來證實,沒有一種騎士觀光可以組成一個完整的幻方,即連斜線加起來也相等。在單數乘單數的方格內,全幻方騎士觀光也是不可能的,但在 4kx4k 的圖版上卻可以,如果 k>2。



騎士觀光是由一個半幻方組成--直橫加起來一樣,但斜線的話就不是(見左圖)。把兩個半騎士觀光合起來,會得到一個幻方,可是卻不能完成騎士觀光--第三十二和三十三格不能連絡。這裡列舉了全部已知的騎士觀光。

這真是很困難啊!有沒有更易的方法?有!

一八三二年,H. C. Warnsdorff 提出了一種更實用易明的方法,它的主旨就是要避開絕路。為了避開絕路,在每走一步前都要檢查下一步所可能到達的格子,方法是 :統計每個下一步可能到達的格子,它本身有多少條符合規定的可選路線。把這個數字標記在相應每個格子內。然後,就跳到數字最小的那個格子;如果全部格子數字相同,就隨便到一個。如圖:

如上述,下一步應跳到 c8,因為它只有三個可能走法。

這裡,來親自玩玩騎士觀光!

 

回最上

Hosted by www.Geocities.ws

1