关于马踏棋盘问题的求教

yf_boy

最近看了马踏棋盘问题,突然比较感兴趣,写了段程序,主要思路是这样的
/*Analyse:               
        1.init chessboard
        2.start from (0.0) and try direction from 0
        3.if can_go,go next;if can't,try another direction
        4.if have try all the direction, go back old one and init the current point
        5.if try all the direction of start point(0.0),return can't find, otherwise print the chessboard*/

突然想深入了解这个问题,对于n*n的棋盘,求共有多少种走法.要求用C来实现,不知道大家有什么想法.谢谢.

烈火２５５

本人新手,在此块讨论区人微言轻,本不敢谈什么个人的看法.
但我以前写过类似的程序,
我做的题是8*8,选择任意点为起点马踏完成,记录每一步.
从理论上来说用递归算法是可以的,但是在TC环境下是得不出答案的
因为递归后,一步一步尝试使递归层越陷越深,不知道怎么的就死了
(哪位能告诉我什么原因吗?)
最后我找到一种方法
就是不论以哪个点为始点,我都向外围靠,走完外圈再走内圈
所以不论哪个点为始点都能走通.
至于N*N还没有尝试过.
问一下你的程序运行了吗?

JohnBull

深度优先的递归遍历适于求解那些简单问题，因为情况复杂之后，递归深度太大，将造成堆栈耗尽。
比较复杂的问题适于采用广度优先的遍历。如果情况进一步复杂，还可以在广度节点扩展的时候加入启发函数，进行a*遍历。

方法与深度优先差不多，只不过把栈换成队列即可。

powerpolly

本科的数据结构教材里有这个习题，原题是马的遍历：从任一起点均可无重复遍历棋盘的所有落子点。

算法比较简单，主要考虑遍历策略，因为走下一步最多有八种可能方法，我的遍历策略是择优遍历下一步的下一步所能选择的方法最少的走法，可以想象靠边的点的走法最少，所以遍历路线是从外到内。

我这里有源码，如果楼主需要可以放上来。

yf_boy

谢谢大家帮忙,我也些了个程序,通过限制递归的次数来解决这个问题,在这里我限制的递归次数为100000,我还想知道知道如果求解6*6或者8*8棋盘可能的解的个数,
这是我的程序,写的比较烂,请大家指教
/* 要求：
  1.依次输出所走过的各位置的坐标。
  2.画出棋盘的图形形式，并在其上动态的标注行走过程。
  3.程序能方便的移植到其他规格的棋盘上。*/
/*Analyse:               
        1.init chessboard
        2.start from (0.0) and try from direction 0
        3.if can_go,go next;if can't,try another direction
        4.if have try all the direction, go back old one and init the current point
        5.if try all the direction of start point(0.0),return can't find, otherwise print the chessboard*/
#include <time.h>;

#define xSize 8
#define ySize 8
#define MAXSTEP 100000
int iStep = 0;
long allStep = 0;
int xRecord = 0,yRecord = 0;
int chessboard[xSize][ySize][2];//define chessboard;[0]--count,[1]--direction

