马踏棋盘回路计数问题

mathe

中国象棋（9×10）棋盘上一只马从任何一个位置出发，没有重复经过所有格子最后返回起始点的不同方案有多少种？ 如果不需要返回起始点，那么又有多少种方案？ 已添加到A193054, A193055

风云剑

以前试过，相当多，时间太久 以下是转的 ＝＝＝＝＝＝＝＝＝＝＝ /* 一、题目： （马的遍历问题）：设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复的走过棋盘上的每一个位置。 要求：（1）依次输出所走过的各位置的坐标。 （2）最好能画出棋盘的图形形式，并在其上动态的标注行走的过程。 （3）程序能方便的移植到其它规格的棋盘上。 二、设计思想概述： 根据设计的题目要求，首先先要了解中国象棋的棋盘规格以及马的走法。在中国象棋的棋盘上，和国际象棋一样也是8*8的方格，但是与国际象棋相比多出一条楚河汉界，而且按中国象棋中马的走法，马是在棋盘的点上行走的，而不是在格子上。因此在考虑实际问题时可以将点抽象成格子来处理，这样比较好理解和实现。 所以，中国象棋的棋盘可以抽象成10行9列的棋盘，马在格子上行走。 中国象棋中的马是走“日”字形的，也就是如果马在x轴方向移动两格，那么就在y轴方向上移动一格。类似的如果马在y轴方向移动两格，那么就在x轴方向上移动一格。 题目要求马在中国象棋棋盘上不重复的遍历。根据题意，设计了两种算法（以下分别称为方法一、方法二） 方法一： 马的遍历的过程也就是一个搜索的过程。在刚开始考虑问题的时候，我采用了深度优先搜索的办法，并且加上了回溯。但是在实际的问题实现的过程中却发现当棋盘规模比较小的时候，此方法很有效。可是当棋盘的规模增大时，长时间的运行却求不出结果。这时讨论原因，认为把搜索和回溯写成一个函数，在函数的反复调用的过程中耗费了大量的时间和空间。另外马从起始位置出发走第一步时候，最多有8种可能性，那么走第二步的时候有64种可能性，走第三步的时候就有了512种可能，依次类推可以知道要搜索的路径过多，根本不太可能在短时间内搜索出一条符合题意的路径，而且还要考虑回溯将同样耗费很多的时间。 综合以上的分析，对原先的算法加以改进。在搜索的过程中给程序加上一个启发条件可以有效的缩小搜索范围，并且加快程序的运行速度，另一方面将递归结构改写为非递归结构，去除递归调用的环节加快运行速度。 经过考虑，给搜索过程加上的启发条件为在走下一步棋的时候，考虑下一步棋子落点往各个方向走的可能性的数目，从中选出一个可能性较小的落点，下一步马就落在这个点上。 此算法具有良好的可移植性，可以方便的移植到不同规格的棋盘上。 方法二： 马的遍历过程也可以这样实现：将中国象棋棋盘上的每个点，抽象为图中的一个节点，只要找出包含这棋盘上所有点的哈密顿回路，那么不管马的起始位置在什么地方，都能不重复的走遍这个棋盘上的所有的点，也就是哈密顿回路中所有的点。 但是这个方法不具有良好的可移植性。因为对于找哈密顿回路是世界难题，国际上还没有一种可行的良好的方法。在本程序中的哈密顿回路是通过分割棋盘，然后拼凑而成的，其中经过了无数次的尝试。 三、 具体实现要点： 方法一： 设置一个二维数组a[n1][n1]来代表马在棋盘上走的位置是马遍历的第几步，规定起始位置为第一步。 设置两个一维数组dx[8]、dy[8]来代表x轴和y轴方向的增量。 设置标志flag, 表示这个位置有没有被走过，如果未被走过则为-1，而走过则为0。 设置一维数组v[8]为马走下一步可能落点走下一步的可能性。 设置二维数组d[n1*n1][8] 保存v[8]，方便回溯。 设置二维数组b[n1*n1]保存回溯路线。 在搜索的时候，将原坐标加上各个增量，如果还在棋盘内，那么就走下一步。在这个基础上，再试着向各方向走，如果还在棋盘内，那么可能性就加1。比较这些点走下一步的可能性的大小，从中选择一个可能性最小的作为下一步的落点。然后重复先前的步骤，搜索路径。如果遇到无路可走的时候，就回溯，选择另一条路径搜索。如果搜索到一条遍历路径就输出,进行动态演示。如果没有，则显示“No answer!” 动态演示部分，用graphic.h头文件的函数line画线，函数circle画圆，函数itoa进行整型到字符型的转换，函数outtextxy进行字符输出显示。先画一个中国象棋的棋盘，然后将保存步数的数组a[n1][n1]从1开始输出，每画一个圆，代表一个棋子，并在圆的圆心显示数。在要走下一步时候就按一下空格，显示下一步，直到走遍棋盘。 方法二： “ma .ma”为存储10*9棋盘的哈密顿回路的文件，要注意的是哈密顿回路是以二维数组的形式存储的。 首先将文件读取到二维数组a[10][9]中，找到马遍历的起点在回路中的位置，然后依次遍历哈密顿回路上的各个点，并将各个点为马所走的第几步的数据存储在另一个二维数组b[10][9]中，最后将二维数组b[10][9]输出，动态演示。 此方法的动态演示部分与方法一相同。 四、 测试结果 方法一的程序不能以如下点为起点进行遍历： （x,y）：x为横坐标，也就是棋盘的第几列；y为纵坐标，也就是棋盘的第几行 （2，2） （2，6） （3，4） （4，4） （6，6） （6，8） （7，1） （8，2） 方法二的程序能以任意点为起点进行遍历。 */

