分治法解骑士巡游问题(Knight‘s Tour)

问题描述

国际象棋的棋盘为$m\times n$的方格棋盘，现将“马”放在任意指定的方格中，按照“马”走棋的规则（与中国象棋规则一样，马走“日”字）将“马”进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋盘$m\times n$个方格，回到起点。
编写代码，实现马周游操作，用数字给出“马”移动的路径并格式化输出。

参考资料：
Parberry I . An Efficient Algorithm for the Knight’s Tour Problem[J]. Discrete Applied Mathematics, 1997, 73(3):251-260.
Cull, P.; De Curtins, J. (1978). “Knight’s Tour Revisited” . Fibonacci Quarterly. 16: 276–285.

解题思路

分治法的核心思想，就是“分而治之”。因此分治求解该问题的基本方法就是

将大棋盘分成小棋盘；
小棋盘直接给出答案；
小棋盘拼接成大棋盘。
1
2
3

$|m-n|\le 2$条件下的解

首先易证明对于$m\times n$尺寸的棋盘，若$m\times n$为奇，则该棋盘上不存在马的周游回路。例如，若给棋盘每格涂上两种颜色中的一种，所有相邻两格颜色不同，则马的每一步都将从一种颜色的格子跳入另一种颜色的格子。奇数总格数的棋盘需要奇数步才能够遍历完，那么出发时的格子颜色与最后一步到达的格子颜色必定不同，由此证明该棋盘上马的周游无法形成回路。
首先定义结构化概念：如果马的周游路线包括下图所示的几步，则称其为结构化的。

直接给出几个基本棋盘的结构化回路：


从左到右、从上到下分别是$6\times 6,6\times 8,8\times 8,8\times 10,10\times 10,10\times 12,6\times 7,7\times 8,8\times 9,9\times 10,10\times 11,11\times 12$的棋盘的回路。

当棋盘大小$m,n\ge 12$且$|m-n|\le 2$时，棋盘可拆分成$4k$个结构化的基本棋盘，每相邻的四个棋盘上的回路都可按下图步骤所示合并：断开A、B、C、D，连接E、F、G、H。

