(SIZE-2)*(SIZE-2)棋盘骑士游历问题

 

16．(SIZE-2)*(SIZE-2)棋盘骑士游历问题

 

/*(SIZE-2)*(SIZE-2)棋盘骑士游历问题*/

 

#include<iostream>

#include<iomanip>

using namespace std;

 

/*常量定义棋盘大小为（SIZE-2）*（SIZE-2）*/

#define SIZE 9

 

int num1=0;                             //各个位置遍历总数；           

 

/*类go用于实现棋盘的遍历*/

class go{

private:

       int row[8];                            

       int col[8];                          //row，col为下一步位置的八种可能；

       int h[SIZE][SIZE];                   //拓展后棋盘大小；

       int num;                             //一个位置遍历方法总数；

public:

       go(void) {                           //构造函数，实现棋盘初始化等工作； 

              int i,j;

              int r[8]={1,2,2,1,-1,-2,-2,-1};

              int c[8]={-2,-1,1,2,2,1,-1,-2};

              for(int k=0;k<=7;k++){

                     row[k]=r[k];

                     col[k]=c[k];

              }

              num=0;

              for(i=2;i<SIZE-2;i++){

                     for(j=2;j<SIZE-2;j++){

                            h[i][j]=0;

                     }

              }

       }

       ~go(void) {}                         //析构函数；    

       void tryit(int a,int b,int c);       //遍历函数； 

       void print();                        //输出函数；

       void setzero();                      //置零函数； 

};

 

/*数字代表走的步数*/

void go::print()

{

       cout<<"结果"<<num<<":"<<endl;

       for(int i=2;i<SIZE-2;i++){

              for(int j=2;j<SIZE-2;j++){

                            cout<<setw(6)<<h[i][j];

              }

              cout<<endl;

       }

       cout<<endl<<endl<<endl;

}

 

/*一个位置开始的全部遍历,递归回溯主体*/

void go::tryit(int a=2,int b=2,int count=1)

{

       int u,v;

       h[a][b]=count;

       count++;

       for(int i=0;i<8;i++){                               //八个方向上的尝试；

                     u=a+row[i];

                     v=b+col[i];

                     if(u>=2&&u<SIZE-2&&v>=2&&v<SIZE-2&&h[u][v]==0){

                            h[u][v]=count;

                            if(count==(SIZE-4)*(SIZE-4)){           //一种方法结束，输出；

                                   num++;

                                   num1++;

                                   print();

                            }

                            else{                                   //一种方法没完成，回溯；

                                   tryit(u,v,count);                 

                            }

                            h[u][v]=0;                              //完成一种方法后置零；         

                     }

       }

}

 

/*另一个位置开始前的置零工作*/

void go::setzero()

{     int i,j;

       int r[8]={1,2,2,1,-1,-2,-2,-1};

       int c[8]={-2,-1,1,2,2,1,-1,-2};

       num=0;

       for(int k=0;k<=7;k++){

              row[k]=r[k];

              col[k]=c[k];

       }

       for(i=2;i<SIZE-2;i++){

              for(j=2;j<SIZE-2;j++){

                     h[i][j]=0;

              }

       }

}

 

 

int main()

{

       go R;

       for(int i=2;i<SIZE-2;i++){

              for(int j=2;j<SIZE-2;j++){

                     cout<<"初始位置为("<<i<<","<<j<<"),方法如下："<<endl;

                     R.tryit(i,j,1);

                     R.setzero();

              }

       }

       cout<<"遍历总数为："<<num1<<endl;

       return 0;

}