含空洞的馬步型哈密頓圈探索

楊克昌,劉志輝

(1.湖南理工學(xué)院 計(jì)算機(jī)學(xué)院,湖南 岳陽(yáng) 414006;2.湖南電視臺(tái),長(zhǎng)沙 410000)

含空洞的馬步型哈密頓圈探索

楊克昌1,劉志輝2

(1.湖南理工學(xué)院 計(jì)算機(jī)學(xué)院,湖南 岳陽(yáng) 414006;2.湖南電視臺(tái),長(zhǎng)沙 410000)

通過(guò)搜索某些特殊的較小馬步遍歷,將其按照一元旋轉(zhuǎn)與二元支撐兩種組合模型構(gòu)建成含空洞的馬步型哈密頓圈,拓廣了哈密頓圈圖論課題的研究范圍.

馬步哈密頓圈;空洞;組合;遞歸;回溯

引言——馬步遍歷與哈密頓圈

馬步遍歷與馬步型哈密頓圈是一個(gè)集趣味性與學(xué)術(shù)性于一身的組合圖論問(wèn)題.

在給定的方格棋盤(pán)中,馬從棋盤(pán)的某一格出發(fā),按馬走“日”的規(guī)則經(jīng)過(guò)棋盤(pán)中的每一個(gè)方格恰一次,該問(wèn)題稱為馬步遍歷問(wèn)題,經(jīng)過(guò)棋盤(pán)的每一個(gè)方格恰一次的線路稱為馬步遍歷路徑.

馬步遍歷中若終點(diǎn)能與始點(diǎn)相銜接,即遍歷路徑的終點(diǎn)與始點(diǎn)也能形成一個(gè)“日”形關(guān)系,該遍歷路徑為一馬步封閉圈,稱為騎士巡游圈,或稱馬步型哈密頓圈,以下簡(jiǎn)稱哈密頓圈.

本文探討含空洞的哈密頓圈,即探索在方格棋盤(pán)中含有一個(gè)馬步不能踏入的空洞區(qū)域的哈密頓圈.這顯然是一個(gè)比尋求一般意義上的馬步遍歷或哈密頓圈更具挑戰(zhàn)性的課題.

如果棋盤(pán)中的空洞只是某一單個(gè)空格,只需在搜索哈密頓圈的程序中加入“障礙空格”的條件限制即可.當(dāng)棋盤(pán)中的空洞為一片空格區(qū)域時(shí),因?yàn)榇藭r(shí)棋盤(pán)參數(shù)必然比較大,同時(shí)空洞限制比較復(fù)雜,應(yīng)用常規(guī)回溯或遞歸設(shè)計(jì)來(lái)探索很難切入.本文給出兩個(gè)組合模型實(shí)施構(gòu)建,即通過(guò)搜索棋盤(pán)參數(shù)較小的始點(diǎn)與終點(diǎn)滿足某些特殊要求的馬步遍歷,用這些遍歷按給定的組合模型構(gòu)建成含空洞的哈密頓圈.

1 一元旋轉(zhuǎn)模型構(gòu)建

一元旋轉(zhuǎn)組合模型,即只一個(gè)特殊的馬步遍歷通過(guò)旋轉(zhuǎn)組合成含空洞的哈密頓圈.

1.1 一元旋轉(zhuǎn)組合模型

設(shè)一元旋轉(zhuǎn)組合模型的組合元素為n行m列的遍歷A,按如圖1所示的旋轉(zhuǎn)模式實(shí)施組合:遍歷A作為基礎(chǔ)橫放在棋盤(pán)下部,棋盤(pán)左邊模塊為組合元素A逆時(shí)針旋轉(zhuǎn)270°后列倒置而成,右邊的模塊為組合元素A逆時(shí)針旋轉(zhuǎn)90°后列倒置而成,橫放棋盤(pán)上部的為A遍歷旋轉(zhuǎn)180°所得.

圖1 一元旋轉(zhuǎn)組合模式

按如圖1所示的一元旋轉(zhuǎn)組合模式,遍歷A的始點(diǎn)與終點(diǎn)定為(1,1)與(2,m?1),注意到終點(diǎn)(2,m?1)既可與下一個(gè)同向遍歷的始點(diǎn)(1,1)相銜接,也可以與逆時(shí)針旋轉(zhuǎn) 90°后列倒置遍歷始點(diǎn)(1,1)相銜接,因而組合可以進(jìn)行橫豎兩個(gè)方向的任意擴(kuò)展.

設(shè)棋盤(pán)的上下部各設(shè)置wh個(gè)遍歷,左右部各設(shè)置wv個(gè)遍歷,則所得含空洞的哈密頓圈共走2(wv+wh)mn步,棋盤(pán)為 (2n+wvm)×whm,中央所含空洞為wvm× (whm-2n).

注意到whm≤2n時(shí)組合時(shí)無(wú)空洞,而當(dāng)n＜ 3時(shí)無(wú)遍歷,顯然要求whm＞ 2n≥6.

1.2 探索遍歷回溯設(shè)計(jì)

應(yīng)用回溯設(shè)計(jì)探索在nm廣義棋盤(pán)中指定始點(diǎn)為(1,1)、終點(diǎn)為(2,m?1)的馬步遍歷.

設(shè)置數(shù)組x(i),y(i)記錄遍歷中第i步的行列位置,二維數(shù)組d(u,v)記錄棋盤(pán)中位置 (u,v)即第u行第v列所在格的步數(shù)值.

例如第 9步走在棋盤(pán)的(3,2)格,則x(9)= 3,y(9)= 2;d(3,2)= 9.若d(i,j)= 0,表示棋盤(pán)中的 (i,j)格為空,可以走位.

注意到馬走“日”形最多可走8個(gè)方向,圖2所示當(dāng)馬處在(x,y)時(shí)可選的8個(gè)方向.

圖2 馬步可走的8個(gè)位置

設(shè)置控制馬步規(guī)則的數(shù)組a(k)、b(k),若馬的當(dāng)前位置為(x,y),馬步可跳的8個(gè)位置為(x+a(k),y+b(k)),k= 1,2,… ,8.其中

在回溯過(guò)程中,需知第i步到第i+ 1步原已選取到哪一個(gè)方向,設(shè)置t(i)記錄第i步到第i+1步已選取的方向數(shù),回溯時(shí)只要從t(i)+1～8選取方向即可.

回溯從i= 1開(kāi)始進(jìn)入條件循環(huán),條件循環(huán)的條件為i＞0.當(dāng)i＞0時(shí)還未完成回溯,可試探走馬.

設(shè)置k(t(i)+1～8)循環(huán)依次選取方向,并求出此方向的走馬位置:u=x(i)+a(k),v=y(i)+b(k).

判斷:若1 ≤u≤n, 1≤v≤m,d(u,v)= 0,即所選位置在棋盤(pán)中且該位為空,可走馬步d(u,v)=i+ 1;同時(shí)記錄下此時(shí)的方向t(i)=k,q=1標(biāo)志此步走馬成功,退出選方向循環(huán).

第i步走馬成功后,檢測(cè)若i=mn- 1,且滿足終點(diǎn)條件(u= 2,v=m- 1),標(biāo)志已搜索到滿足組合要求的遍歷A,即進(jìn)入組建并輸出含空洞的哈密頓圈.

第i步走馬成功后,檢測(cè)若i=mn- 1,還未完成遍歷,經(jīng)i=i+1繼續(xù)下一步探索.

第i步選取8個(gè)方向若保持q=0,即i時(shí)的8 個(gè)方向均不能走馬,在此卡住,不能再向前了,于是方向t(i)與此時(shí)馬位清“0”后,經(jīng)i=i-1迭代回溯到前一步繼續(xù)探索.

當(dāng)回溯到i=0時(shí),所有結(jié)點(diǎn)搜索完成,結(jié)束.

1.3 棋盤(pán)左上角置“1”規(guī)范化輸出

哈密頓圈是一個(gè)封閉圈,無(wú)所謂起點(diǎn)與終點(diǎn).為方便查閱,習(xí)慣把棋盤(pán)的左上角置“1”進(jìn)行規(guī)范化輸出.

棋盤(pán)左上角遍歷按遍歷A旋轉(zhuǎn)180°實(shí)際輸出,注意到此時(shí)棋盤(pán)左上角元素實(shí)為 A遍歷的d(n,m).因而可設(shè)e=d(n,m)- 1,組合圈的每一步均減去e,這樣使棋盤(pán)左上角置“1”.

同時(shí),為銜接必需,根據(jù)圖1所示逆時(shí)針構(gòu)建中各遍歷所在位置進(jìn)行調(diào)整:

左邊從上至下共wv個(gè)遍歷的元素需分別加上mn、…、wvmn;

下部從左至右橫排的wh個(gè) A同向遍歷的元素需分別加上(wv+1)mn,…,(wv+wh)mn;

右邊從下至上共wv個(gè)遍歷的元素需分別加上(wh+wv+ 1)mn, … ,(wh+2wv)mn;

上部從右至左橫排的wh-1個(gè)同向旋轉(zhuǎn)遍歷元素需分別加上(wh+ 2wv+ 1)mn, … , (2wh+ 2wv-1)mn;

最后,棋盤(pán)左上角遍歷中出現(xiàn)的所有非正項(xiàng)均需加上 (2wh+2wv)mn.

1.4 構(gòu)建實(shí)例與說(shuō)明

遍歷為n行m列 (m＞2n),請(qǐng)輸入n,m:3,8

