马踏棋盘算法

问题定义：

将马随机放在国际象棋的Board[0～7][0～7]的某个方格中，马按走棋规则进行移动。，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。

思路：

 利用回溯法的思想，马的走法总共有8，c[8]={1,2,1,2,-1,-2,-1,-2},b[8]={2,1,-2,-1,2,1,-2,-1}，c是横坐标，b是纵坐标。总共有64步，利用这么多的条件就可以得出是否可走的条件。另外关键的一点是递归结束后，把a[i][j]归零，因为这一步是以后其他走法的必经一步，所以要归零。而在八皇后问题中，不存在走回来的，它默认的有个顺序，即数组下标顺序，而马走日是有可能走回来的。

代码实现

#include<stdio.h> 
int m=8,n=8,a[8][8];
int c[8]={1,2,1,2,-1,-2,-1,-2},b[8]={2,1,-2,-1,2,1,-2,-1},num=0,sum=0;
int check(int i,int j){//b,c数组表示每次走的横坐标，纵坐标需要加上的数。a表示整个棋盘。
    if(a[i][j]!=0||i>=m||j>=n||i<0||j<0)//判断是否出界和坐标是否走过 
      return 0;                //num表示走的步数，总共不能超过棋盘总步数64步 
    return 1; 
}
void magosun(int i,int j){
    int k;
    if(num<64){
        for(k=0;k<8;k++){
            if(check(i,j)){
                a[i][j]=1;
                num++;
                magosun(i+c[k],j+b[k]);  
                a[i][j]=0;   //关键地方，因为曾经走过的可能是下一种走法要走的，要归0 
            } 
        }
    }
    else{
        sum++;          //sum表示有多少种做法 
    }
}
int main(){
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            a[i][j]=0;
        }
    } 
    magosun(0,0);   //从0,0坐标开始 
    printf("%d",sum);
}