风云剑

这是个示例，不针对楼主的问题 #include "stdio.h" const int nSize=6; //棋盘大小 int s=1, x=0, y=0, x0=0, y0=0; //x,y为初始位置 int htry1[8]={ -2, -1, 1, 2, 2, 1, -1, -2 }; int htry2[8]={ 1, 2, 2, 1, -1, -2, -2, -1 }; int board[nSize][nSize]; /* */ void print(void) { //打印一种跳法 for(int i=0; i < nSize; i++) { for(int j=0; j < nSize; j++) printf("%4d", board[i][j]); printf("\n"); } } /* */ void try1(int nStep) { //为第nStep选择合适的位置 for(int k=0; k < 8; k++) { int i=htry1[k]; int j=htry2[k]; if(x + i < nSize && x + i > -1 && y + j < nSize && y + j > -1 && !board[x + i][y + j]) { board[x + i][y + j]=nStep; x=x + i; y=y + j; if(nStep == nSize * nSize && (x - x0) * (x - x0) + (y - y0) * (y - y0) == 5) { printf("第%d种跳法是:\n", s++); print(); } else try1(nStep + 1); board[x][y]=0; x=x - i; y=y - j; } } } /* */ void main(void) { for(int i=0; i < nSize; i++) for(int j=0; j < nSize; j++) board[i][j]=0; //初始化棋盘 board[x][y]=1; try1(2); }

风云剑

