关于鱼c马踏棋盘的算法,数据结构与算法,技术交流,鱼C论坛

951923615 发表于 2016-3-13 16:38:03

关于鱼c马踏棋盘的算法

#include <stdio.h>
#include <time.h>

#define X 8
#define Y 8

int chess;

// 找到基于(x,y)位置的下一个可走的位置
int nextxy(int *x, int *y, int count)
{
switch(count)
{
case 0:
if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
{
*x = *x + 2;
*y = *y - 1;
return 1;
}
break;

case 1:
if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
{
*x = *x + 2;
*y = *y + 1;
return 1;
}
break;

case 2:
if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
{
*x = *x + 1;
*y = *y - 2;
return 1;
}
break;

case 3:
if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
{
*x = *x + 1;
*y = *y + 2;
return 1;
}
break;

case 4:
if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
{
*x = *x - 2;
*y = *y - 1;
return 1;
}
break;

case 5:
if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
{
*x = *x - 2;
*y = *y + 1;
return 1;
}
break;

case 6:
if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
{
*x = *x - 1;
*y = *y - 2;
return 1;
}
break;

case 7:
if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
{
*x = *x - 1;
*y = *y + 2;
return 1;
}
break;

default:
break;
}

return 0;
}

void print()
{
int i, j;

for( i=0; i < X; i++ )
{
for( j=0; j < Y; j++ )
{
printf("%2d\t", chess);
}
printf("\n");
}
printf("\n");
}

// 深度优先遍历棋盘
// (x,y)为位置坐标
// tag是标记变量，每走一步，tag+1
int TravelChessBoard(int x, int y, int tag)
{
int x1=x, y1=y, flag=0, count=0;

chess = tag;

// 如果tag==X*Y，则完成整个棋盘的遍历
if( tag == X*Y )
{
print();
return 1;
}

flag = nextxy(&x1, &y1, count);
while( 0==flag && count < 7 )
{
count++;
flag = nextxy(&x1, &y1, count);
}

while( flag )
{
if( TravelChessBoard(x1, y1, tag+1) )
{
return 1;
}

x1 = x;
y1 = y;
count++;

flag = nextxy(&x1, &y1, count);
while( 0==flag && count < 7 )
{
count++;
flag = nextxy(&x1, &y1, count);
}
}

if( 0 == flag )
{
chess = 0;
}

return 0;
}

