马踏棋盘回路计数问题
中国象棋（9×10）棋盘上一只马从任何一个位置出发，没有重复经过所有格子最后返回起始点的不同方案有多少种？如果不需要返回起始点，那么又有多少种方案？
已添加到A193054, A193055 以前试过，相当多，时间太久
以下是转的
＝＝＝＝＝＝＝＝＝＝＝
/*
一、题目：
（马的遍历问题）：设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复的走过棋盘上的每一个位置。
要求：（1）依次输出所走过的各位置的坐标。
（2）最好能画出棋盘的图形形式，并在其上动态的标注行走的过程。
（3）程序能方便的移植到其它规格的棋盘上。
二、设计思想概述：
根据设计的题目要求，首先先要了解中国象棋的棋盘规格以及马的走法。在中国象棋的棋盘上，和国际象棋一样也是8*8的方格，但是与国际象棋相比多出一条楚河汉界，而且按中国象棋中马的走法，马是在棋盘的点上行走的，而不是在格子上。因此在考虑实际问题时可以将点抽象成格子来处理，这样比较好理解和实现。 所以，中国象棋的棋盘可以抽象成10行9列的棋盘，马在格子上行走。
中国象棋中的马是走“日”字形的，也就是如果马在x轴方向移动两格，那么就在y轴方向上移动一格。类似的如果马在y轴方向移动两格，那么就在x轴方向上移动一格。
题目要求马在中国象棋棋盘上不重复的遍历。根据题意，设计了两种算法（以下分别称为方法一、方法二）
方法一：
马的遍历的过程也就是一个搜索的过程。在刚开始考虑问题的时候，我采用了深度优先搜索的办法，并且加上了回溯。但是在实际的问题实现的过程中却发现当棋盘规模比较小的时候，此方法很有效。可是当棋盘的规模增大时，长时间的运行却求不出结果。这时讨论原因，认为把搜索和回溯写成一个函数，在函数的反复调用的过程中耗费了大量的时间和空间。另外马从起始位置出发走第一步时候，最多有8种可能性，那么走第二步的时候有64种可能性，走第三步的时候就有了512种可能，依次类推可以知道要搜索的路径过多，根本不太可能在短时间内搜索出一条符合题意的路径，而且还要考虑回溯将同样耗费很多的时间。
综合以上的分析，对原先的算法加以改进。在搜索的过程中给程序加上一个启发条件可以有效的缩小搜索范围，并且加快程序的运行速度，另一方面将递归结构改写为非递归结构，去除递归调用的环节加快运行速度。
经过考虑，给搜索过程加上的启发条件为在走下一步棋的时候，考虑下一步棋子落点往各个方向走的可能性的数目，从中选出一个可能性较小的落点，下一步马就落在这个点上。
此算法具有良好的可移植性，可以方便的移植到不同规格的棋盘上。
方法二：
马的遍历过程也可以这样实现：将中国象棋棋盘上的每个点，抽象为图中的一个节点，只要找出包含这棋盘上所有点的哈密顿回路，那么不管马的起始位置在什么地方，都能不重复的走遍这个棋盘上的所有的点，也就是哈密顿回路中所有的点。
但是这个方法不具有良好的可移植性。因为对于找哈密顿回路是世界难题，国际上还没有一种可行的良好的方法。在本程序中的哈密顿回路是通过分割棋盘，然后拼凑而成的，其中经过了无数次的尝试。
三、 具体实现要点：
方法一：
设置一个二维数组a来代表马在棋盘上走的位置是马遍历的第几步，规定起始位置为第一步。
设置两个一维数组dx、dy来代表x轴和y轴方向的增量。
设置标志flag, 表示这个位置有没有被走过，如果未被走过则为-1，而走过则为0。
设置一维数组v为马走下一步可能落点走下一步的可能性。
设置二维数组d 保存v，方便回溯。
设置二维数组b保存回溯路线。
在搜索的时候，将原坐标加上各个增量，如果还在棋盘内，那么就走下一步。在这个基础上，再试着向各方向走，如果还在棋盘内，那么可能性就加1。比较这些点走下一步的可能性的大小，从中选择一个可能性最小的作为下一步的落点。然后重复先前的步骤，搜索路径。如果遇到无路可走的时候，就回溯，选择另一条路径搜索。如果搜索到一条遍历路径就输出,进行动态演示。如果没有，则显示“No answer!”
动态演示部分，用graphic.h头文件的函数line画线，函数circle画圆，函数itoa进行整型到字符型的转换，函数outtextxy进行字符输出显示。先画一个中国象棋的棋盘，然后将保存步数的数组a从1开始输出，每画一个圆，代表一个棋子，并在圆的圆心显示数。在要走下一步时候就按一下空格，显示下一步，直到走遍棋盘。
方法二：
“ma .ma”为存储10*9棋盘的哈密顿回路的文件，要注意的是哈密顿回路是以二维数组的形式存储的。
首先将文件读取到二维数组a中，找到马遍历的起点在回路中的位置，然后依次遍历哈密顿回路上的各个点，并将各个点为马所走的第几步的数据存储在另一个二维数组b中，最后将二维数组b输出，动态演示。
此方法的动态演示部分与方法一相同。
四、 测试结果
方法一的程序不能以如下点为起点进行遍历：
（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={ -2, -1, 1, 2, 2, 1, -1, -2 };
int htry2={ 1, 2, 2, 1, -1, -2, -2, -1 };
int board;
/* */
void print(void)
{ //打印一种跳法
for(int i=0; i < nSize; i++)
{
for(int j=0; j < nSize; j++) printf("%4d", board);
printf("\n");
}
}
/* */
void try1(int nStep)
{ //为第nStep选择合适的位置
for(int k=0; k < 8; k++)
{
int i=htry1;
int j=htry2;
if(x + i < nSize && x + i > -1 && y + j < nSize && y + j > -1 && !board)
{
board=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=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=0; //初始化棋盘
board=1;
try1(2);
} 还有这个
/*
马步遍历和骑士巡游问题。
马步遍历：在N*N棋盘上某一点开始以马步遍历整个棋盘，但不要求最后回到起点。
骑士巡游：在马步遍历的基础上要求最后回到起点。
*/
#include <stdio.h>
#include <time.h>
//#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;//棋盘，比实际棋盘大4，因为有2格是边界。
//边界为值为-1，空白值为0，有棋子为1。
static char ResultBoard; //用于输出结果的棋盘。
static STEP 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=0;
}
}
for(long i=0; i < SIZES + 4; i++)
{
Board= -1;
Board= -1;
Board= -1;
Board= -1;
Board= -1;
Board= -1;
Board= -1;
Board= -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);
}
printf("\n");
}
}
/* */
void Result(void) //输出结果
{
long dx, dy;
dx=Step.x - Step.x; //判断最后是否回到起点。
dy=Step.y - Step.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.x - 2].y - 2]=i + 1;
}
for(long i=0; i < SIZES; i++)
{
for(long j=0; j < SIZES; j++)
{
printf("%4d", ResultBoard);
fprintf(fp, "%4d", ResultBoard);
}
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 -100N0N000 -1 -1
-1 -10N000N00 -1 -1
-1 -1000X0000 -1 -1
-1 -10N000N00 -1 -1
-1 -100N0N000 -1 -1
-1 -100000000 -1 -1
-1 -100000000 -1 -1
-1 -100000000 -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.x + TryX;
NextY=Step.y + TryY;
if(Board == 0) //如果这个位置是空，
{
Board=1; //放置一个马，
++CurStep;
Step.x=NextX;
Step.y=NextY; //计入步数，
if(CurStep == STEPS - 1) //如果步数达到最大步数（棋盘全满），
{
Result(); //输出结果。
}
PutIt(); //再做下一次尝试。
}
}
Board.x].y]=0;//如果8个方向都不为空，将这次的马拿走，
--CurStep;//并且步数倒退1步。
}
/* */
int main(void)
{
long SX, SY;
time_tbegin_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.x=SX + 1; //第一步由输入产生。
Step.y=SY + 1;
Board.x].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;
} mathe问的是计数问题，这个比风云剑的要弱很多，
我觉得这里面一定有可行的数学手段 此题与走格子路线数统计问题：
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$种可能了，这个数有点大。但实际情况会好多少，这个暂时不知道。 马步遍历，不需要知道是白马还是黑马，只要标出每步的序号即可，比如：
1223932 3244130 5
3835 2234031 42542
21903784335443 629
368734555069285326
8920856883565144 7
866788597449702752
19787382716057 845
668164775875481114
6318797261161346 9
806562177647101512
就是一个哈密顿回路。 在5×6的棋盘上找到8条哈密顿回路
path 1
1282110 3
2211 22920
273023 4 9
1215 81924
7261714 5
1613 62518
path 2
1242110 3
2211 22920
253023 4 9
1215 81928
7261714 5
1613 62718
path 3
1282112 3
2211 22920
273023 413
1015 81924
7261714 5
16 9 62518
path 4
1242112 3
2211 22920
253023 413
1015 81928
7261714 5
16 9 62718
path 5
12413 6 3
14 5 22312
253011 4 7
1015261922
292017 827
16 9282118
path 6
12213 6 3
14 5 22312
213011 4 7
1015261924
292017 827
16 9282518
path 7
1241310 3
14 5 22312
253011 4 9
615261922
292017 827
16 7282118
path 8
1221310 3
14 5 22312
213011 4 9
615261924
292017 827
16 7282518
这8条实质上可能是其中一、二条的几种对称状态。 1 8112029
102130 312
7 2 92819
22172413 4
25 6151827
162326 514
1 8112229
102130 312
7 2 92823
20172413 4
25 6151827
161926 514
1 4112029
102130 312
5 2 92819
22172413 8
25 6151827
162326 714
1 4112229
102130 312
5 2 92823
20172413 8
25 6151827
161926 714
110192229
182730 920
11 2212823
2617 613 8
3121524 5
1625 4 714
110192629
182730 920
11 2212825
2217 613 8
3121524 5
1623 4 714
1 8192229
182730 920
7 2212823
2617 61310
3121524 5
1625 41114
1 8192629
182730 920
7 2212825
2217 61310
3121524 5
1623 41114 由于是回路，起点在哪里是无所谓的。
此外，每种方案都对应一种反向的方案。
我们不妨认为反向后的方案是同一种方案。
因此，对于$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$:?$?$