马踏棋盘问题（又称骑士周游或骑士漫游问题）

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

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

1 2 3 4 5 6 7 8都是马此刻可以走的位置，马踏棋盘问题的一个实现如下：

请教一下以下代码实现哪个步骤错了？


#include
int sum = 0;
int PD(int M[8][8],int n,int m);
int PD(int M[8][8],int n,int m)
{
    int i,j;
    
    //判断8个方向的棋点是否能下。 
    if(n-2 >= 0 && m-1 >= 0)
    {
        if(M[n-2][m-1] == 0)
        {
        M[n-2][m-1] = 1;
        PD(M,n-2,m-1);
        }
    }
    
    
    if(n-2 >= 0 && m+1 < 8)
    {
        if(M[n-2][m+1] == 0)
        {
        M[n-2][m+1] = 1;
        PD(M,n-2,m+1);
        }
    }

    if(n-1 >= 0 && m+2 < 8)
    {
        if(M[n-1][m+2] == 0)
        {
        M[n-1][m+2] = 1;
        PD(M,n-1,m+2);
        }
    }
    
    
    if(n+1 < 8 && m+2 < 8)
    {
        if(M[n+1][m+2] == 0)
        {
        M[n+1][m+2] = 1;
        PD(M,n+1,m+2);
        }
    }
    
    if(n+2 < 8 && m+1 < 8)
    {
        if(M[n+2][m+1] == 0)
        {
        M[n+2][m+1] = 1;
        PD(M,n+2,m+1);
        }
    }
    
    if(n+2 < 8 && m-1 >= 0)
    {
        if(M[n+2][m-1] == 0)
        {
        M[n+2][m-1] = 1;
        PD(M,n+2,m-1);
        }
    }
    
    
    if(n+1 < 8 && m-2 >= 0)
    {
        if(M[n+1][m-2] == 0)
        {
        M[n+1][m-2] = 1;
        PD(M,n+1,m-2);
        }
    }
    
    
    if(n-1 >= 0 && m-2 >= 0)
    {
        if(M[n-1][m-2] == 0)
        {
        M[n-1][m-2] = 1;
        PD(M,n-1,m-2);
        }
    }
    
    if(sum == 64)
    {
        printf("%d行%d列\n",n+1,m+1);
        return;
    }
    
    for(i = 0;i < 8; i++)
    {
        for(j = 0;j < 8; j++)
        {
            if(M[i][j] == 1)
            sum++;
        }
    }

    if(sum != 64)
    {
        M[n][m] = 0;
        sum = 0;
        return;
    }

    return 0; 
    
}

int main()
{
    int M[8][8];
    int n,m;

//数组初始化为0  
    for(n = 0;n < 8; n++)
    {
        for(m = 0;m < 8; m++)
        {
        M[n][m] = 0; 
        }
    }

    printf("请选择起始位置 '行 列':");
    scanf("%d %d",&n,&m);
    
    M[n-1][m-1] = 1;
    
    PD(M,n-1,m-1);
    return 0;
}

在该代码实现中，没有判断马是否已经遍历了所有的棋格。在程序中，当sum等于64时，只输出当前所在的行和列，但没有终止程序的执行，因此程序会继续执行，而且在程序中没有添加其他的终止条件，导致程序无限循环。应该在sum等于64时，添加终止程序的代码，例如使用return语句终止程序的执行。另外，也应该将sum的计数重置为0，以便重新计数从当前位置开始能够遍历的棋格数目。

这篇文章：马踏棋盘算法(骑士周游问题)——回溯法也许有你想要的答案，你可以看看
除此之外, 这篇博客: 初学C语言【14】寻找单身狗中的方法二：异或（两数，相同为 0 ，相异为 1 ），整个数组全部元素进行异或，出现两次的元素异或为“0”，最后的结果不可能是零（否则没有单身狗了，不可能，我就是单身狗），寻找数组元素异或后二进制为 1 的位置（区别），然后将该数组分为两组，一组该二进制位全为 1 ，将数组中该位为1的所有数异或，因为数组中相同的数异或为0，仅留下该位为1的单身狗数；另外一组该位全为0，同理，该位为0的所有数异或，最后仅留下该位为0的单身狗数。部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

#include<stdio.h>
void finddog(int a[], int sz, int* num)
{
    int i = 0;
    int pos = 0;
    int ret = 0;
    //遍历数组，结果为两个不同数的异或。
    for (i = 0; i < sz; i++)
    {
        ret ^= a[i];
    }
    //寻找这两个不同数异或结果的一个位为 1 的位
    for (pos = 0; pos < 32; pos++)
    {
        if (((ret >> pos) & 1) == 1)//整型 32 位，从低位向高位依次遍历
        {
            break;     //pos记录二进制位为 1 的数
        }
    }
    for (i = 0; i < sz; i++)
    {
        //找到数组中pos位为1的数，并进行异或
        if (((a[i] >> pos) & 1) == 1)
        {
           num[1] ^= a[i];
        }
        //找到数组中pos位为0的数，并进行异或
        else
        {
            num[0] ^= a[i];
        }
    }
}
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 2, 1, 3 };
    int num[2] = { 0 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    finddog(arr, sz, num);
    printf("%d %d\n", num[0], num[1]);
    return 0;
}