選擇wh=wv= 1,構(gòu)建如圖3所示,即得一個(gè)14行8列棋盤(pán),中央含8行2列空洞的哈密頓圈.

圖3 96步含空洞的哈密頓圈

該含空洞的哈密頓圈共有96個(gè)馬步！

應(yīng)用一元旋轉(zhuǎn)組合模型構(gòu)建,遍歷A還可選3×7、3×9、3×10等.

簡(jiǎn)單構(gòu)建時(shí)選擇wh=wv=1即可,若一般地?cái)U(kuò)展到橫排wh個(gè)遍歷、豎列wv個(gè)旋轉(zhuǎn)遍歷(這里wh與wv分別為從鍵盤(pán)輸入的任意大于 1的正整數(shù)),此時(shí)要求whm＞ 2n≥ 6,而構(gòu)建元素除以上列舉參數(shù)外,遍歷A還可選 5×5、5×6 等.

2 二元支撐模型構(gòu)建

二元支撐組合模式,即需用兩個(gè)不同的馬步遍歷A,B通過(guò)支撐組合構(gòu)建含空洞的哈密頓圈,如圖4所示.

圖4 二元支撐組合模式

2.1 二元支撐組合模型

二元支撐組合模式的組合元素遍歷A同前,即為n行m列,始點(diǎn)為(1,1),終點(diǎn)為 (2,m-1);設(shè)組合元素遍歷 B為n1行m1列,始點(diǎn)為(1,1),終點(diǎn)為(n1,3).

按如圖4所示的二元支撐組合模式,遍歷A終點(diǎn)(2,m-1)既可與下一個(gè)同向的A始點(diǎn)(1,1)相銜接,也可以與異向的 B始點(diǎn)(1,1)相銜接;而遍歷B終點(diǎn) (n1,3)既可與下一個(gè)同向的 B始點(diǎn)(1,1)相銜接,也可以與異向的 A始(1,1)相銜接,因而構(gòu)建時(shí)可以進(jìn)行橫與豎兩個(gè)方向的任意擴(kuò)展.

設(shè)上下部設(shè)置wh個(gè)遍歷A,左右部設(shè)置wv個(gè)遍歷B,則所構(gòu)建的含空洞的哈密頓圈共走2whmn+2wvmn步,構(gòu)建的棋盤(pán)為 (2n+wvn1)×whm,所含空洞為wvn1× (whm-2m1).

注意到whm≤2m1時(shí)組合無(wú)空洞,顯然要求whm＞2m1.

2.2 探索組合遍歷遞歸算法設(shè)計(jì)

注意到構(gòu)建需探索兩個(gè)不同的遍歷元素,擬采用遞歸設(shè)計(jì)實(shí)施探索.

建立遞歸函數(shù):探索在n×m棋盤(pán)中始點(diǎn)為(x,y)、終點(diǎn)為(x1,y1)的馬步遍歷.

遞歸過(guò)程中,棧保留了遞歸過(guò)程中的各個(gè)狀態(tài)的參數(shù),因而可省略以上回溯設(shè)計(jì)中的t,x,y數(shù)組.控制馬步規(guī)則的a、b數(shù)組與二維數(shù)組d(i,j)同前.

在控制k循環(huán)中若對(duì)所有k= 1,2,… ,8,候選位置(u,v)均不滿足走馬條件(或位置出界,或位置非空),則通過(guò)實(shí)施回溯,繼續(xù)前一步的檢測(cè).

若第g步全部8個(gè)位置已走完,則回溯到g-1步.對(duì)于g-1步,k=k+1后繼續(xù)檢測(cè),直到該步8個(gè)位置已走完時(shí),又回溯到前一步.若第g步走步成功且g＜mn,則g+1后遞歸進(jìn)入下一步探索.整個(gè)程序依此進(jìn)行遞歸檢測(cè)與回溯,直到回溯到第1步結(jié)束.

當(dāng)走到第g步時(shí),若mn且滿足終點(diǎn)條件(u=x1且v=y1)時(shí),即已搜索到指定遍歷,標(biāo)志量q=1,返回主程序.若 =mn但不滿足終點(diǎn)條件時(shí),則g=g- 1繼續(xù)搜索.

主程序兩次帶不同的始點(diǎn) (x,y)與終點(diǎn) (x1,y1)調(diào)用遞歸函數(shù)搜索遍歷B、A.首先若探索B成功,則把d數(shù)組元素賦值給c數(shù)組,同時(shí)d數(shù)組元素清0,為接著探索A遍歷作準(zhǔn)備.

若兩次探索成功,則按左上角置“1”規(guī)范(同前,具體數(shù)據(jù)作相應(yīng)修改)輸出組建的含空洞哈密頓圈.兩次調(diào)用若存在一次搜索不成功,輸出“沒(méi)有合適的遍歷”而結(jié)束.

