惠燕，潘煜

（西安工業(yè)大學 計算機學院，陜西 西安 710032）

騎士游歷問題是一個古老而著名的問題，問題的描述是：在8×8格的國際象棋棋盤上，象棋馬能否從某個格子出發(fā)按照“馬跳日”的規(guī)則跳遍所有64個格子最后再回到出發(fā)的那個格子?國際象棋中的馬，英語為knight，恰好又意指中世紀西方世界的“騎士”，因此，這個問題又被稱為 “騎士游歷”問題。該問題即可以理解為國際象棋中的棋子在一個空棋盤內移動，問它能否經過六十四格并且只經過一次？騎士按“L”形路線移動，即在某方向前進兩格，接著在與原方向垂直的方向上前進一格。

1 騎士游歷問題模型的數(shù)學抽象

走的方向上相應的數(shù)據(jù)變化的確定[2-3]。

1.1 方向的研究

1.1.1 方向的分類

騎士游歷的規(guī)則確定了騎士游歷的方向。在國際象棋的棋盤里總共有8×8個格子，若使棋子“騎士”從任何一個格子開始，按照L形路線（在某方向前進兩格，接著在與原方向垂直的方向上前進一格）移動方法，游歷每一個格子，并且每個格子只允許被到達一次，則每次騎士可走的有8個方向的選擇。圖1是騎士將某一位置作為起始位置，繼續(xù)按照在某方向前進2格，接著在與原方向垂直的方向前進1格的方式即所謂L形路線可走的8個方向的示意圖。

騎士游歷問題最初是由大數(shù)學家歐拉（Euler）在1759年開始研究的。定義1：給定無孤立結點圖G，若存在一條路，經過圖中每邊一次且僅一次，該路稱為歐拉路；若存在一條回路，經過圖中每邊一次且僅一次，該回路稱為歐拉回路[1]。

騎士游歷問題因為它的典行性和可研究性，引來了國內外很多數(shù)學愛好者和程序設計者的注意。自從數(shù)學家提出這個問題以來，有很多人開始潛心研究。根據(jù)問題的描述可知求解騎士游歷問題的每一步就是馬在棋盤上走的每一步變化，而具體解決問題的關鍵在于騎士可走的8個方向以及可

圖1 騎士單次L形路線的方向示意圖Fig.1 Sketch map of knight single L-shaped route directions

圖1是按理論上騎士在某一個格子時可走的方向進行的說明。其包含2種情況：第1種如果騎士是按圖1所示的位置作為起始點進行遍歷的，該點則此時是本次遍歷的第一步，那么如圖所示的8個方向將都是可以走的；第2種如果圖示的這一點是騎士游歷過程中的某一點，那么這8個方向中就有可能有不可以走的格子，原因在于8個格子中有可能有以前遍歷時已經走過的格子。

1.1.2 方向的表示

根據(jù)騎士行走方向的規(guī)則，可以借助于直角坐標系對騎士可走的8個方向如何表示進行說明。假設騎士此時在棋盤圖形界面的位置為（x，y），那么8個可能走的方向的位置可分別表示為：1）（x+2，y-1）；2）（x+1，y-2）；3）（x-1，y-2）；4）（x-2，y-1）；5）（x-2，y+1）；6）（x-1，y+2）；7）（x+1，y+2）；8）（x+2，y+1）。 這 8 個點是按照順時針的方向依次變化的，如圖2所示。通過序偶的表示方式，圖2借用直角坐標系把騎士可走的8個方向進行了表示。在每一個序偶中x和y所加減的數(shù)表示的是騎士所在的格子和它可到達的格子的中心距。

圖2 騎士可走方向的坐標表示Fig.2 Coordinate representations of knight’s direction

1.2 可達數(shù)的研究

每個格子的可到達數(shù)的初始情況如圖3所示，圖中每個小格子中的數(shù)字代表騎士在相應的格子中可以走的方向數(shù)?？梢钥闯?，即使把棋子控制在棋盤內部，騎士在任意一個格子中的走法也都不唯一。走法最少的是4個角上的4個格子，為兩種走法。雖然每個格子的走法都不唯一，但是必須為每一個格子選擇唯一的一條路徑來實現(xiàn)騎士的游歷，這是需要通過算法來實現(xiàn)的。那么如何在不唯一的路徑中選擇一條路徑來進行游歷呢？假使騎士從其中一個格子走到了可到達的一個格子，那么根據(jù)題目的要求，騎士就不可以再次到達這2個格子中的任意1個。也就是說它們周圍的某些格子騎士可走的方向數(shù)要相應地減一。因此可以根據(jù)下面兩點來擬定改變每個格子可到達數(shù)的方式：1）每個格子只能被騎士到達一次；2）任意一個終點都可以根據(jù)一定的路徑返回到起點；具體操作時任意一個作為或曾經作為起點的格子的可到達數(shù)都置為0，因為它將不可再被到達，也就不可能再到達其他格子；任意一個作為或曾經作為終點卻始終未被到達的格子的可到達數(shù)均減一，因為它們的起點就是它們作為起點時的終點之一，而此時這個起點已被到達并且不可再被到達，所以它們的路徑數(shù)也就是可到達數(shù)相應地減少了一個。