设该算法时间复杂度为$T(n)$，其递归方程为 T ( n ) = { O ( 1 ) n<12 4 T ( n / 2 ) + O ( 1 ) n ≥ 12 T(n)=

$$\begin{cases}O(1)&\text{n<12}\\4T(n/2)+O(1) &\text{n}\ge\text{12}\end{cases}$$ T(n)={O(1)4T(n/2)+O(1)​n<12n≥12​。解得$T(n)=O(n^2)$。

编程细节要点为

如何存储棋盘
如何把棋盘正确分割为基本棋盘
如何将基本棋盘的路线正确填入原棋盘
1
2
3

完整代码如下

#include<cstdio>
#include<string.h>
int direct[8][2]={{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1}};					//马的八个移动方向
int ChessBoard[500][500][2];
const int B6_6[6][6][2]={																	//基本结构化棋盘，数字代表移动方向在direct中的下标，每格有两个移动方向
	{{0,7},{7,6},{0,5},{5,0},{7,5},{6,5}},
	{{1,0},{6,1},{1,4},{1,7},{6,4},{4,5}},
	{{2,7},{3,0},{4,3},{1,0},{7,2},{6,3}},
	{{7,2},{6,7},{5,0},{4,2},{3,7},{4,6}},
	{{0,1},{3,0},{0,5},{0,5},{4,2},{5,3}},
	{{1,2},{1,3},{3,4},{4,1},{2,4},{3,4}}
},
B6_7[6][7][2]={
	{{0,7},{0,6},{0,5},{0,5},{0,6},{7,6},{6,5}},
	{{1,0},{1,6},{6,4},{6,4},{1,4},{5,4},{5,4}},
	{{2,7},{3,0},{4,0},{2,1},{2,1},{7,2},{6,3}},
	{{2,7},{6,2},{5,2},{4,6},{4,5},{7,6},{6,5}},
	{{0,1},{3,0},{1,5},{5,0},{1,0},{5,2},{5,3}},
	{{1,2},{3,1},{2,4},{4,1},{2,1},{4,2},{4,3}}
},
B6_8[6][8][2]={
	{{0,7},{0,6},{5,0},{5,0},{0,6},{6,0},{5,7},{5,6}},
	{{0,1},{6,1},{6,4},{0,4},{4,1},{4,1},{7,4},{4,5}},
	{{2,7},{3,0},{7,4},{2,7},{7,2},{1,4},{2,7},{3,6}},
	{{7,2},{6,2},{5,6},{4,6},{6,5},{6,7},{5,7},{6,3}},
	{{0,1},{3,0},{1,5},{0,3},{3,1},{0,3},{2,5},{3,5}},
	{{1,2},{2,3},{2,4},{4,2},{1,2},{1,4},{3,2},{3,4}}
},
B7_8[7][8][2]={
	{{0,7},{6,7},{5,0},{0,5},{6,7},{0,7},{5,7},{6,5}},
	{{0,1},{1,7},{0,4},{5,7},{4,1},{1,4},{7,5},{6,4}},
	{{7,2},{3,1},{3,4},{6,2},{1,4},{3,5},{3,2},{3,5}},
	{{7,0},{6,0},{3,6},{1,7},{3,6},{1,0},{5,2},{6,3}},
	{{7,0},{6,3},{4,2},{4,7},{6,1},{7,0},{6,7},{4,6}},
	{{0,2},{2,3},{4,5},{2,5},{3,5},{0,5},{5,2},{4,5}},
	{{1,2},{1,3},{1,4},{1,2},{3,1},{1,2},{2,3},{3,4}}
},
B8_8[8][8][2]={
	{{0,7},{7,6},{5,7},{0,5},{7,5},{5,0},{7,5},{6,5}},
	{{7,1},{1,6},{1,4},{6,1},{1,6},{1,4},{7,6},{4,5}},
	{{2,7},{3,6},{5,3},{3,7},{7,0},{1,3},{7,2},{6,3}},
	{{2,1},{7,3},{7,2},{2,0},{5,6},{2,0},{4,7},{6,3}},
	{{2,7},{3,6},{5,1},{0,7},{3,6},{4,3},{7,2},{4,3}},
	{{7,1},{7,6},{0,3},{2,3},{0,7},{7,4},{7,2},{3,6}},
	{{2,0},{3,0},{5,0},{2,5},{3,4},{5,0},{5,4},{5,3}},
	{{2,1},{1,3},{4,3},{4,1},{4,1},{3,1},{2,3},{4,3}}
},
B8_9[8][9][2]={
	{{0,7},{0,6},{5,0},{0,5},{0,6},{0,5},{5,0},{7,5},{6,5}},
	{{0,1},{1,6},{5,4},{1,4},{4,1},{1,4},{1,4},{7,4},{4,5}},
	{{2,1},{3,0},{6,4},{2,0},{7,5},{5,6},{1,6},{6,2},{5,3}},
	{{2,7},{0,7},{1,5},{4,1},{5,6},{4,5},{0,1},{6,7},{6,3}},
	{{1,7},{6,2},{5,1},{1,4},{2,0},{2,3},{6,2},{7,5},{6,4}},
	{{7,1},{3,6},{3,0},{2,6},{6,7},{1,5},{4,2},{7,2},{3,6}},
	{{0,2},{3,0},{5,0},{1,5},{4,0},{0,2},{5,0},{5,2},{5,3}},
	{{2,1},{1,3},{2,4},{4,2},{4,1},{3,1},{4,1},{2,4},{4,3}}
},
B8_10[8][10][2]={
	{{0,7},{0,6},{5,0},{0,5},{0,5},{6,5},{5,0},{0,5},{7,5},{6,5}},
	{{0,1},{1,6},{1,4},{1,4},{4,1},{1,4},{1,4},{1,0},{4,7},{6,4}},
	{{2,0},{3,6},{6,4},{6,5},{0,2},{0,6},{7,5},{6,7},{7,2},{4,3}},
	{{2,7},{1,7},{4,7},{6,0},{1,7},{7,5},{0,4},{5,4},{7,2},{3,5}},
	{{2,7},{6,2},{5,2},{1,7},{2,0},{4,1},{5,2},{1,3},{3,4},{6,3}},
	{{7,1},{3,6},{3,2},{3,6},{7,1},{3,5},{4,3},{0,7},{5,7},{6,3}},
	{{0,2},{3,0},{5,0},{1,5},{3,0},{5,0},{5,1},{0,5},{5,2},{5,4}},
	{{2,1},{1,3},{2,4},{4,1},{4,1},{1,3},{4,1},{4,1},{3,2},{3,4}}
},
B9_10[9][10][2]={
	{{0,7},{7,6},{5,0},{0,5},{7,0},{6,0},{5,0},{0,5},{7,6},{5,6}},
	{{7,1},{1,6},{7,4},{6,0},{4,1},{1,4},{4,7},{4,1},{4,7},{5,4}},
	{{2,7},{3,6},{5,3},{0,6},{6,2},{4,3},{0,5},{2,1},{2,5},{6,3}},
	{{2,1},{6,3},{0,2},{0,3},{1,7},{7,4},{1,5},{3,0},{5,4},{3,6}},
	{{2,0},{3,7},{2,0},{5,2},{1,4},{5,4},{5,1},{5,6},{7,2},{4,5}},
	{{7,2},{6,1},{4,0},{0,1},{4,1},{3,1},{5,3},{1,5},{2,7},{6,5}},
	{{7,0},{6,7},{3,7},{0,7},{4,1},{1,4},{2,5},{1,5},{6,7},{6,3}},
	{{0,2},{0,3},{4,5},{0,5},{1,0},{1,4},{5,0},{0,5},{5,2},{3,5}},
	{{1,2},{1,3},{3,4},{3,4},{3,1},{1,4},{4,1},{1,2},{4,2},{3,4}}
},
B10_10[10][10][2]={
	{{0,7},{0,6},{7,5},{6,0},{0,5},{6,5},{7,5},{5,0},{7,5},{6,5}},
	{{1,0},{6,0},{1,4},{1,4},{1,7},{4,1},{1,4},{1,0},{7,6},{4,6}},
	{{2,0},{3,6},{4,2},{4,3},{0,2},{5,6},{7,6},{6,3},{7,2},{4,3}},
	{{0,2},{7,6},{4,6},{7,1},{7,0},{3,0},{0,4},{2,6},{2,7},{6,3}},
	{{2,7},{0,7},{5,4},{7,0},{2,6},{2,7},{4,2},{4,3},{6,4},{6,3}},
	{{2,1},{2,6},{5,3},{7,4},{5,3},{4,3},{2,6},{6,5},{6,2},{3,5}},
	{{7,1},{3,6},{3,1},{2,5},{7,3},{1,5},{3,5},{1,2},{7,2},{6,5}},
	{{2,7},{1,6},{6,7},{1,5},{1,3},{2,5},{6,2},{1,2},{7,6},{6,5}},
	{{2,0},{1,3},{5,0},{1,0},{5,0},{5,3},{5,0},{1,0},{5,2},{5,3}},
	{{2,1},{3,2},{4,1},{3,1},{4,1},{4,2},{4,1},{2,1},{4,2},{4,3}}
},
B10_11[10][11][2]={
	{{0,7},{6,0},{0,5},{6,0},{7,5},{5,0},{0,6},{5,6},{0,7},{5,7},{6,5}},
	{{1,7},{6,0},{1,4},{4,1},{6,4},{4,1},{0,5},{4,1},{1,4},{6,5},{6,4}},
	{{0,2},{3,6},{0,2},{4,7},{1,6},{2,3},{2,6},{1,7},{5,4},{3,2},{3,6}},
	{{7,2},{3,6},{5,4},{6,2},{7,4},{5,0},{5,1},{5,6},{6,2},{6,2},{5,6}},
	{{2,1},{7,6},{7,6},{2,1},{3,1},{2,1},{7,6},{4,5},{3,1},{2,7},{6,5}},
	{{2,0},{6,3},{6,2},{0,6},{6,0},{1,3},{2,5},{6,2},{1,2},{2,5},{5,6}},
	{{2,7},{2,6},{4,3},{7,3},{1,0},{2,4},{4,5},{1,3},{7,1},{7,2},{3,6}},
	{{7,2},{6,2},{2,0},{6,2},{1,5},{6,7},{4,2},{6,7},{6,5},{2,7},{5,6}},
	{{2,0},{3,0},{1,5},{0,5},{4,3},{5,0},{1,5},{0,5},{0,1},{2,3},{5,3}},
	{{1,2},{1,3},{4,2},{4,1},{1,2},{1,4},{3,2},{4,2},{3,1},{2,4},{3,4}}
},
B10_12[10][12][2]={
	{{0,7},{0,6},{6,5},{0,5},{7,6},{0,5},{7,5},{0,5},{0,6},{0,5},{7,6},{6,5}},
	{{1,7},{1,6},{5,4},{1,4},{1,6},{1,4},{6,5},{1,4},{7,6},{1,4},{7,4},{6,4}},
	{{2,1},{3,2},{5,6},{2,6},{1,0},{5,3},{6,7},{2,3},{5,7},{2,0},{7,2},{6,3}},
	{{2,1},{3,6},{7,0},{2,1},{5,0},{5,2},{4,1},{2,5},{5,7},{6,3},{7,2},{4,3}},
	{{0,7},{2,6},{2,1},{7,1},{4,0},{1,2},{4,1},{3,5},{0,6},{3,5},{7,2},{6,3}},
	{{2,0},{0,7},{5,4},{6,3},{0,6},{1,6},{4,5},{1,6},{7,2},{3,6},{5,4},{6,3}},
	{{2,1},{3,6},{4,5},{7,4},{1,3},{0,6},{5,4},{2,0},{5,1},{0,7},{7,2},{6,3}},
	{{1,7},{7,6},{3,2},{2,5},{2,1},{6,7},{2,1},{7,4},{2,5},{4,3},{7,2},{6,4}},
	{{2,0},{1,0},{5,0},{5,0},{2,3},{5,0},{1,0},{5,0},{5,0},{5,0},{3,2},{5,3}},
	{{2,1},{3,1},{4,3},{4,1},{4,2},{4,1},{3,1},{4,1},{4,3},{4,1},{4,2},{4,3}}
},
B11_12[11][12][2]={
	{{0,7},{6,7},{5,0},{6,5},{7,5},{6,5},{5,0},{7,0},{5,6},{7,0},{5,7},{5,6}},
	{{7,1},{1,6},{1,4},{1,0},{4,1},{6,5},{6,1},{0,6},{4,1},{4,1},{7,5},{4,6}},
	{{7,2},{3,0},{3,2},{1,7},{0,2},{4,3},{6,7},{2,7},{1,3},{5,4},{2,3},{3,6}},
	{{2,7},{6,3},{0,7},{4,0},{7,2},{6,2},{2,4},{6,1},{0,5},{6,7},{2,7},{5,3}},
	{{7,0},{6,3},{7,6},{5,6},{3,4},{4,2},{1,6},{3,5},{3,5},{7,1},{2,4},{5,6}},
	{{7,2},{3,1},{4,0},{3,7},{6,2},{1,3},{1,2},{6,7},{5,2},{0,1},{3,5},{3,6}},
	{{0,2},{2,3},{2,7},{0,3},{4,5},{2,6},{5,1},{0,5},{1,6},{6,5},{2,3},{6,4}},
	{{0,7},{0,3},{1,4},{5,2},{3,1},{1,4},{5,2},{1,7},{3,5},{5,4},{2,7},{6,5}},
	{{7,0},{6,1},{5,4},{3,4},{2,1},{7,6},{1,5},{2,1},{6,2},{1,7},{7,2},{6,5}},
	{{0,1},{3,0},{4,5},{0,5},{1,5},{5,0},{5,0},{0,5},{3,5},{1,0},{5,2},{3,5}},
	{{1,2},{1,3},{1,4},{4,1},{2,1},{1,4},{1,3},{4,2},{4,1},{1,4},{3,2},{4,3}}
};
void DivideConquer(int x1,int y1,int x2,int y2);
void FillBoard(int *board,int x1,int y1,int x2,int y2,bool flag);
void CombineBoard(int x1,int y1,int x2,int y2);
int main()
{
	int m,n;
	printf("请输入棋盘大小m,n(|m-n|<=2):\n");
	scanf("%d%d",&m,&n);
	if (m*n%2||(m<6||n<6)) printf("该棋盘不存在骑士巡游回路\n");
	else if (n-m>2||m-n>2) printf("棋盘大小有误\n");
	else
	{
		int circuit[500][500],step=1,i,j,x,y;												//circuit记录每格的步序数
		printf("请输入马的起点坐标：");
		scanf("%d%d",&x,&y);
		if (x<=0||x>=m||y<=0||y>=n)	printf("非法的坐标\n");
		else
		{
			DivideConquer(0,0,m-1,n-1);
			memset(circuit,0,sizeof(circuit));
			i=--x;
			j=--y;
			do
			{
				circuit[i][j]=step++;															//模拟马走棋盘的过程
				int a=i,b=j;
				i+=direct[ChessBoard[a][b][0]][0];
				j+=direct[ChessBoard[a][b][0]][1];
				if (circuit[i][j]>1){
					i=a+direct[ChessBoard[a][b][1]][0];
					j=b+direct[ChessBoard[a][b][1]][1];
				}
			}while(i!=x||j!=y);
			printf("骑士巡游路线如下\n");
			for (int p=0;p<m;p++)
			{
				for (int q=0;q<n;q++)
					printf("%d\t",circuit[p][q]);
				printf("\n");
			}
		}
	}
	return 0;
}
void DivideConquer(int x1,int y1,int x2,int y2)
{
	//分治法主要函数
	int h=x2-x1+1,w=y2-y1+1,dw=w/4*2+w%2,dh=h/4*2+h%2;		//dw,dh分别是棋盘宽和高的一半，且保证了至少有一个是偶数，使得分治时不会出现无解的棋盘
	bool flag=false;
	if (w<h)
	{
		flag=true;
		int t=w;w=h;h=t;		//将棋盘翻转并标记，使得基本棋盘的内容能正确填入
	}
	if (h==6&&w==6) FillBoard((int*)B6_6,x1,y1,x2,y2,flag);		//填充基本棋盘
	if (h==6&&w==7) FillBoard((int*)B6_7,x1,y1,x2,y2,flag);
	if (h==6&&w==8) FillBoard((int*)B6_8,x1,y1,x2,y2,flag);
	if (h==7&&w==8) FillBoard((int*)B7_8,x1,y1,x2,y2,flag);
	if (h==8&&w==8) FillBoard((int*)B8_8,x1,y1,x2,y2,flag);
	if (h==8&&w==9) FillBoard((int*)B8_9,x1,y1,x2,y2,flag);
	if (h==8&&w==10) FillBoard((int*)B8_10,x1,y1,x2,y2,flag);
	if (h==9&&w==10) FillBoard((int*)B9_10,x1,y1,x2,y2,flag);
	if (h==10&&w==10) FillBoard((int*)B10_10,x1,y1,x2,y2,flag);
	if (h==10&&w==11) FillBoard((int*)B10_11,x1,y1,x2,y2,flag);
	if (h==10&&w==12) FillBoard((int*)B10_12,x1,y1,x2,y2,flag);
	if (h==11&&w==12) FillBoard((int*)B11_12,x1,y1,x2,y2,flag);
	if (h>11&&w>11)
	{
		DivideConquer(x1,y1,x1+dh-1,y1+dw-1);	//递归实现分治
		DivideConquer(x1+dh,y1,x2,y1+dw-1);
		DivideConquer(x1,y1+dw,x1+dh-1,y2);
		DivideConquer(x1+dh,y1+dw,x2,y2);
		CombineBoard(x1,y1,x2,y2);				//合并棋盘
	}
}
void FillBoard(int *board,int x1,int y1,int x2,int y2,bool flag)
{
	//实现基本棋盘的填充。flag为棋盘翻转标志
	int h=x2-x1+1,w=y2-y1+1;
	if (flag)
		for (int i=x1;i<=x2;i++)
			for (int j=y1;j<=y2;j++)
			{
				ChessBoard[i][j][0]=7-board[(i-x1+(j-y1)*h)*2];			//7-board，是利用了direct中互为转置的方向下标之和为7的细节
				ChessBoard[i][j][1]=7-board[(i-x1+(j-y1)*h)*2+1];
			}
	else
		for (int i=x1;i<=x2;i++)
			for (int j=y1;j<=y2;j++)
			{
				ChessBoard[i][j][0]=board[((i-x1)*w+j-y1)*2];
				ChessBoard[i][j][1]=board[((i-x1)*w+j-y1)*2+1];
			}
}
void CombineBoard(int x1,int y1,int x2,int y2)
{
	//合并棋盘，时间复杂度为O(1)
	int dw=(y2-y1+1)/4*2+(y2-y1+1)%2,dh=(x2-x1+1)/4*2+(x2-x1+1)%2;
	if (ChessBoard[x1+dh][y1+dw-1][0]==6) ChessBoard[x1+dh][y1+dw-1][0]=4;
	else ChessBoard[x1+dh][y1+dw-1][1]=4;
	if (ChessBoard[x1+dh+2][y1+dw-2][0]==2) ChessBoard[x1+dh+2][y1+dw-2][0]=1;
	else ChessBoard[x1+dh+2][y1+dw-2][1]=1;
	if (ChessBoard[x1+dh+1][y1+dw][0]==1) ChessBoard[x1+dh+1][y1+dw][0]=5;
	else ChessBoard[x1+dh+1][y1+dw][1]=5;
	if (ChessBoard[x1+dh][y1+dw+2][0]==5) ChessBoard[x1+dh][y1+dw+2][0]=4;
	else ChessBoard[x1+dh][y1+dw+2][1]=4;
	if (ChessBoard[x1+dh-1][y1+dw][0]==2) ChessBoard[x1+dh-1][y1+dw][0]=0;
	else ChessBoard[x1+dh-1][y1+dw][1]=0;
	if (ChessBoard[x1+dh-3][y1+dw+1][0]==6) ChessBoard[x1+dh-3][y1+dw+1][0]=5;
	else ChessBoard[x1+dh-3][y1+dw+1][1]=5;
	if (ChessBoard[x1+dh-2][y1+dw-1][0]==5) ChessBoard[x1+dh-2][y1+dw-1][0]=1;
	else ChessBoard[x1+dh-2][y1+dw-1][1]=1;
	if (ChessBoard[x1+dh-1][y1+dw-3][0]==1) ChessBoard[x1+dh-1][y1+dw-3][0]=0;
	else ChessBoard[x1+dh-1][y1+dw-3][1]=0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242

$m、n$任意情况下的解

具体请参考第二篇文献"Knight’s Tour Revisited"。大致思路是，直接给出一系列基本棋盘的曼哈顿回路和曼哈顿链，其中曼哈顿链都满足从棋盘某个角出发在另一角结束。如此就可将大棋盘拆分成若干小棋盘（不一定均分），然后将各小棋盘中的曼哈顿链和曼哈顿回路联接成一个大回路，即得解。除此外，该文章作者还证明了骑士巡游问题有解的必要条件是

$m\times n$为偶且$min(m,n)\ge 5$

代码实现较复杂暂未完成，有兴趣的读者可以自行尝试。