http://www.paper.edu.cn
关于Knight’s Tour Problem 的图论解法
吴英，李传文
兰州大学数学与统计学院，甘肃兰州 （730000）
摘 要：本文通过分析欧拉所给出的Knight’s Tour Problem 的解法, 结合哈密尔顿路和哈密尔顿圈的相关知识，得出其解法对应着二部图中的一条哈密尔顿圈。由此再充分利用8×8棋盘所对应的8×8表格的对称性及同构图的特性，对欧拉所给出的Knight’s Tour Problem 的解法作了进一步的探讨，得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法。最后，把Knight’s Tour Problem推广到了m×n棋盘上，考虑到移动规则的特殊性，利用图论的相关知识，得到了3×4、8×16和16×16棋盘上的Knight’s Tour Problem的解法，同时给出了8m×8n（m＞2,n＞2）棋盘上Knight’s Tour Problem的猜想。
关键词: Knight’s Tour Problem 哈密尔顿路 哈密尔顿圈 同构图 图的对称性 中图分类号：O157.6
1 问题的提出及有关理论
Knight’s Tour Problem 是由印度棋手在大约公元前200年时直观地提出并解决的，该问题用现代语言描述的话，仍是在一个具体的图中找寻哈密尔顿圈的问题。其中，图G中的哈密尔顿圈指的是经过图G中每个顶点且只经过一次的闭迹；而图Ｇ中哈密尔顿路指的是经过Ｇ中每个顶点且只经过一次的开迹。
Knight’s Tour Problem：给出一个8×8 棋盘，用一个棋子代表骑士。一个骑士从当前位置通过向垂直方向移动2格，水平方向移动1格，或向垂直方向移动1格，水平方向移动2格的方式移动，那么，是否存在这样的可能： 让骑士能够落在棋盘的每一格上恰好一次，而又不违反规则呢？这样的旅行称为骑士周游（knight tour）。还可以要求一个骑士周游具有这样的性质：从最后一格移到第一格时，仍满足一个合法的骑士移动，具有这种性质的骑士周游称为重复周游（Reentrant）。
，
在给出该问题解法之前，我们先介绍如下定义、定理及相关理论[12]。 定义1 在图G中，如果一条边的两端点相同，就称它为环（loop）。 定义2 设G是无向图（该图中的每条边都没有方向），x∈V(G)的顶点度（vertex degree）定义为G中与顶点x相关联的边的数目（一条环要计算两次）。 定义3 两个图G=(V(G),E(G),ψG)和H=(V(H),E(H),ψH)称为同构的（isomorphic）,记为D≌H,如果存在两个双射
θ: V(G) → V(H) 和
Φ: E(G) → E(H) 使得对任意a∈E(G),
ψG(a)=(x,y)当且仅当ψH(Φ(a))=(θ(x),θ(y))∈E(H).
映射对（θ,Φ）称为G和H之间的一个同构映射(isomorphic mapping).
定义４ 若无环图的顶点集可以划分为两个非空子集X和Y（其中∣X∣= m和∣Y∣= n）,使得X中任何两顶点之间无边相连并且Y中任何两顶点之间也无边相连，则称该图为２部分图(偶图，bipartite graph或bigraph),记为K*m,n,{X,Y}称为２部划分(bipartation). 定理1 在8×8棋盘中，令aij 表示第i行第j列公共的棋格（1≤i,j≤8），akl 表示第k行第l列公共的棋格（1≤k,l≤8）。由移动法则可知，从aij 到akl 是合法的移动，当且仅当︱i-k︱=1,︱j-l︱=2或者︱i-k︱=2,︱j-l︱=1. 证明：由于aij 表示第i行第j列公共的棋格，akl 表示第k行第l列公共的棋格，如果从aij 到
-1-
http://www.paper.edu.cn
akl 是合法的移动，则其必然是向垂直方向移动2格，水平方向移动1格，或向垂直方向移动1格，水平方向移动2格的方式移动，所以︱i-k︱=1, ︱j-l︱=2或者 ︱i-k︱=2,︱j-l︱=1。反之，如果︱i-k︱=1, ︱j-l︱=2或者 ︱i-k︱=2,︱j-l︱=1，则表明从aij 到akl必然是向垂直方向移动2格，水平方向移动1格，或向垂直方向移动1格，水平方向移动2格的方式移动，显然满足移动法则。 □
另外，当︱(i+j）-(k+l)︱为偶数时，aij 到akl 绝不是合法移动；也就是说，只有当(i+j）与(k+l) 奇偶性不同时，aij 到akl 才可能是合法的移动。把每个棋格看作某个图G的顶点，并且给每个顶点分别标上对应的标号aij，那么只有当(i+j）与(k+l)奇偶性不同时，顶点aij 与akl 之间才可能存在一条公共边；也就是说，当(i+j）与(k+l)奇偶性相同时，顶点aij 与akl 之间不存在公共边。所以，我们可以根据(i+j）的奇偶性把顶点归类为两个不同的顶点子集M，N，从而在此意义下8×8棋盘可被视为二部图，在同构的意义下该二部图是唯一的，记作K*32，32，其顶点集分别为：M={ aij︱(i+j）为偶数，1≤i,j≤8}， N={ akl︱(k+l) 为奇数，1≤k,l≤8}。
棋盘中的棋格看作图K*32，32的顶点，两顶点之间有一条边当且仅当对应棋格之间存在合理的骑士移动。从而一条哈密尔顿路径代表8×8棋盘上的一个骑士周游，一个哈密尔顿圈代表一个重复周游（Reentrant）。
定理2 设 G是一个具有二分划Ｘ，Ｙ的二部图，如果︱X︱≠︱Y︱, 则 G 中不存在哈密尔顿圈。
2 欧拉解法及对应图论解法
欧拉对该问题进行了研究，并给出了一种解法[3]。该解法将8×8棋盘上的Knight’s Tour Problem转化成为8×8表格上能否按一定规则排列数字1到64的数学问题。欧拉给出的解法满足定理1的条件，并且我们将应用定理1探索该问题的新解法。欧拉得到的解法由下面的表格给出：
58 4349 4644 5947 5022 731 28 213 3060574845322349
37425156162920
526138332419105
4136556413162528
6253343918271411
3540635415121726
表1 欧拉得出的8×8棋盘上Knight’s Tour Problem的解法
其中，棋格中的数码代表骑士到达该棋格的次序。特别地，数码1的棋格表示骑士的初始位置。因为从棋格1到棋格64的移动是一个合法的骑士移动，所以该周游是一个重复周游(Reentrant)。并且该解法对应在二部图K*32，32上是一个哈密尔顿圈。我们任取8×8棋盘上的某一棋格，按照二部图K*32，32上的哈密尔顿圈上顶点所对应的棋格进行合理移动，就可以顺利完成一次重复周游(Reentrant)。结合以上图论知识的分析，另外考虑到该解法的循环性及其8×8棋盘的对称性，本文作者得到下述算法，进而可以容易的得到Knight’s Tour Problem的一系列解法。
8×8棋盘上的每一个棋格都可以作为周游的起始位置。也就是说，在表1中的每一个数字都可以变成1，其余数字均作相应变化，即可得出Knight’s Tour Problem 的一种解法。算法表述如下：任取表1中的数字K, 使其变为K'=1, 其余数字L均变为L'：
若L≥K, 则L'＝L-（K-1）；
若L＜K，则L'＝L-（K-1）+64。
例如，将表1中的17作为起始位置，则可得一种解法如下表所示：
-2-
http://www.paper.edu.cn
42 27 4433 30 4128 43 3231 34 296 55 1615 50 756 5 5251 14 5721263540495413436452217835853252039486164912463718232116259192447386360110表2 8×8棋盘上Knight’s Tour Problem新的解法
因此，在欧拉解法的基础上我们应用上述算法可得另外一系列不同解法。
3 Knight’s Tour Problem 的拓展及相关猜想
Knight’s Tour Problem 能应用在任何m×n的棋盘上，我们将其视为图中哈密尔顿路径的
存在性问题。把一个m×n棋盘中的棋格看作m×n阶的二部图G的顶点，两个棋格之间有一条边当且仅当这两个棋格间是一个合法的骑士移动。G 中的一条哈密尔顿路代表m×n棋盘上的一个骑士周游，一个哈密尔顿圈代表一个重复周游。我们考虑m×n棋盘为黑白相间的棋格，一个合法的骑士移动必然是不同颜色棋格间的移动。如果m和n都是奇数，则一种颜色的棋格数比另一种颜色的棋格数多1，因此由定理２可知，此时G中不存在重复周游。如果m和n中至少有一个是偶数，则黑白棋格数相同，这才有可能存在重复周游。骑士在n×n
22
棋盘上周游，用1到n为棋格标号，引出了一个方阵，1到n中的每个数码恰好出现一次。对于8×8的棋盘的上述解法对应在二部图K*32，32上是一个哈密尔顿圈，因此，每一个棋格都可以作为骑士的最终位置。也就是说，在表1中的每一个数字都可以变成64，其余数字均作相应变化，即可得出Knight’s Tour Problem 的一种解法。具体算法如下： 任取表1中的数字K, K变成K′=64,其他数字L变为L′,若L≤K, 则 L′=L+(64-K)； 若L＞K, 则L′=L-K.
由此算法可以保证棋盘中最外面的棋格可以为终点，即表1中最外面的行列中的数字可以是64，由此，我们可以得出在8×16和16×16棋盘上的Knight’s Tour Problem的解法。我们把16×16棋盘看作四个8×8棋盘拼凑而成，骑士从一个8×8棋盘过渡到另一个8×8棋盘来完成周游，数字1代表起始位置，顺时针方向完成一个8×8棋盘上的骑士周游再到另一个8×8棋盘，1和64之间都是合法的骑士周游。对应解法如下表所示：
32 17 34 11 26 15 3623 20 31 16 35 10 2718 33 22 15 12 29 821 24 19 30 7 38 1360 45 6 39 62 51 565 40 61 44 57 54 146 59 42 3 48 63 5241 4 47 58 43 2 49
914372853505564
1029388916675116111
8790103941051106574
10410192897667112117
81869510010911473128
96105827768127118113
8580991081211246972
10697788312671122119
79 84 107 98 123 120 125 70 表3 8×16棋盘上Knight’s Tour Problem的解法
32 1723 2018 3321 2460 455 4046 5938 2934 11 26 1531 16 35 1022 25 12 2919 30 7 386 39 62 5161 44 57 5442 3 48 6324 27 2 11362781356152495291437285350556447382924272115247642326393051461105540372825123485350172231364550964533241181346354492821163544576058374233141962758551415 20 43 34 59 56 61 6 9 41 4 47 58 43 2-3-
http://www.paper.edu.cn
23 2640 3717 2232 4121 1642 3315 2039 30 51 4628 25 12 331 36 45 5018 13 4 6335 44 57 6014 19 62 743 34 59 561489545586110536449855649243584744152634834259461545744614055651623964560133873019242182912252233182710351631202336 15 26 11 34 17 32 表4 16×16棋盘上Knight’s Tour Problem的解法
猜想：当m＞2,n＞2时，8m×8n棋盘上的Knight’s Tour Problem不存在合理的骑士周游。
我们可以把16×16棋盘看作四个8×8棋盘拼凑而成，骑士从一个8×8棋盘过渡到另一个8×8棋盘时，其起点和终点都集中在16×16棋盘中心的8×8棋盘中，当m＞2,n＞2时，8m×8n棋盘上的骑士移动再无法合乎法则的向外延伸，故可能不存在合理的骑士周游。
参考文献：
[1]孙惠泉.图论及其应用（第1版）[M]. 北京：科学出版社 2004.9. (4—6).
[2]徐俊明.图论及其应用（第1版）[M]. 合肥：中国科学技术大学出版社 1998.1. (8—16).
[3]Richard A.Brualdi. Introductory Combinatones(Fourth Edition.)[M].Beijing: China machine, Press. 2005.3 (454-455).
The solutions of Knight’s Tour problem in Graph Theory
Wu Ying,Li Chuanwen
Department of mathematics and satistics of Lanzhou University, Lanzhou, 73000 China Abstract
According to the analysis of the solution to Knight’s Tour Problem given by Euler earlier and the knowledge of Hamilton path and Hamilton cycle, we obtain that the solution denotes a Hamilton cycle in the defined bigraph. With the use of the symmetrics of 8-by-8 chess-board and the special properties of isomorphic graphs, we botain a series of solutions of this problem whose each square can be the initial position of the knight from the advanced discussions about the solutions given by Euler. Finally, we take the Knight’s Tour Problem to m-by-n chess-board. According to the spectral of the precinple to legal moves and some knowledge about Graph theory we can obtain the solutions of Knight’s Tour Problem on 3-by-4 chess-board
8-by-16 chess-board and 16-by-16 chess-board,and obtain a conjecture to Knight’s Tour Problem on 8-by-8 chess-board（m＞2,n＞2）.
Keywords：Knight’s Tour Problem Hamilton path Hamilton cycle isomorphic graph the symmetrics of graphs CLC Number：O157.6
作者简介：吴英(1980—)，山东郓城人，硕士研究生，研究方向基础数学。
-4-