马踏棋盘 （骑士周游）问题_骑士周游问题

// 代码
// 马踏棋盘.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include"stdio.h"
#include"time.h"

#define X 6              //棋盘>=6且为偶数
#define Y 6
int CHESS[X][Y];

int next(int *x, int *y, int count)           //判断x、y的下一个点是否符合要求，若符合则把x、y的值改为下一个点的值
{
	switch (count)
	{
	case(0):
		if (*x - 2 >= 0 && *y - 1 >= 0 && CHESS[*x - 2][*y - 1] == 0)
		{
			*x = *x - 2;
			*y = *y - 1;
			return 1;
		}
		break;
	case(1):
		if (*x - 2 >= 0 && *y + 1 < Y&&CHESS[*x - 2][*y + 1] == 0)
		{
			*x = *x - 2;
			*y = *y + 1;
			return 1;
		}
		break;
	case(2):
		if (*x - 1 >= 0 && *y + 2 < Y&&CHESS[*x - 1][*y + 2] == 0)
		{
			*x = *x - 1;
			*y = *y + 2;
			return 1;
		}
		break;
	case(3):
		if (*x + 1 < X&&*y + 2 < Y&&CHESS[*x + 1][*y + 2] == 0)
		{
			*x = *x + 1;
			*y = *y + 2;
			return 1;
		}
		break;


	case(4):
		if (*x + 2 < X&&*y + 1 < Y&&CHESS[*x + 2][*y + 1] == 0)
		{
			*x = *x + 2;
			*y = *y + 1;
			return 1;
		}
		break;
	case(5):
		if (*x + 2 < X&&*y - 1 >= 0 && CHESS[*x + 2][*y - 1] == 0)
		{
			*x = *x + 2;
			*y = *y - 1;
			return 1;
		}
		break;
	case(6):
		if (*x + 1 < X&&*y - 2 >= 0 && CHESS[*x + 1][*y - 2] == 0)
		{
			*x = *x + 1;
			*y = *y - 2;
			return 1;
		}
		break;
	case(7):
		if (*x - 1 >= 0 && *y - 2 >= 0 && CHESS[*x - 1][*y - 2] == 0)
		{
			*x = *x - 1;
			*y = *y - 2;
			return 1;
		}
		break;
	default:break;

	}
	return 0;
}


void print(int(*p)[Y])              //输出棋盘
{
	int x, y;
	for (x = 0; x < X; x++)
	{
		for (y = 0; y < Y; y++)
			printf("%3d", CHESS[x][y]);
		printf("\n");
	}
}


int find(int a, int b, int count)
{
	int x = a;
	int y = b;
	CHESS[x][y] = count;                  //改变棋盘的值，记录步数
//	printf("%d\n", count);             //调试用
	if (count >= 43)
	{ 
		//print(CHESS);                  //调试用
	}
	if (X*Y  == count)
		return 1;                       //如果走到X*Y步，棋盘遍历完毕，退出
	int i = 0;
	int flag = 0;
	flag = next(&x, &y, i);                //判断下一步是否符合
	while (flag == 0 && i < 7)              //不符合尝试下一个点，上一步i=0，次步从i=1开始
	{
		i++;
		flag = next(&x, &y, i);
	}
	while (flag)                            //找到满足点递归下一步
	{
		if (find(x, y, count + 1))              //如果找到最后一个，返回
		{
			return 1;
			printf("%d\n", count + 1);
		}
		x = a;                             //否则，回溯上一步
		y = b;
		i =i++;                             //和上一个while对应，i++为未试过的情况
		flag = next(&x, &y, i);

		while (flag == 0 && i < 7)
		{
			i++;
			flag = next(&x, &y, i);         //直到找到满足点为止，找到后通过while进入下一次递归
		}

	}
	if (flag == 0)                                //flag==0，无满足点，返回上一步
	{
		CHESS[a][b] = 0;                          //把该点的棋盘重置为0
	}
	return 0;
}



int main()
{
	clock_t t1, t2;
	int a = 7, b = 7;
	t1 = clock();
	if (find(3, 1, 1))     //开始位置（3,1）
	{
		printf("Result:\n");
		print(CHESS);
	}
	else
		printf("Can not find\n");
	t2 = clock();
	printf("Time:\n %ds\n", ((t2 - t1) / CLOCKS_PER_SEC));
	return 1;
}

//在递归使用的过程中，一开始只是按照之前使用过的递归模式进行码码，
//结果多次尝试后未果，查论坛后发现自己的算法有问题。
//要根据实际问题用不同的算法
//到底是对递归和回溯的过程不过熟练，尤其是遍历和回溯的判断和结构
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