圖3 棋盤中每個格子的初始可到達數(shù)Fig.3 Initial reached number of each grid

2 基于JAVA的算法設計與實現(xiàn)

隨著計算機技術的不斷發(fā)展，人們一直在探索著自然語言和計算機語言之間的映射問題。著名數(shù)學家歐拉在沒有計算機的時代解決了這個問題，找到了一種解答。而在計算機技術發(fā)達的今天，也可以借助程序設計來實現(xiàn)該問題的解答。騎士游歷就是一個有信息的圖搜索的過程。

要將騎士游歷問題程序化，關鍵是要能設計出馬在棋盤上走的每一步的算法。因為在每一步騎士還需要選擇一個方向進行游歷，所以算法設計中需要從騎士在每個格子中可能走的方向及騎士在每個格子中的可到達數(shù)兩個方面進行設計，即當前步的行列位置和當前步已經試探過的方向，將騎士的空間移動抽象成數(shù)學方式，進而可以映射到Java程序中用對應的數(shù)據(jù)結構來實現(xiàn)[4-6]。所以使用兩個數(shù)組，它先把8個可能走的方向用兩個數(shù)組表示出來，這兩個數(shù)組分別是：horizontal[]={2，1，-1，-2，-2，-1，1，2}；vertical[]={-1，-2，-2，-1，1，2，2，1}；它們分別表示水平方向和垂直方向即騎士所走L形狀所需的x坐標和y坐標的變化量。通過這兩個數(shù)組可以記住棋盤的每個位置是在騎士的第幾步到達的，這反映了問題的解，即第幾步到哪個位置。數(shù)組direction direction[x][y]記住在棋盤的某個位置已經試探過的方向，每個位置有8個方向，可按某種順序對8個方向編號，然后在每個位置按編號順序試探方向。在確定數(shù)據(jù)結構之后，可得騎士游歷程序算法流程圖，如圖4所示。

AccessibleSquare類主要是算法實現(xiàn)類，其中騎士對8個方向的游歷的主要代碼如下：

public AccessibleSquares（int x ， int y ）{

圖4 騎士游歷程序算法流程圖Fig.4 Flow chart of knight travel program algorithm

……

for（int i=0； i＜ horizontal.length； i++）

{textXPos=x+horizontal[i]；

textYPos=y+vertical[i]；

if（（textXPos＞=0） & （textXPos＜=8） &textYPos＞=0）& （textYPos＜=8））

xpos[arraxpos]=textXPos；

ypos[arraypos]=textYPos；

accessibility[arraypos]=KnightsTour.access[textXPos][textYPos]；

if（accessibility[arraypos]＞ 0）

arraypos++；

……}

在這個類中運用了排序法，鑒于本程序中的數(shù)組不是很大和冒泡排序法容易編程的特點，程序選擇了冒泡排序法，但是算法開銷較大還有待以后改進。

3 結束語

在研究騎士旅游的基礎上，愛爾蘭數(shù)學家漢密爾頓（Hamilton）于1862年將其一般化提出：是否能在有 n個節(jié)點的圖上，找出一條通路，經過每個節(jié)點一次，并且只能一次，即漢密爾頓回路，無論是騎士旅游問題還是漢密爾頓回路問題的研究對電路圖的設計及圖像加密等方面都有極大的幫助。

[1]左孝凌，李為鑑，劉永才.離散數(shù)學[M].上海：上?？茖W技術文獻出版社，2003.

[2]寧宣熙，Angelika N.廣義象棋盤中的馬步哈密頓圈問題及其實證研究[J].南京航空航天大學學報，2004，36（3）：383-387.NING Xuan-xi，Angelika N.Research on knight’s circuit problem in generalized chessboards and their solutions[J].Journal of Nanjing University of Aeronautics and Astronautics，2004，36（3）：383-387.

[3]柏森，楊曉帆，瞿曉鴻，等.關于騎士旅游問題的幾個定理[J].重慶大學學報，1998，21（3）： 32-38.BAI Sen，YANG Xiao-fan， QU Xiao-hong，et al.Several Theorems about knight-tour Problem[J].Journal of Chongqing University， 1998，21（3）： 32-38.

[4]葉核亞.數(shù)據(jù)結構 （Java版）[M].北京：電子工業(yè)出版社，2004.

[5]Eckel B.Java編程思想[M].4版.北京：機械工業(yè)出版社，2007.

[6]張居敏，石禮娟，龍翔.Java程序設計經典教程（融合上機操作實例）[M].北京：電子工業(yè)出版社，2008.

[7]李秀娟,田川,馮欣.數(shù)據(jù)挖掘分類技術研究與分析[J].現(xiàn)代電子技術，2010（20）:86-88.LI Xiu-juan,TIAN Chuan，F(xiàn)ENG Xin.Research on Classification Technology in Data Mining[J].Modern Electronics Technique,2010（20）:86-88.