马踏棋盘问题，小甲鱼答案有一部分没看明白
马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马走日”的规则将“马”进行移动，要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。
#include <stdio.h>
#define X 8
#define Y 8
int chess;
// 找到下一个可走的位置
int next(int *px, int *py, int count)
{
int x = *px;
int y = *py;
switch(count)
{
case 0:
if (x+2<=X-1 && y-1>=0 && chess == 0)
{
*px = x + 2;
*py = y - 1;
return 1;
}
break;
case 1:
if (x+2<=X-1 && y+1<=Y-1 && chess == 0)
{
*px = x + 2;
*py = y + 1;
return 1;
}
break;
case 2:
if (x+1<=X-1 && y-2>=0 && chess == 0)
{
*px = x + 1;
*py = y - 2;
return 1;
}
break;
case 3:
if (x+1<=X-1 && y+2<=Y-1 && chess == 0)
{
*px = x + 1;
*py = y + 2;
return 1;
}
break;
case 4:
if (x-2>=0 && y-1>=0 && chess == 0)
{
*px = x - 2;
*py = y - 1;
return 1;
}
break;
case 5:
if (x-2>=0 && y+1<=Y-1 && chess == 0)
{
*px = x - 2;
*py = y + 1;
return 1;
}
break;
case 6:
if (x-1>=0 && y-2>=0 && chess == 0)
{
*px = x - 1;
*py = y - 2;
return 1;
}
break;
case 7:
if (x-1>=0 && y+2<=Y-1 && chess == 0)
{
*px = x - 1;
*py = y + 2;
return 1;
}
break;
}
return 0;
}
int setHorse(int x, int y, int tag)
{
int x1 = x, y1 = y, flag = 0, count = 0;
// tag记录轨迹
chess = tag;
// 如果tag等于64退出程序
if (tag == X*Y)
{
return 1;
}
// 如果可以走，那么flag为1
flag = next(&x1, &y1, count);
// 否则尝试其他路径
while (flag == 0 && count < 7)
{
count += 1;
flag = next(&x1, &y1, count);
}
// 递归进入下一个坐标
while (flag)
{
// 返回1表示成功找到落脚点
if (setHorse(x1, y1, tag+1))
{
return 1;
}
// 否则从上一步重新尝试
x1 = x;
y1 = y;
count += 1;
flag = next(&x1, &y1, count);
while (flag == 0 && count < 7)
{
count += 1;
flag = next(&x1, &y1, count);
}
}
if (flag == 0)
{
chess = 0;
}
return 0;
}
int main(void)
{
int i, j;
for (i = 0; i < X; i++)
{
for (j = 0; j < Y; j++)
{
chess = 0;
}
}
// 讲道理，从 (2, 0) 坐标开始计算是比较容易出结果的
// 如果你比较有耐心，或 CPU 特别强劲，可以尝试计算其它坐标
if (setHorse(2, 0, 1))
{
for (i = 0; i < X; i++)
{
for (j = 0; j < Y; j++)
{
printf("%02d", chess);
}
putchar('\n');
}
}
else
{
printf("可惜无解！\n");
}
return 0;
}
在setHOrse函数中while(flag) 迭代如果flag不为0则得到解，如果flag为0则退出循环，应该是无解，函数返回0，为什么中间要有一个 if (flag == 0)
{
chess = 0;
}
并且当我删掉这段的时候，代码多次运行结果都为 无解？ 这段代码的作用是什么 领鱼币 领鱼币x2 正好缺鱼币 本帖最后由 赚小钱 于 2020-5-13 18:26 编辑
马走过的地方会被设置为1(二维数组上)，flag 表示能否找到，下一个位置，如果 flag 表示，在当前位置没有一个可以走的下一个位置，那么应该回退，此时，即表示当前的路是错的，所以应该在二维数组将当前位置设置为0
PS: 算法属于回溯算法。
回溯算法的核心思想是:
选择一个起点出发，沿着某一条路，不断检测是否可用，
如果可用就继续这条路(即深度遍历)
当遇到某种情况，可以确定，这条路行不通的时候，(剪枝函数)
就回头(回溯)，
帮顶。。。
页:
[1]