马踏棋盘问题，修改与校正

Question

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

void print_chess();
int House(int x, int y, int step);
int chess_table[8][8];

int next_step(int* x,int* y,int count)
{
    switch(count)
    {
    case 0:
        if(*x+2<8 && *y+1<8 && chess_table[*x+2][*y+1]==0){
            *x+=2;*y+=1;
            return 1;
        }

        break;
    case 1:
        if(*x+1<8 && *y+2<8 && chess_table[*x+1][*y+2]==0){
            *x+=1;*y+=2;
            return 1;
        }
        break;
    case 2:
        if(*x+2<8 && *y-1>0 && chess_table[*x+2][*y-1]==0){
            *x+=2;*y-=1;
            return 1;
        }
        break;
    case 3:
        if(*x+1<8 && *y-2>0 && chess_table[*x+1][*y-2]==0){
            *x+=1;*y-=2;
            return 1;
        }
        break;
    case 4:
        if(*x-1>0 && *y-2>0 && chess_table[*x-1][*y-2]==0){
            *x-=1;*y=2;
            return 1;
        }
        break;
    case 5:
        if(*x-2>0 && *y-1>0 && chess_table[*x-2][*y-1]==0){
            *x-=2;*y-=1;
            return 1;
        }
        break;
    case 6:
        if(*x-2>0 && *y+1<8 && chess_table[*x-2][*y+1]==0){
            *x-=2;*y+=1;
            return 1;
        }
        break;
    case 7:
        if(*x-1>0 && *y+2<8 && chess_table[*x-1][*y+2]==0){
            *x-=1;*y+=2;
            return 1;
        }
        break;
    default:
        break;
    }
    return 0;
}

int House(int x,int y,int step)
{
    int _x=x;
    int _y=y;
    int flag=0;
    int count=0;
    chess_table[x][y]=step;//默认在（x，y）为step步
    if(step==64)//循环在step=25时退出
    {
        print_chess();//print_chess
        return 1;
    }

    flag=next_step(&_x,&_y,count);//当step小于25说明存在下一部
    while(0==flag && count<7)     //用传地址的方法找下一步落点
    {                             //向八个方向查找
        count ++;
        flag=next_step(&_x,&_y,count);
    }
    while(flag)//找到当前新的值进入下一步
    {
        if(House(_x,_y,step+1))
        {
            return 1;
        }//此处House如果=0及进入下一步后无路可走，则退一步，找当前步新的可能
        _x=x;
        _y=y;
        count++;
        flag=next_step(&_x,&_y,count);
        while(flag==0 && count<7)     //用传地址的方法找下一步落点
    {                             //向剩下方向查找
        count ++;
        flag=next_step(&_x,&_y,count);
    }

    }
    if(0==flag)//flag仍为0，八方找不到下一步
    {
        chess_table[x][y]=0;//否认x，y为step部
    }
    return 0;

}

void print_chess()
{
    for(int i=0;i<8;i++)
    {
            for(int j=0;j<8;j++)
        {
            printf("%d\t",chess_table[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

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

    start =clock();

    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            chess_table[i][j]=0;
        }
    }
    if(!House(2,0,1))
    {
        printf("lost\n");
    }
    finish=clock();
    printf("spend %lf second:",(double)(finish-start)/CLOCKS_PER_SEC);
    return 0;
}

请教，运行一小时无果，检查不出问题，请告知如何修改

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

【您想要解决的问题】： 您想要解决的问题是修改并校正C语言编写的“马踏棋盘”问题的代码。您希望找到代码中的问题，并使其能够成功运行，解决当前运行一小时无果的问题。

【问题出现原因】：

1. 代码中存在逻辑错误，特别是在next_step函数中，对于每个方向的移动，没有正确处理边界条件。
2. House函数中的递归逻辑可能存在问题，导致无法正确找到所有可能的走法。
3. print_chess函数被调用时，step变量的值可能不是最终的走法步数，因为它在递归过程中被修改。

【问题解决方案】：

1. 修正next_step函数中的边界检查，确保不会尝试访问数组之外的元素。
2. 检查House函数的递归逻辑，确保它能够正确地回溯并在找不到走法时返回。
3. 修改print_chess函数的调用时机，确保在找到完整的走法后才调用。

【提供代码】： 由于代码较长，且需要对逻辑进行整体的检查和修正，这里提供一个简化的框架，您可以根据这个框架逐步修正您的代码：

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

#define N 8
#define STEPS 64

int chess_table[N][N];
int visited[N][N];

void print_chess() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", visited[i][j] ? 1 : 0);
        }
        printf("\n");
    }
}

int is_valid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N && !visited[x][y];
}

int knight_move(int x, int y, int step) {
    int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
    for (int i = 0; i < 8; i++) {
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (is_valid(new_x, new_y)) {
            visited[new_x][new_y] = 1;
            if (step == STEPS - 1 || knight_move(new_x, new_y, step + 1)) {
                return 1;
            }
            visited[new_x][new_y] = 0; // Backtrack
        }
    }
    return 0;
}

int main() {
    memset(visited, 0, sizeof(visited));
    clock_t start, finish;
    start = clock();
    if (!knight_move(0, 0, 1)) {
        printf("No solution found.\n");
    }
    finish = clock();
    printf("Time taken: %lf seconds\n", (double)(finish - start) / CLOCKS_PER_SEC);
    print_chess();
    return 0;
}

【代码运行方式】： 您需要一个C语言的编译器，如GCC或Clang，来编译并运行这段代码。在命令行中，您可以使用如下命令编译和运行代码：

gcc -o knight knight.c
./knight

【代码预期运行结果】： 代码将尝试找到马踏棋盘的解决方案，并打印出棋盘的状态。如果找到解决方案，棋盘上的每一步都会被标记为1。

【推荐相关链接】：

1. C语言编程教程
2. 马踏棋盘问题介绍
3. 递归算法基础