int init_chess()//init chessboard
{
        int i,j;
        for(i=0;i<xSize;i++)
                for(j=0;j<ySize;j++)
                {
                        chessboard[j][0]=0;//init count
                        chessboard[j][1]=0;//init direction
                }
}
int print_chess()//print chessboard
{
        int i,j;
        for(i=0;i<xSize;i++)
        {
                for(j=0;j<ySize;j++)
                        printf("%4d",chessboard[j][0]);
                printf("\n\n";
        }
}
int search_x(int count)//search xPoint by count
{
        int i,j;
        for(i=0;i<xSize;i++)
                for(j=0;j<ySize;j++)
                        if(chessboard[j][0]==count)
                                return i;
        return 0;
}
int search_y(int count)//search yPoint by count
{
        int i,j;
        if(count==0)
                return 0;
        for(i=0;i<xSize;i++)
                for(j=0;j<ySize;j++)
                        if(chessboard[j][0]==count)
                                return j;
        return 0;
}
int can_go(int m,int n)//
{
        /*find if it out board or have been gone*/
        if((m>;=0&&m<xSize&&n>;=0&&n<ySize)&&(chessboard[m][n][0] == 0))
                return 1;//can go
        else
                return 0;//can't go
}

int go_back(int i,int j)
{
        int m,n;
        //find old one(m,n)
        m = search_x(chessboard[j][0]-1);
        n = search_y(chessboard[j][0]-1);
        //(m,n) direction++
        ++chessboard[m][n][1];

        //clear(i,j)
        chessboard[j][0] = 0;
        chessboard[j][1] = 0;
       
        //go from(m,n)
        //printf("go back to i=%d,j=%d,count=%d\n",m,n,chessboard[m][n][0]);
        go(m,n);
}
int go(int i,int j)
{
        int level = 0 , count = 0 ;
        int m,n;
       
        level = chessboard[j][1];
        count = chessboard[j][0];
        if(count == (xSize*ySize)-1)
        {
                iStep = -1;
                return;
        }
       
        iStep++;
        allStep++;
        if(iStep >; MAXSTEP)
        {
                xRecord = i;
                yRecord = j;
                iStep = 0;
                return;
        }
        switch(level)
        {
        case 0:
                m = i-2;
                n = j+1;
                break;
        case 1:
                m = i-1;
                n = j+2;
                break;
        case 2:
                m = i+1;
                n = j+2;
                break;
        case 3:
                m = i+2;
                n = j+1;
                break;
        case 4:
                m = i+2;
                n = j-1;
                break;
        case 5:
                m = i+1;
                n = j-2;
                break;
        case 6:
                m = i-1;
                n = j-2;
                break;
        case 7:
                m = i-2;
                n = j-1;
                break;
        default:/*if can't find next go to back to first.*/
                //if(i==0&&j==0)/*search all but can't find*/
                //{
                //        printf("Can't find any trace";
                //        return;
                //}
                go_back(i,j);
                return;       
        }
        if(can_go(m,n) == 1)
        {
                chessboard[m][n][0] = ++count;
                //printf("can go.allStep=%d,iStep=%d,i=%d,j=%d,level=%d,count=%d\n",allStep,iStep,i,j,chessboard[j][1],chessboard[j][0]);
                go(m,n);
        }
        else
        {
                chessboard[j][1] = ++level;
                //printf("can't go.allStep=%diStep=%d,i=%d,j=%d,level=%d,count=%d\n",allStep,iStep,i,j,chessboard[j][1],chessboard[j][0]);
                go(i,j);
        }
}

//#define CLOCKS_PER_SEC 1000000
int main()
{
        int i;
        clock_t time;
        //printf("time=%d",time);
        //Init chessboard

        init_chess();
       
        //go from (0.0)
        //go(0,0);
        do
        {
                go(xRecord,yRecord);
        }while(iStep != -1);
       
        time = clock();
        printf("Search OK,allStep=%d\n,time=%d\n",allStep,time/CLOCKS_PER_SEC);

        //print go trace
        print_chess();
}

aero

如果是5*5的棋盘，结果是多少种啊？

JohnBull

[quote]原帖由 "aero"]如果是5*5的棋盘，结果是多少种啊？[/quote 发表：


我写的程序说有304种.

aero

原帖由 "JohnBull" 发表：


我写的程序说有304种.

^_^，那就对了。偶写的是304种，可是在网上搜的一个论坛上的一篇帖子中提到是1000多种。怕自己错了。

JohnBull都说了，那一定没错了。超相信JohnBull老大的算法。

JohnBull

原帖由 "aero" 发表：


^_^，那就对了。偶写的是304种，可是在网上搜的一个论坛上的一篇帖子种提到是1000多种。怕自己错了。

JohnBull都说了，那一定没错了。超相信JohnBull老大的算法。

OK! Buddy!
right together, wrong together!  :em11:

yuxh

偶怎么得出来有30000多种？

1. #include <stdio.h>;
   
2. 
   
3. struct _steps {
   
4.     int nextX;
   
5.     int nextY;
   
6. }steps[] = {
   
7.     {-2, -1},
   
8.     {-2, 1},
   
9.     {-1, -2},
   
10.     {-1, 2},
    
11.     {1, -2},
    
12.     {1, 2},
    
13.     {2, -1},
    
14.     {2, 1}
    
15. };
    
16. int nSize, nSteps, nCount;
    
17. int startx=0, starty=0;
    
18. char **Board;
    
19. 
    
20. typedef struct stepstack{
    
21.     int x;
    
22.     int y;
    
23.     struct stepstack *next;
    
24. }step;
    
25. 
    
26. step *head = NULL, *tail = NULL;
    
27. step **pStep = & head ;
    
28. 
    
29. int InitBoard()
    
30. {
    
31.     int i, j;
    
32.     Board = (char **)malloc(nSize * sizeof(char *));
    
33.     if(Board == NULL) return -1;
    
34.     for(i = 0; i < nSize; i++) {
    
35.         Board[i] = (char *)malloc(nSize);
    
36.         if(Board[i] == NULL) return -2;
    
37.         for(j = 0; j < nSize; j++)
    
38.             Board[i][j] = 0;
    
39.     }
    
40.     return 0;
    
41. }
    
42. 
    
43. void FindPoint(int a, int b, int x, int y)
    
44. {
    
45.     int i, nextA, nextB, nNum;
    
46.     step  *newstep, *oldstep, *steplist;
    
47. 
    
48.     nNum = 0;
    
49.     for(i = 0; i < 8; i++) {
    
50.         nextA = a + steps[i].nextX;
    
51.         nextB = b + steps[i].nextY;
    
52.         if(nextA < 0 || nextA >;= nSize || nextB < 0 || nextB >;= nSize) continue;
    
53.         if(Board[nextA][nextB] == 1) continue;
    
54. 
    
55.         oldstep = tail;
    
56.         newstep = (step *)malloc(sizeof(step));
    
57.         newstep->;x = a;
    
58.         newstep->;y = b;
    
59.         newstep->;next = NULL;
    
60.         tail = newstep;
    
61.         *pStep = newstep;
    
62.         pStep = &(newstep->;next);
    
63. 
    
64.         Board[a][b] = 1;
    
65.         nSteps++;
    
66.         if(nextA == x && nextB == y) {
    
67.             printf("STEPS[%d]:", nSteps);
    
68.             for(steplist=head; steplist != NULL; steplist = steplist->;next) {
    
69.                 printf("(%d, %d)==>;",  steplist->;x, steplist->;y);
    
70.             }
    
71.             printf("(%d, %d)\n", x, y);
    
72.             nCount++;
    
73.         }
    
74.         else
    
75.             FindPoint(nextA, nextB, x, y);
    
76.         Board[a][b]=0;
    
77.         nSteps--;
    
78.         free(newstep);
    
79.         if(oldstep != NULL) {
    
80.             oldstep->;next = NULL;
    
81.             pStep = &(oldstep->;next);
    
82.             tail = oldstep;
    
83.         }
    
84.         else {
    
85.             head = NULL;
    
86.             pStep = & head ;
    
87.             tail = NULL;
    
88.         }
    
89.     }
    
90.     return;
    
91. }
    
92. 
    
93. main()
    
94. {
    
95.     int i, x, y;
    
96.     printf("Input the chessboard size:");
    
97.     scanf("%d", &nSize);
    
98.     if(InitBoard() < 0) {
    
99.         printf("memory error.\n");
    
100.         exit(-1);
     
101.     }
     
102.     do {
     
103.         printf("Input the target position(x,y):");
     
104.         scanf("%d, %d", &x, &y);
     
105.     }while(x < 0 || x >;= nSize || y < 0 || y >;= nSize);
     
106.     nSteps = 0;
     
107.     nCount = 0;
     
108.     FindPoint(startx, starty, x, y);
     
109.     printf("COUNT:%d\n", nCount);
     
110. }
     

复制代码