#include<stdio.h>
#include<time.h>
#define X 8
#define Y 8
int chess[X][Y];
int c = 1;
//找到基于（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 += 2;
*y -= 1;
return 1;
}
break;
case 1:
if (*x + 2 <= X - 1 && *y + 1 <= Y - 1 && chess[*x + 2][*y + 1] == 0)
{
*x += 2;
*y += 1;
return 1;
}
break;
case 2:
if (*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)
{
*x -= 2;
*y -= 1;
return 1;
}
break;
case 3:
if (*x - 2 >= 0 && *y + 1 <= Y - 1 && chess[*x - 2][*y + 1] == 0)
{
*x -= 2;
*y += 1;
return 1;
}
break;
case 4:
if (*x + 1 <= X - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)
{
*x += 1;
*y -= 2;
return 1;
}
break;
case 5:
if (*x + 1 <= X - 1 && *y + 2 <= Y - 1 && chess[*x + 1][*y + 2] == 0)
{
*x += 1;
*y += 2;
return 1;
}
break;
case 6:
if (*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)
{
*x -= 1;
*y -= 2;
return 1;
}
break;
case 7:
if (*x - 1 >= 0 && *y + 2 <= Y - 1 && chess[*x - 1][*y + 2] == 0)
{
*x -= 1;
*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[i][j]);
}
printf("\n");
}
printf("\n");
}
//深度优先遍历棋盘 (x,y)为起始位置坐标,tag为标记变量,每走一步，tag加一
int Travalchesboard(int x, int y, int tag)
{
int x1 = x, y1 = y, flag = 0, count = 0;
chess[x][y] = tag;
if (tag == X * Y)
{
//打印棋盘
print();
return 1;
}
flag = nextxy(&x1, &y1, count); //打印马的下一个坐标（x1,y1），如果找到flag=1，否则=0；
while (flag == 0 && count < 7)
{
count++;
flag = nextxy(&x1, &y1, count);
}
while (flag)
{
if (Travalchesboard(x1, y1, tag + 1)) //这里这个递推需要好好理解一下，在不满足条件出去一个函数后，tag会减一，从而实现不对则往回返
{
return 1;
}
x1 = x;
y1 = y;
count++;
flag = nextxy(&x1, &y1, count); //出现意外，继续找下一步可走坐标
}
if (flag == 0)
{
chess[x][y] = 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[i][j] = 0;
}
}
if (!Travalchesboard(2, 0, 1))
{
printf("sorry,fault!! \n");
}
finish = clock();
printf("\n time: \n", (double)(finish - start) / CLOCKS_PER_SEC);
return 0;
}
网友评论