2.3 構(gòu)建實(shí)例與說(shuō)明

遍歷B為n1行m1列,請(qǐng)輸入n1,m1:4,3

遍歷A為n行m列(m>2m1),請(qǐng)輸入n,m:3,10

選擇wh=wv= 1,得如圖5所示棋盤(pán)為10行10列,中間空洞為4行4列的哈密頓圈.

圖5 84步含空洞的哈密頓圈

該含空洞的哈密頓圈共有84個(gè)馬步.

由輸出結(jié)果看,馬步從棋盤(pán)左上角開(kāi)始,圍繞中央空洞瀟灑走一“回”(“回”字通道寬度為 3格),最后又回到出發(fā)點(diǎn).

應(yīng)用二元支撐組合模型構(gòu)建時(shí),遍歷A的參數(shù)同前列舉,而遍歷B可選3×9、3×11、4×3、4×5、5×5等.

3 結(jié)束語(yǔ)

應(yīng)用組合模型對(duì)含空洞的哈密頓圈的探索與構(gòu)建,拓廣了哈密頓圈圖論課題的研究范圍.

以上提供的兩個(gè)構(gòu)建含空洞的哈密頓圈的組合模型也可以構(gòu)建某些棋盤(pán)參數(shù)較大的不含空洞的哈密頓圈.

應(yīng)用一元構(gòu)建組合模型時(shí),如果參量m=n(例如m=n= 5),選擇上下部各設(shè)置2個(gè)A,左右各設(shè)置wv個(gè)A時(shí)可構(gòu)建棋盤(pán)為(wv+ 2)n×2n的不含空洞的哈密頓圈.應(yīng)用二元構(gòu)建組合模型時(shí),如果輸入的參量滿足m=2m1(例 如n1=4 ,m1=5,n= 3,m=10)時(shí)也有可能構(gòu)建棋盤(pán)為(2n+n1)×m不含空洞的哈密頓圈.

應(yīng)用常規(guī)回溯或遞歸搜索哈密頓圈,當(dāng)棋盤(pán)參數(shù)較大時(shí),因相應(yīng)回溯層次太多或遞歸深度太深而顯得無(wú)能為力,采用以上組合方式是一個(gè)較好的解決途徑.

在給定棋盤(pán)的行與列,同時(shí)給定中央空洞的行與列的哈密頓圈搜索時(shí),必須根據(jù)具體實(shí)際選擇組合模型與運(yùn)行參數(shù).

本文推出的兩個(gè)組合模型只限空洞在棋盤(pán)中處于上下對(duì)稱、同時(shí)左右也對(duì)稱的正中央,如果要求空洞在棋盤(pán)上下或左右有偏移時(shí),必須設(shè)計(jì)更復(fù)雜的多元組合模型.

[1]寧安琪,寧宣熙.有洞棋盤(pán)的馬步哈密頓圈問(wèn)題及其實(shí)證研究[J].小型微型計(jì)算機(jī)系統(tǒng),2004,(12):2126～2130

[2]寧安琪,寧宣熙.正方棋盤(pán)中廣義馬步哈密頓圈問(wèn)題的若干研究結(jié)果[J].小型微型計(jì)算機(jī)系統(tǒng),2005,(09):1551～1555

[3]徐尚進(jìn).有向圖具有哈密頓圈的一個(gè)充要條件[J].廣西大學(xué)學(xué)報(bào)(自然科學(xué)版),1999,(2)

[4]寧宣熙.堵塞流理論及其應(yīng)用[M].北京:科學(xué)出版社,2005

[5]Zhu Yu-long,Shi Gang.Two new solutions for the Knight's tour problem[J].Mini-Micro Systems,1996,17(8):51～59.

[6]Ning Xuan-xi.Study on application of blocking flow theory in determination of Hamiltonian Guaph[R].Report on Aeronautical Science and Technology of China,GF-99045.(1999)

[7]Kevin McGown,Ananda Leininger.Knight's tour[EB/OL].http://oregonstate,edu/garityd/reu/.

Knight’s Circuit Tour on a Chessboard with Holes

YANG Ke-chang1,LIU Zhi-hui2
(1.College of Computer Science,Hunan Institute of Science and Technology,Yueyang 414006,China;2.Hunan Broadcasting System,Changsha 410000,China)

By searching some particular and small-scale knight’s path tours,this paper assembles them in accordance with two combination models into a knight’s circuit tour on a chessboard with holes,thus the scope of the study on Hamiltonian graphs theory is extended.

Knight’s circuit tour;hole;combination;recursion;backtracking

TP311.1;O157

A

1672-5298(2011)01-0012-05

2010-12-21

楊克昌(1946? ),男,湖南冷水江人,湖南理工學(xué)院計(jì)算機(jī)學(xué)院教授.主要研究方向:組合數(shù)學(xué)與算法設(shè)計(jì)