关于骑士巡游问题的一些思考

mzy

关于骑士巡游问题的一些思考
初二的时代杯有一道题是关于骑士巡游的。
题目本身并不重要，这里介绍一下骑士巡游规则：

骑士巡礼（英语：Knight's tour），又名骑士巡游，是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格，而且每个网格只能够经过一次。假若骑士能够从走回到最初位置，则称此巡礼为“封闭式巡礼”，否则，称为“开放巡礼”。对于8*8棋盘，一共有26,534,728,821,064种封闭巡礼，有19,591,828,170,979,904种开放式巡礼。[1][2][3]

由骑士巡礼引申出了一个著名的数学问题 ：骑士巡礼问题--找出所有的骑士巡礼路径。编写一个程序来找出骑士巡礼路径经常在计算机系的学生的练习中出现。骑士巡礼问题的变种包括各种尺寸的棋盘甚至非正方形的棋盘。 ——WikiPedia

在zjy的启发下，我和wyd,zwb昨天晚上补题时思考了一下：给定一个n*m的棋盘，问是否存在合法的骑士巡游
然后开始打游戏了(bushi

目前的几个思路如下：
1.爆搜
使用类似于DFS或双向多源BFS的方法搜索
似乎可以分治？
2.贪心
想象每个点每一步有八个路径，每次选择下一步时，优先走到出路最少的格子，以避免封锁后续路径
3.数学方法
目前没有任何头绪


最后附上我写的代码：

1. #include <iostream>
   
2. #include <cstdio>
   
3. using namespace std;
   
4. 
   
5. const int MAXN = 100;  // 假设最大图的节点数为100
   
6. bool adj[MAXN][MAXN];   // 邻接矩阵
   
7. bool visited[MAXN];     // 记录节点是否访问过
   
8. 
   
9. // 深度优先搜索函数
   
10. void dfs(int node, int n) {
    
11.     visited[node] = true;  // 标记当前节点已访问
    
12.     printf("%d ", node);    // 输出当前节点
    
13. 
    
14.     // 遍历所有邻接节点
    
15.     for (int i = 0; i < n; i++) {
    
16.         if (adj[node][i] && !visited[i]) {
    
17.             dfs(i, n);  // 如果当前节点有边连接到 i 且 i 没有访问过，则递归调用 dfs
    
18.         }
    
19.     }
    
20. }
    
21. 
    
22. int main() {
    
23.     int n, m;
    
24.     scanf("%d %d", &n, &m);  // 输入图的节点数 n 和边数 m
    
25. 
    
26.     // 初始化邻接矩阵
    
27.     for (int i = 0; i < n; i++) {
    
28.         for (int j = 0; j < n; j++) {
    
29.             adj[i][j] = false;  // 初始化所有边为没有连接
    
30.         }
    
31.     }
    
32. 
    
33.     // 输入边的关系
    
34.     for (int i = 0; i < m; i++) {
    
35.         int u, v;
    
36.         scanf("%d %d", &u, &v);  // 输入边 (u, v)
    
37.         adj[u][v] = true;  // 标记 u 到 v 有一条边
    
38.         adj[v][u] = true;  // 假设图是无向的，标记 v 到 u 有一条边
    
39.     }
    
40. 
    
41.     // 初始化 visited 数组
    
42.     for (int i = 0; i < n; i++) {
    
43.         visited[i] = false;
    
44.     }
    
45. 
    
46.     // 假设从节点 0 开始 DFS
    
47.     dfs(0, n);
    
48. 
    
49.     return 0;
    
50. }
    

复制代码

mzy

丸辣忘了放积分奖励了

会设不会解

%%%%%%%%%%%%%%%%%