还有这个 /* 马步遍历和骑士巡游问题。 马步遍历：在N*N棋盘上某一点开始以马步遍历整个棋盘，但不要求最后回到起点。 骑士巡游：在马步遍历的基础上要求最后回到起点。 */ #include #include //#define _PRINT_FULL_RESULT_ #define _PRINT_SOME_RESULT_ #define MAX_SIZE 20 #define MAX_STEP MAX_SIZE * MAX_SIZE typedef struct { long x; long y; } STEP; static long TryX[]={ -2, -1, 1, 2, 2, 1, -1, -2 }; static long TryY[]={ 1, 2, 2, 1, -1, -2, -2, -1 }; static char Board[MAX_SIZE + 4][MAX_SIZE + 4]; //棋盘，比实际棋盘大4，因为有2格是边界。 //边界为值为-1，空白值为0，有棋子为1。 static char ResultBoard[MAX_SIZE][MAX_SIZE]; //用于输出结果的棋盘。 static STEP Step[MAX_STEP]; //存储每一步的坐标。 static long CurStep; //当前步，第一步是0。 static long Results; //解的个数。 static long Hamilton; //能够回到起点的解的个数。 static long SIZES, STEPS; //实际的棋盘大小和步数。 FILE *fp; //用于记录结果的文件。 /* */ void Init(void) //棋盘初始化。 { for(long i=0; i < SIZES + 4; i++) { for(long j=0; j < SIZES + 4; j++) { Board[i][j]=0; } } for(long i=0; i < SIZES + 4; i++) { Board[i][0]= -1; Board[i][SIZES + 3]= -1; Board[0][i]= -1; Board[SIZES + 3][i]= -1; Board[i][1]= -1; Board[i][SIZES + 2]= -1; Board[1][i]= -1; Board[SIZES + 2][i]= -1; } Results=0; Hamilton=0; } /* */ void Disp(void) //打印棋盘状态 { printf("\n-----------------------------------------\n"); for(long i=0; i < SIZES + 4; i++) { for(long j=0; j < SIZES + 4; j++) { printf("%2d ", Board[i][j]); } printf("\n"); } } /* */ void Result(void) //输出结果 { long dx, dy; dx=Step[CurStep].x - Step[0].x; //判断最后是否回到起点。 dy=Step[CurStep].y - Step[0].y; Results++; #ifdef _PRINT_FULL_RESULT_ printf("\n-------------- %ld --------------\n", Results); fprintf(fp, "\n-------------- %ld --------------\n", Results); #endif if(dx * dx + dy * dy == 5) { Hamilton++; #ifdef _PRINT_FULL_RESULT_ printf("---------- Hamilton %d ----------\n", Hamilton); fprintf(fp, "---------- Hamilton %d ----------\n", Hamilton); #endif } #ifdef _PRINT_FULL_RESULT_ for(long i=0; i < STEPS; i++) { ResultBoard[Step[i].x - 2][Step[i].y - 2]=i + 1; } for(long i=0; i < SIZES; i++) { for(long j=0; j < SIZES; j++) { printf("%4d", ResultBoard[i][j]); fprintf(fp, "%4d", ResultBoard[i][j]); } printf("\n"); fprintf(fp, "\n"); } #elif defined _PRINT_SOME_RESULT_ printf("\rResults: %ld, Hamiltons: %ld", Results, Hamilton); #endif } /* -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 N 0 N 0 0 0 -1 -1 -1 -1 0 N 0 0 0 N 0 0 -1 -1 -1 -1 0 0 0 X 0 0 0 0 -1 -1 -1 -1 0 N 0 0 0 N 0 0 -1 -1 -1 -1 0 0 N 0 N 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 */ void PutIt(void) { long NextX, NextY; for(long i=0; i < 8; i++) //8个方向上尝试， { NextX=Step[CurStep].x + TryX[i]; NextY=Step[CurStep].y + TryY[i]; if(Board[NextX][NextY] == 0) //如果这个位置是空， { Board[NextX][NextY]=1; //放置一个马， ++CurStep; Step[CurStep].x=NextX; Step[CurStep].y=NextY; //计入步数， if(CurStep == STEPS - 1) //如果步数达到最大步数（棋盘全满）， { Result(); //输出结果。 } PutIt(); //再做下一次尝试。 } } Board[Step[CurStep].x][Step[CurStep].y]=0; //如果8个方向都不为空，将这次的马拿走， --CurStep; //并且步数倒退1步。 } /* */ int main(void) { long SX, SY; time_t begin_tm, end_tm; #ifdef _PRINT_FULL_RESULT_ fp=fopen("horse.txt", "w"); #endif printf("Board size ?(SIZE=?):"); scanf("%ld", &SIZES); STEPS=SIZES * SIZES; printf("Start at ?(X=?):"); scanf("%ld", &SX); printf("Start at ?(Y=?):"); scanf("%ld", &SY); begin_tm=time(&begin_tm); Init(); CurStep=0; Step[CurStep].x=SX + 1; //第一步由输入产生。 Step[CurStep].y=SY + 1; Board[Step[CurStep].x][Step[CurStep].y]=1; //棋盘相应位置放置一个马。 #ifdef _PRINT_FULL_RESULT_ fprintf(fp, " - Board size: %d*%d, start at (%d,%d)\n", SIZES, SIZES, SX, SY); #endif PutIt(); //开始遍历。 end_tm=time(&end_tm); #ifdef _PRINT_FULL_RESULT_ fprintf(fp, "\n-------------- END --------------\n"); fprintf(fp, "Results: %ld, Hamiltons: %ld\n", Results, Hamilton); fprintf(fp, "-------------- %ld secs---------------\n", end_tm - begin_tm); #endif printf("\n-------------- END --------------\n"); printf("Results: %ld, Hamiltons: %ld\n", Results, Hamilton); printf("-------------- %ld secs---------------\n", end_tm - begin_tm); fclose(fp); return 0; }

wayne

mathe问的是计数问题，这个比风云剑的要弱很多， 我觉得这里面一定有可行的数学手段

KeyTo9_Fans

此题与走格子路线数统计问题： http://bbs.emath.ac.cn/viewthread.php?tid=517 是同一类问题。 在走格子路线数统计问题里，$4$种走法的位移为： $(0,1)$、$(1,0)$、$(0,-1)$、$(-1,0)$ 我们可以根据这$4$种走法，设计出$C(4,2)=6$种瓷砖： 于是路线数统计问题就变成了铺瓷砖方案数统计问题。 我们从上往下铺瓷砖。 铺的时候需要考虑： 1、新铺的瓷砖和已经铺好的瓷砖的边沿是否匹配。 2、新铺的瓷砖和已经铺好的瓷砖的连通性是否合法。 可以用动态规划算法统计合法的铺瓷砖方案总数。 由于所有走法的坐标变化的绝对值不超过$(1+0)$。 所以边沿状态只有一行格子的信息。 而马踏棋盘有$8$种走法： $(1,2)$、$(2,1)$、$(1,-2)$、$(2,-1)$、$(-1,2)$、$(-2,1)$、$(-1,-2)$、$(-2,-1)$ 一共有$C(8,2)=28$种瓷砖。 所有走法的坐标变化的绝对值不超过$(2+1)$。 所以边沿状态有$2$行加$1$个格子的信息。 即$19$个格子的信息。 信息包括： 1、该格子的两个端口（上一步从哪里跳过来，下一步跳到哪里去）已经确定了几个？用一个数字$0$、$1$、$2$表示。 2、对于标了数字$1$的格子，它们的连通情况。用$1a$、$1b$、$1c$……表示。相同的字母表示目前已经相连，不同的字母表示目前尚未相连。 暂不考虑第$2$条信息，在最坏的情况下第$1$条信息就已经有$3^19$种可能了，这个数有点大。但实际情况会好多少，这个暂时不知道。

