找回密码
 欢迎注册
查看: 59626|回复: 69

[擂台] 马踏棋盘回路计数问题

[复制链接]
发表于 2011-5-25 21:30:18 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

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

已添加到A193054, A193055

点评

对于最后返回起点的情况,69楼给出了结果,方案数为19381952998732022416892种。 而不需返回起点的情况比较难,目前还没有求出方案数。  发表于 2015-8-11 17:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-26 21:32:01 | 显示全部楼层
以前试过,相当多,时间太久

以下是转的
===========
/*
一、题目:

(马的遍历问题):设计程序完成如下要求:在中国象棋棋盘上,对任一位置上放置的一个马,均能选择一个合适的路线,使得该棋子能按象棋的规则不重复的走过棋盘上的每一个位置。

要求:(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)

方法二的程序能以任意点为起点进行遍历。

*/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-26 21:35:25 | 显示全部楼层
这是个示例,不针对楼主的问题
#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);
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-26 21:42:38 | 显示全部楼层
还有这个
/*
马步遍历和骑士巡游问题。
马步遍历:在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[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;
}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-27 08:58:59 | 显示全部楼层
mathe问的是计数问题,这个比风云剑的要弱很多,
我觉得这里面一定有可行的数学手段
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-27 14:48:10 | 显示全部楼层
此题与走格子路线数统计问题:

http://bbs.emath.ac.cn/viewthread.php?tid=517

是同一类问题。

在走格子路线数统计问题里,$4$种走法的位移为:

$(0,1)$、$(1,0)$、$(0,-1)$、$(-1,0)$

我们可以根据这$4$种走法,设计出$C(4,2)=6$种瓷砖:

bricks.PNG

于是路线数统计问题就变成了铺瓷砖方案数统计问题。

我们从上往下铺瓷砖。

铺的时候需要考虑:

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$种可能了,这个数有点大。但实际情况会好多少,这个暂时不知道。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-28 22:11:20 | 显示全部楼层
马步遍历,不需要知道是白马还是黑马,只要标出每步的序号即可,比如:
   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
就是一个哈密顿回路。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-30 17:40:43 | 显示全部楼层
在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条实质上可能是其中一、二条的几种对称状态。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-30 21:37:02 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-5-31 14:25:12 | 显示全部楼层
由于是回路,起点在哪里是无所谓的。

此外,每种方案都对应一种反向的方案。

我们不妨认为反向后的方案是同一种方案。

因此,对于$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$:?$?$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 16:41 , Processed in 0.075679 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表