int main()
{
int i, j;
clock_t start, finish;

start = clock();

for( i=0; i < X; i++ )
{
for( j=0; j < Y; j++ )
{
chess = 0;
}
}

if( !TravelChessBoard(2, 0, 1) )
{
printf("抱歉，马踏棋盘失败鸟~\n");
}

finish = clock();
printf("\n本次计算一共耗时: %f秒\n\n", (double)(finish-start)/CLOCKS_PER_SEC);

return 0;
}
其中while( flag )
{
if( TravelChessBoard(x1, y1, tag+1) )
{
return 1;
}

x1 = x;
y1 = y;
count++;
其中x1 = x，y1 = y各代表什么量，如果将
x1 = x ，y1 = y注释掉，依然可以运行，结果却不一样，为何

～风介～ 发表于 2016-3-14 00:05:24

高材生在此！{:10_256:}@阴影中的曙光 @醉酒青牛

ELI_ 发表于 2016-7-1 15:17:59

谢谢分享

psychopath 发表于 2016-7-10 04:28:40

好好学习学习

DAY 发表于 2016-7-11 10:11:43

关于马踏棋盘算法的一些感悟与大家分享一下：
首先明确思路：从一个坐标出发，从下一步八中走法选择一种，走到底，当此路不通时，才回到上一步，走其他方法。
简单点说就是，路通一直走下去，路不通回溯上一步。。understanding！！！！！
还有说一下上面楼主代码的一点小错误，，，变量count<7,这点我不是很认同，我觉得应该改为count<=7吧！！{:5_91:}
说到这里我附上代码（代码中X，Y定义为5，方便计算机计算，当然如果你的计算机配置不错，，可以把X ，Y的值定义为8{:5_97:} ）
#include<cstdio>
#include<ctime>

#define X 5
#define Y 5
int chess={0};

void printChess(){
printf("This is horse Chess:\n");
for(int i=0;i<X;i++){
for(int j=0;j<Y;j++){
printf("%2d ",chess);
}
printf("\n");
}
}

int next(int *x,int *y,int step){
switch(step)
{
   case 0:
         if(*y+2<=Y-1 && *x-1>=0 && chess[*x-1][*y+2]==0)
         {
            *y+=2;
            *x-=1;
            return 1;
         }
         break;
   case 1:
         if(*y+2<=Y-1 && *x+1<=X-1 && chess[*x+1][*y+2]==0)
         {
            *y+=2;
            *x+=1;
            return 1;
         }
         break;
   case 2:
         if(*y+1<=Y-1 && *x+2<=X-1 && chess[*x+2][*y+1]==0)
         {
            *y+=1;
            *x+=2;
            return 1;
         }
         break;
   case 3:
         if(*y-1>=0 && *x+2<=X-1 && chess[*x+2][*y-1]==0)
         {
            *y-=1;
            *x+=2;
            return 1;
         }
         break;
   case 4:
         if(*y-2>=0 && *x+1<=X-1 && chess[*x+1][*y-2]==0)
         {
            *y-=2;
            *x+=1;
            return 1;
         }
         break;
   case 5:
         if(*y-2>=0 && *x-1>=0 && chess[*x-1][*y-2]==0)
         {
            *y-=2;
            *x-=1;
            return 1;
         }
         break;
   case 6:
         if(*y-1>=0 && *x-2>=0 && chess[*x-2][*y-1]==0)
         {
            *y-=1;
            *x-=2;
            return 1;
         }
         break;
   case 7:
         if(*y+1<=Y-1 && *x-2>=0 && chess[*x-2][*y+1]==0)
         {
            *y+=1;
            *x-=2;
            return 1;
         }
         break;
   default:
         break;
}
return 0;
}

int horse(int x,int y,int tag){
int x_t=x,y_t=y;
int flag=0,count=0;
chess=tag;
if(tag==X*Y){
printChess();
return 1;
}
flag=next(&x_t,&y_t,count);
while(!flag && count<=7){
count++;
flag=next(&x_t,&y_t,count);
}
while(flag){
if(horse(x_t,y_t,tag+1))
return 1;
x_t=x,y_t=y,count++;
flag=next(&x_t,&y_t,count);
while(!flag && count<=7){
count++;
flag=next(&x_t,&y_t,count);
}
}
if(!flag)chess=0;
return 0;

}

int main()
{
clock_t begin,end;
begin=clock();
if(!horse(2,0,1)){
printf("The horse Chess is unavailable!");
}
end=clock();
printf("This time used is %lf\n",(double)(end-begin)/CLOCKS_PER_SEC);
return 0;
}

特别说明：因为代码没有加注释，在明白思路的前提下看才会更省力哦。。{:5_109:}

li83126 发表于 2016-7-12 12:33:40

多谢分享{:10_249:}

0洛枫0 发表于 2016-12-2 08:35:43

学习

L丶发表于 2016-12-5 14:45:28

学习学习{:10_254:}

流月飞星 发表于 2016-12-6 10:36:31

{:10_266:}

0洛枫0 发表于 2016-12-8 08:47:13

学习

谦虚求学 发表于 2016-12-25 14:38:22

int x1=x, y1=y, flag=0, count=0;这个你看懂了，你就知道 x1和 y1 表示什么意思了 {:5_91:}

啊dong1992 发表于 2016-12-26 22:21:00

学习下~~

天然萌 发表于 2017-1-13 01:31:39

为什么程序设置横向纵向都为7后，程序运行很久没有结果？不下15分钟，电脑i5处理器，不应该不出结果呀？设置5个，解出来速度很快，这是怎么回事呢？视频上讲的不就50多秒吗？难道我电脑问题？

gascd 发表于 2017-2-10 04:49:16

天然萌发表于 2017-1-13 01:31
为什么程序设置横向纵向都为7后，程序运行很久没有结果？不下15分钟，电脑i5处理器，不应该不出结果呀？设 ...

有可能需要几天解出来。或者是一个月。

常德水鱼村 发表于 2018-9-14 08:50:03

支持楼主！

whdd 发表于 2018-9-16 12:51:49

{:9_219:}

whdd 发表于 2018-9-16 15:38:50

{:9_227:}

whdd 发表于 2018-9-16 15:39:22

{:9_227:}

whdd 发表于 2018-9-16 15:40:01

{:9_236:}

whdd 发表于 2018-9-16 15:40:43

页: [1] 2 3

鱼C论坛's Archiver

关于鱼c马踏棋盘的算法