xbtianlang

马步遍历，不需要知道是白马还是黑马，只要标出每步的序号即可，比如： 1 22 39 32 3 24 41 30 5 38 35 2 23 40 31 4 25 42 21 90 37 84 33 54 43 6 29 36 87 34 55 50 69 28 53 26 89 20 85 68 83 56 51 44 7 86 67 88 59 74 49 70 27 52 19 78 73 82 71 60 57 8 45 66 81 64 77 58 75 48 11 14 63 18 79 72 61 16 13 46 9 80 65 62 17 76 47 10 15 12 就是一个哈密顿回路。

xbtianlang

在5×6的棋盘上找到8条哈密顿回路 path 1 1 28 21 10 3 22 11 2 29 20 27 30 23 4 9 12 15 8 19 24 7 26 17 14 5 16 13 6 25 18 path 2 1 24 21 10 3 22 11 2 29 20 25 30 23 4 9 12 15 8 19 28 7 26 17 14 5 16 13 6 27 18 path 3 1 28 21 12 3 22 11 2 29 20 27 30 23 4 13 10 15 8 19 24 7 26 17 14 5 16 9 6 25 18 path 4 1 24 21 12 3 22 11 2 29 20 25 30 23 4 13 10 15 8 19 28 7 26 17 14 5 16 9 6 27 18 path 5 1 24 13 6 3 14 5 2 23 12 25 30 11 4 7 10 15 26 19 22 29 20 17 8 27 16 9 28 21 18 path 6 1 22 13 6 3 14 5 2 23 12 21 30 11 4 7 10 15 26 19 24 29 20 17 8 27 16 9 28 25 18 path 7 1 24 13 10 3 14 5 2 23 12 25 30 11 4 9 6 15 26 19 22 29 20 17 8 27 16 7 28 21 18 path 8 1 22 13 10 3 14 5 2 23 12 21 30 11 4 9 6 15 26 19 24 29 20 17 8 27 16 7 28 25 18 这8条实质上可能是其中一、二条的几种对称状态。

风云剑

1 8 11 20 29 10 21 30 3 12 7 2 9 28 19 22 17 24 13 4 25 6 15 18 27 16 23 26 5 14 1 8 11 22 29 10 21 30 3 12 7 2 9 28 23 20 17 24 13 4 25 6 15 18 27 16 19 26 5 14 1 4 11 20 29 10 21 30 3 12 5 2 9 28 19 22 17 24 13 8 25 6 15 18 27 16 23 26 7 14 1 4 11 22 29 10 21 30 3 12 5 2 9 28 23 20 17 24 13 8 25 6 15 18 27 16 19 26 7 14 1 10 19 22 29 18 27 30 9 20 11 2 21 28 23 26 17 6 13 8 3 12 15 24 5 16 25 4 7 14 1 10 19 26 29 18 27 30 9 20 11 2 21 28 25 22 17 6 13 8 3 12 15 24 5 16 23 4 7 14 1 8 19 22 29 18 27 30 9 20 7 2 21 28 23 26 17 6 13 10 3 12 15 24 5 16 25 4 11 14 1 8 19 26 29 18 27 30 9 20 7 2 21 28 25 22 17 6 13 10 3 12 15 24 5 16 23 4 11 14

KeyTo9_Fans

由于是回路，起点在哪里是无所谓的。 此外，每种方案都对应一种反向的方案。 我们不妨认为反向后的方案是同一种方案。 因此，对于$N*(N+1)$的棋盘，方案数如下： $N=1$:?$0$ $N=2$:?$0$ $N=3$:?$0$ $N=4$:?$0$ $N=5$:?$8$ $N=6$:?$?$ $N=7$:?$?$ $N=8$:?$?$ $N=9$:?$?$ ##### $11#,19#,32#$提供的新数据： $N=1$:?$0$ $N=2$:?$0$ $N=3$:?$0$ $N=4$:?$0$ $N=5$:?$8$ $N=6$:?$1067638$ $N=7$:?$34524432316$ $N=8$:?$7112881119092574$ $N=9$:?$?$