马踏棋盘问题秒出结果

Vision

马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。

国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马走日”的规则将“马”进行移动，要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。

题目：编写代码，实现马踏棋盘的操作，要求使用 1~64 来标注“马”移动的轨迹。

#include <stdio.h>
#include <time.h>
#define N 8                                //国际象棋8行8列
#define POSITIONS 8                //国际象棋中马最多可以走八个位置

int GetNextPosition(int, int, int PositionsList[N][N][POSITIONS*2+2], const int ChessBoard[N][N]);
int sort(int row, int col, int PositionsList[N][N][POSITIONS*2+2], const int ChessBoard[N][N]);
int HorseWalkOverChessBoard(int, int, int ChessBoard[N][N]);

int main()
{
    int row, column, ChessBoard[N][N] = {0};
    time_t StartTime, EndTime;
       
        printf("请输入第一步棋的行和列（1-%d）:", N);
        scanf("%d%d", &row, &column);getchar();
        putchar('\n');
        row--, column--;
    StartTime = time(NULL);       
    if(HorseWalkOverChessBoard(row, column, ChessBoard))
    {
                for(row = 0; row < N; row++)
                {
                        for(column = 0; column < N; column++)
                                printf("%4d", ChessBoard[row][column]);
                        printf("\n\n");
                }
        printf("成功! ");
    }
        else
                printf("迷路了! ");
        printf("用时%d分%d秒。\n\n", ((EndTime=time(NULL))-StartTime)/60, (EndTime-StartTime)%60);
               
    return 0;
}

int HorseWalkOverChessBoard(int row, int col, int ChessBoard[N][N])
{
        int PositionsList[N][N][POSITIONS*2+2] = {0}, path[N*N*2];
    int CanToPoints, NewRow, NewCol, step = 0;
        int *PathPoint = &path[0];
   
    CanToPoints = GetNextPosition(row, col, PositionsList, ChessBoard);
        sort(row, col, PositionsList, ChessBoard);
    ChessBoard[row][col] = 1;
    *PathPoint = row, *(PathPoint+1) = col;
    PathPoint += 2, step++;

    while(step < N*N)
    {
        if(PositionsList[row][col][POSITIONS*2] < PositionsList[row][col][POSITIONS*2+1])
        {
            NewRow = PositionsList[row][col][PositionsList[row][col][POSITIONS*2]];
            NewCol = PositionsList[row][col][PositionsList[row][col][POSITIONS*2] + 1];
            PositionsList[row][col][POSITIONS*2] += 2;
            row = NewRow, col = NewCol;
            CanToPoints = GetNextPosition(row, col, PositionsList, ChessBoard);
                        sort(row, col, PositionsList, ChessBoard);
            if(step == N*N-1 && !ChessBoard[row][col]) CanToPoints = 2;//最后一步不能预判，特别处理
            if(CanToPoints)        //预判该棋格是否可行，减少回溯次数。
            {
                *PathPoint++ = row, *PathPoint++ = col;                //移动轨迹
                ChessBoard[row][col] = ++step;                                //在棋格标记步数
            }
        }
        else
        {
            --step, PathPoint -= 2;
                         if(PathPoint < path) return 0;
            ChessBoard[*PathPoint][*(PathPoint+1)] = 0;        //当前棋格无路可走则删除数据
            row = *(PathPoint-2), col = *(PathPoint-1);        //回溯上一棋格
        }
    }
    return 1;
}

