骑士巡游问题

国际象棋中的马，从任何一个格子开始，是否可以找到一种走法，走遍全部的64个格子，并且要求已经走过的点不要重复地走，但不要求最后回到出发点

采用深度优先，递归调用。

软件结构

1）二维数组表示棋盘，map[m][n]

2）选择一个初始点(0,0)

3）从初始点开始跳跃，跳跃的方法是从当前格可跳跃到的所有方格之中任选一个跳入，如果跳到死胡同里，则退回选择其他未遍历的方格；如果跳满了所有的方格，则成功。

#include <iostream> 
#include <iomanip>  //I/O流控制头文件,setw()的头文件,setw(n) 设域宽为n个字符 
#define N 12        //定义一个宏并赋初值 
using namespace std; 
int b[N][N];    //定义全局性的二维数组保存步数 
bool a[N][N];   //记录某一点是否已经走过 
int num=0;      //记录方案数 
int dx[]={0,1,1,-1,-1,2,2,-2,-2};  
int dy[]={0,2,-2,2,-2,1,-1,1,-1};  //提供每一步的走法 
void solve(int i,int j,int k,bool&ok,int n)  //计算走法 
{
 int m,x1,y1,n1,n2; 
 bool t1,t2;    //布尔变量
 for(m=1;m<=8;m++) 
 { 
     x1=i+dx[m]; 
     y1=j+dy[m]; 
     t1=((x1>=0)&&(x1<n));  //判断x是否在棋盘内 
     t2=((y1>=0)&&(y1<n));  //判断y是否在棋盘内 
     if((t1==true)&&(t2==true)&&(a[x1][y1]==true)) 
	 { 
       a[x1][y1]=false;  //记录该点已经走过 
       b[x1][y1]=k; //k代表第几步
       if(k<n*n)    
	   { 
         solve(x1,y1,k+1,ok,n); 
	   } 
       else 
	   { 
         num++;     //方案数加一 
         ok=true; 
         cout<<"方案"<<num<<" :"<<endl; 
           for(n1=0;n1<n;n1++) 
		   { 
              for(n2=0;n2<n;n2++) 
			  {     
                cout<<setw(4)<<b[n1][n2]; //依次输出经过每一点时的步数 
			  } 
              cout<<endl; 
		   }                                //return; 
	   } 
       a[x1][y1]=true; 
	 } 
 } 
} 
int main() 
{	
   int i,j,row,col,n; 
   bool ok=false ; 
   cout<<"请输入n：";
   cin>>n; 
   for(i=0;i<n;i++) 
   { 
     for(j=0;j<n;j++) 
      a[i][j]=true; 
   } 
 
   cout<<"请输入起始位置的坐标:"; 
   cin>>row>>col; 
   b[row-1][col-1]=1;            //设置起始点 
   a[row-1][col-1]=false; 
   solve (row-1,col-1,2,ok,n);  //调用函数计算结果 
   if(!ok) 
   cout<<"从点("<<row<<","<<col<<")出发无法遍访棋盘的每一个位置"<<endl; 
   system("pause");
   return 0; 
}