C语言 找到路径的所有3个角落的棋盘作为一个骑士

lbsnaicq  于 2023-06-05  发布在  其他
关注(0)|答案(3)|浏览(115)
#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个角落的路径),或者我需要改变什么才能得到答案。
三个角的意思是:右上、右下和左下。

wko9yo5t

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指针变量。

vdzxcuhz

vdzxcuhz2#

可能还有其他bug,但这里有一个:

if (board[x][y] != NOT_VISITED || x >= SIDE || y >= SIDE || x < 0 || y < 0)

这个表达式的求值从board[x][y] != NOT_VISITED开始。此时,xy可能具有板外的值。所以你做了越界访问。
在**访问数组之前,请检查xy**的值。
比如:

if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || board[x][y] != NOT_VISITED)

另一个问题是,在检查您是否已经访问过该角落之前,您会检查“找到”。这将给予一些意想不到的打印“发现”。
这一行:

if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || board[x][y] != NOT_VISITED)

应该是函数中的第一个语句。

再来一只虫子

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);

第一行和最后一行使用相同的表达式,即x + 1y - 2。所以你的代码没有覆盖所有8步。一招两次。

我现在运行程序大约20分钟,它仍然没有得到解决方案。

一旦你修复了上面报告的bug,你就可以给予一试了。。但如果你在20分钟内仍然没有解决方案,不要感到惊讶。
问题是,有太多的路径需要检查,即使是现代计算机也会花费相当长的时间来解决这个问题。
考虑一下:

step 1: 8 paths
step 2: 8 paths
step 3: 8 paths
...
step 16: 8 paths

总共281.474.976.710.656条路径....好的,这并不坏,因为许多这些路径将停止之前,得到第16步,因为马离开董事会或返回到相同的位置。但是...有许多路径要检查。
16个步骤可以做到吗?它需要20个步骤。也就是1.152.921.504.606.846.976,或者甚至需要64步!?8^64个路径要检查...
因此,要找到解决方案,您应该以不同的方式思考,而不仅仅是暴力检查。
通过固定要访问的拐角的顺序,并对移动方向设置一些限制,我得出了这个结论:

这个解决方案表明,您可以在20次移动中访问所有4个角落。

plicqrtu

plicqrtu3#

在已经在线程中提到的其他错误之间,你错过了一些关键的东西:检查是否已找到位置,如果找到则返回。这就是为什么函数永远运行。它不应该花费超过30秒的时间来找到解决方案。
下面是代码的更新工作版本:

#include <stdio.h>
#include <stdlib.h>

#define SIDE 8
#define VISITED 1
#define NOT_VISITED 0

#define GOAL_X 0
#define GOAL_Y 7

#define FALSE 0
#define TRUE !FALSE

#define GOAL_FIRST_CORNER_X 0
#define GOAL_FIRST_CORNER_Y 7

#define GOAL_SECOND_CORNER_X 7
#define GOAL_SECOND_CORNER_Y 7

#define GOAL_THIRD_CORNER_X  7
#define GOAL_THIRD_CORNER_Y 0

void printBoard(int board[][SIDE]);

int goHorsie(int board[][SIDE], int x, int y, int step, int* foundFirst, int* foundSecond, int* foundThird);

int main(void)
{
    int board[SIDE][SIDE] = { NOT_VISITED };

    
    int* foundFirstCorner = (int*)malloc(sizeof(int) * 1);
    int* foundSecondCorner = (int*)malloc(sizeof(int) * 1);
    int* foundThirdCorner = (int*)malloc(sizeof(int) * 1);

    *foundFirstCorner = FALSE;
    *foundSecondCorner = FALSE;
    *foundThirdCorner = FALSE;

    if (goHorsie(board, 0, 0, 1, foundFirstCorner, foundSecondCorner, foundThirdCorner))
    {
        printf("Yes, there is a path passing through all the 3 corners without repeating\n");
        printBoard(board);
    }
    else
    {
        printf("No path passing through all corners without repating");
    }

    free(foundFirstCorner);
    free(foundSecondCorner);
    free(foundThirdCorner);
    getchar();
    return 0;
}

/*
Function checks if knight can travel from top left corner and travel through all corners
input: the board, the current x and y, the current step and pointers to ints representing if alredy found the first, second and third corners
output: whether a path was found
*/
int goHorsie(int board[][SIDE], int x, int y, int step, int* foundFirst, int* foundSecond, int* foundThird)
{
    int res = FALSE;

    if (*foundFirst && *foundSecond && *foundThird) // checks if has been to all the corners
    {
        res = TRUE;
    }
    else if (x >= SIDE || y >= SIDE || x < 0 || y < 0 || // out of the board
        board[x][y] != NOT_VISITED) // we were here already!
    {
        res = FALSE;
    }
    else if (x == GOAL_FIRST_CORNER_X && y == GOAL_FIRST_CORNER_Y) // checks if it is in the first corner
    {
        *foundFirst = TRUE;
        board[x][y] = step;
    }
    else if (x == GOAL_SECOND_CORNER_X && y == GOAL_SECOND_CORNER_Y) // checks if is in the second corner
    {

        *foundSecond = TRUE;
        board[x][y] = step;
    }
    else if (x == GOAL_THIRD_CORNER_X && y == GOAL_THIRD_CORNER_Y) // checks if it is in the third corner
    {

        *foundThird = TRUE;
        board[x][y] = step;
    }
    else
    {
        board[x][y] = step;
        step++;
        // changing order here will change the path, because once a condition is verified (TRUE) the rest aren't checked
        res = goHorsie(board, x + 2, y + 1, step, foundFirst, foundSecond, foundThird) ||
            goHorsie(board, x + 2, y - 1, step, foundFirst, foundSecond, foundThird) ||
            goHorsie(board, x + 1, y + 2, step, foundFirst, foundSecond, foundThird) ||
            goHorsie(board, x + 1, y - 2, step, foundFirst, foundSecond, foundThird) ||
            goHorsie(board, x - 2, y + 1, step, foundFirst, foundSecond, foundThird) ||
            goHorsie(board, x - 2, y - 1, step, foundFirst, foundSecond, foundThird) ||
            goHorsie(board, x - 1, y + 2, step, foundFirst, foundSecond, foundThird) ||
            goHorsie(board, x - 1, y - 2, step, foundFirst, foundSecond, foundThird);
        if (!res)
        {
            board[x][y] = NOT_VISITED;
        }
    }

    return res;
}

/*
Function prints the board
input: board to print
output: none
*/
void printBoard(int board[][SIDE])
{
    int i = 0, j = 0;
    for (i = 0; i < SIDE; i++)
    {
        for (j = 0; j < SIDE; j++)
        {
            printf("%3d", board[i][j]);
        }
        printf("\n");
    }
}

相关问题