int GetNextPosition(int row, int col, int p[N][N][POSITIONS*2+2], const int ChessBoard[N][N])
{
    int i = 0;
    if(!ChessBoard[row+1][col-2] && row+1 < N  && col-2 >= 0) p[row][col][i++] = row+1, p[row][col][i++] = col-2;//左下
    if(!ChessBoard[row-1][col-2] && row-1 >= 0 && col-2 >= 0) p[row][col][i++] = row-1, p[row][col][i++] = col-2;//左上
    if(!ChessBoard[row+1][col+2] && row+1 < N  && col+2 < N)  p[row][col][i++] = row+1, p[row][col][i++] = col+2;//右下
    if(!ChessBoard[row-1][col+2] && row-1 >= 0 && col+2 < N)  p[row][col][i++] = row-1, p[row][col][i++] = col+2;//右上
    if(!ChessBoard[row-2][col-1] && row-2 >= 0 && col-1 >= 0) p[row][col][i++] = row-2, p[row][col][i++] = col-1;//上左
    if(!ChessBoard[row-2][col+1] && row-2 >= 0 && col+1 < N)  p[row][col][i++] = row-2, p[row][col][i++] = col+1;//上右
    if(!ChessBoard[row+2][col-1] && row+2 < N  && col-1 >= 0) p[row][col][i++] = row+2, p[row][col][i++] = col-1;//下左
    if(!ChessBoard[row+2][col+1] && row+2 < N  && col+1 < N)  p[row][col][i++] = row+2, p[row][col][i++] = col+1;//下右
    p[row][col][POSITIONS*2] = 0;        //p[POSITIONS*2]用于保存指针
    p[row][col][POSITIONS*2+1] = i;        //p[POSITIONS*2+1]保存可到达位置个数
    return p[row][col][POSITIONS*2+1];
}

int sort(int row, int col, int PositionsList[N][N][POSITIONS*2+2], const int ChessBoard[N][N])
{
        int i, j, k, r, c, arr[POSITIONS] = {0};
       
        if(PositionsList[row][col][POSITIONS*2+1] < 2)
                return PositionsList[row][col][POSITIONS*2+1];
        for(i = 0; i < PositionsList[row][col][POSITIONS*2+1]; i += 2)
        {
                j = PositionsList[row][col][i], k = PositionsList[row][col][i+1];
                arr[i/2] = GetNextPosition(j, k, PositionsList, ChessBoard);
        }
        for(i = 1; i < PositionsList[row][col][POSITIONS*2+1]/2; i++)        //插入排序
        {
                r = PositionsList[row][col][i*2];
                c = PositionsList[row][col][i*2+1];
                k = arr[i];
                j = i - 1;
                while((j >= 0) && (arr[j] > k))
                {
                        arr[j+1] = arr[j];
                        PositionsList[row][col][2*(j+1)+1] = PositionsList[row][col][2*j+1];
                        PositionsList[row][col][2*(j+1)] = PositionsList[row][col][2*j];
                        j--;
                }
                arr[j+1] = k;
                PositionsList[row][col][2*(j+1)+1] = c;
                PositionsList[row][col][2*(j+1)] = r;
        }
        return PositionsList[row][col][POSITIONS*2+1];
}


运行效果：

请输入第一步棋的行和列（1-8）:4 3

  12  43  14  33  10  39  48  31

  15  34  11  42  47  32   9  40

  44  13  52  35  38  41  30  49

  53  16   1  46  59  50  37   8

   2  45  58  51  36  25  60  29

  17  54  19  26  57  64   7  24

  20   3  56  63  22   5  28  61

  55  18  21   4  27  62  23   6

成功! 用时0分0秒。

请按任意键继续. . .

FishC_GPT

这段代码是一个解决马踏棋盘问题的实现。运行代码后，会要求输入“马”的起始位置（行和列）。然后，代码会使用递归的方式找到“马”移动的路径，最终输出所有棋盘上的位置编号。

代码中，使用一个8*8的数组ChessBoard来表示棋盘，初始值都为0。使用一个数组PositionsList来保存“马”每个位置可走的下一个位置，并按照一定规则排序。函数GetNextPosition根据当前位置，计算出下一个可走的位置，并返回可到达位置个数。函数sort根据PositionsList数组进行插入排序，以便获取下一个最优的位置。

在HorseWalkOverChessBoard函数中，使用递归来遍历整个棋盘。首先，将当前位置和步数存入path数组中，并将棋盘上该位置标记为步数。然后，调用GetNextPosition函数计算下一个可走的位置，并调用sort函数进行排序。如果还有下一个可走的位置，则选择下一个位置进行递归调用；如果没有下一个可走的位置，则进行回溯。

最后，根据结果输出整个棋盘上的位置编号，以及运行时间。

需注意，代码中使用了一些C语言的特性，如指针和数组。在编写代码时，需要确保变量的数据类型和函数的参数、返回值的类型匹配，以避免编译错误。此外，代码中可能存在一些逻辑上的问题，如变量未初始化、数组越界等，需要在实际使用时加以修正。

如果要优化代码以提高执行速度，可以考虑使用其他算法，如 Warnsdorff 算法或蚁群算法。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。