论坛 › 综合交流区 › 马踏棋盘问题秒出结果

Vision 发表于 2023-11-29 21:26:31

马踏棋盘问题秒出结果

本帖最后由 Vision 于 2023-11-30 06:22 编辑

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

国际象棋的棋盘为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, const int ChessBoard);
int sort(int row, int col, int PositionsList, const int ChessBoard);
int HorseWalkOverChessBoard(int, int, int ChessBoard);

int main()
{
    int row, column, ChessBoard = {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);
                        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)
{
        int PositionsList = {0}, path;
    int CanToPoints, NewRow, NewCol, step = 0;
        int *PathPoint = &path;
   
    CanToPoints = GetNextPosition(row, col, PositionsList, ChessBoard);
        sort(row, col, PositionsList, ChessBoard);
    ChessBoard = 1;
    *PathPoint = row, *(PathPoint+1) = col;
    PathPoint += 2, step++;

    while(step < N*N)
    {
      if(PositionsList < PositionsList)
      {
            NewRow = PositionsList];
            NewCol = PositionsList + 1];
            PositionsList += 2;
            row = NewRow, col = NewCol;
            CanToPoints = GetNextPosition(row, col, PositionsList, ChessBoard);
                        sort(row, col, PositionsList, ChessBoard);
            if(step == N*N-1 && !ChessBoard) CanToPoints = 2;//最后一步不能预判，特别处理
            if(CanToPoints)        //预判该棋格是否可行，减少回溯次数。
            {
                *PathPoint++ = row, *PathPoint++ = col;                //移动轨迹
                ChessBoard = ++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, const int ChessBoard)
{
    int i = 0;
    if(!ChessBoard && row+1 < N&& col-2 >= 0) p = row+1, p = col-2;//左下
    if(!ChessBoard && row-1 >= 0 && col-2 >= 0) p = row-1, p = col-2;//左上
    if(!ChessBoard && row+1 < N&& col+2 < N)p = row+1, p = col+2;//右下
    if(!ChessBoard && row-1 >= 0 && col+2 < N)p = row-1, p = col+2;//右上
    if(!ChessBoard && row-2 >= 0 && col-1 >= 0) p = row-2, p = col-1;//上左
    if(!ChessBoard && row-2 >= 0 && col+1 < N)p = row-2, p = col+1;//上右
    if(!ChessBoard && row+2 < N&& col-1 >= 0) p = row+2, p = col-1;//下左
    if(!ChessBoard && row+2 < N&& col+1 < N)p = row+2, p = col+1;//下右
    p = 0;        //p用于保存指针
    p = i;        //p保存可到达位置个数
    return p;
}

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


运行效果：

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

1243143310394831

153411424732   940

4413523538413049

5316   146595037   8

   245585136256029

175419265764   724

20   3566322   52861

551821   4276223   6

成功! 用时0分0秒。

请按任意键继续. . .

FishC_GPT 发表于 2023-11-29 21:26:48

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

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

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

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

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

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

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

查看完整版本: 马踏棋盘问题秒出结果