#include <stdio.h>
#define SIDE 8
#define VISITED 1
#define NOT_VISITED 0
#define FALSE 0
#define TRUE !FALSE
void printBoard(int board[][SIDE]);
int goHorsie(int board[][SIDE], int x, int y, int step, int cor1, int cor2, int cor3);
int main(void)
{
int board[SIDE][SIDE] = { NOT_VISITED };
int found = 0;
found = goHorsie(board, 0, 0, 1, 0, 0, 0);
if (found)
{
printf("Yes, there is a path from 0,0 through all corners! Here it is:\n");
printBoard(board);
}
else
{
printf("No path from 0,0 through all corners\n");
printBoard(board);
}
getchar();
return 0;
}
int goHorsie(int board[][SIDE], int x, int y, int step, int cor1, int cor2, int cor3)
{
int res = FALSE, check = 1;
if (board[x][y] != NOT_VISITED //We were here already!
|| x >= SIDE || y >= SIDE || x < 0 || y < 0)
{
res = FALSE;
check = 0;
}
if (x == 7 && y == 7)
{
printf("1)found!\n");
cor1 = 1;
}
if (x == 7 && y == 0)
{
printf("2)found!\n");
cor2 = 1;
}
if (x == 0 && y == 7)
{
printf("3)found!\n");
cor3 = 1;
}
if (cor1 == 1 && cor2 == 1 && cor3 == 1)
{
printf("FOUND ALL!\n");
return TRUE;
}
else if(check == 1)
{
board[x][y] = step;
step++;
res =
goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3) ||
goHorsie(board, x + 2, y + 1, step, cor1, cor2, cor3) ||
goHorsie(board, x + 2, y - 1, step, cor1, cor2, cor3) ||
goHorsie(board, x + 1, y + 2, step, cor1, cor2, cor3) ||
goHorsie(board, x - 2, y + 1, step, cor1, cor2, cor3) ||
goHorsie(board, x - 2, y - 1, step, cor1, cor2, cor3) ||
goHorsie(board, x - 1, y + 2, step, cor1, cor2, cor3) ||
goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3);
if (!res)
{
board[x][y] = NOT_VISITED;
}
}
return res;
}
void printBoard(int board[][SIDE])
{
int i = 0, j = 0;
for (int i = 0; i < SIDE; i++)
{
for (int j = 0; j < SIDE; j++)
{
printf("%3d", board[i][j]);
}
printf("\n");
}
}
我用递归找到了所有三个角的路径。
我运行了大约20分钟的程序,现在仍然没有得到解决方案。
我知道为什么它花了太长时间,但不确定它是否会让我得到答案,我认为它是永远循环。
所以我的问题是,我是否使函数正确,它最终会给予我正确的答案(所有3个角落的路径),或者我需要改变什么才能得到答案。
三个角的意思是:右上、右下和左下。
3条答案
按热度按时间wko9yo5t1#
这个答案建立在用户4386427的答案上,把它们放在一起得到一个完整的解决方案。
对于
int goHorsie(int board[][SIDE], int x, int y, int step, int cor1, int cor2, int cor3);
,您始终使用当前递归中是否找到三个角的信息的副本。如果您实际上找到了一个或两个角,但不是在一个递归调用中找到所有三个角,那么一旦离开递归,这些新发现的真实值就会丢失。在下一次调用中,您可能会找到丢失的角,但没有注意到,因为以前找到的信息丢失了。为了保持信息的发现,你可以切换到指针参数。
int goHorsie(int board[][SIDE], int x, int y, int step, int* cor1, int* cor2, int* cor3);
例如
*cor1 = 1;
为此,您需要在
main()
中引入相应的可引用变量int maincor1 =0;
等从main()调用,如
found = goHorsie(board, 0, 0, 1, &maincor1, &maincor2, &maincor3);
从内心深处
goHorsie(board, x + 1, y - 2, step, cor1, cor2, cor3)
这是相同的代码,但使用与之前相同名称的now指针变量。
vdzxcuhz2#
可能还有其他bug,但这里有一个:
这个表达式的求值从
board[x][y] != NOT_VISITED
开始。此时,x
和y
可能具有板外的值。所以你做了越界访问。在**访问数组之前,请检查
x
和y
**的值。比如:
另一个问题是,在检查您是否已经访问过该角落之前,您会检查“找到”。这将给予一些意想不到的打印“发现”。
这一行:
应该是函数中的第一个语句。
再来一只虫子
第一行和最后一行使用相同的表达式,即
x + 1
和y - 2
。所以你的代码没有覆盖所有8步。一招两次。我现在运行程序大约20分钟,它仍然没有得到解决方案。
一旦你修复了上面报告的bug,你就可以给予一试了。。但如果你在20分钟内仍然没有解决方案,不要感到惊讶。
问题是,有太多的路径需要检查,即使是现代计算机也会花费相当长的时间来解决这个问题。
考虑一下:
总共281.474.976.710.656条路径....好的,这并不坏,因为许多这些路径将停止之前,得到第16步,因为马离开董事会或返回到相同的位置。但是...有许多路径要检查。
16个步骤可以做到吗?它需要20个步骤。也就是1.152.921.504.606.846.976,或者甚至需要64步!?8^64个路径要检查...
因此,要找到解决方案,您应该以不同的方式思考,而不仅仅是暴力检查。
通过固定要访问的拐角的顺序,并对移动方向设置一些限制,我得出了这个结论:
这个解决方案表明,您可以在20次移动中访问所有4个角落。
plicqrtu3#
在已经在线程中提到的其他错误之间,你错过了一些关键的东西:检查是否已找到位置,如果找到则返回。这就是为什么函数永远运行。它不应该花费超过30秒的时间来找到解决方案。
下面是代码的更新工作版本: