回溯法之应用

　　归纳整理如下：回溯法作为一种系统看待被求解问题的策略，适用范围很广，但其算法的时间效率通常很低，因此它常常作为一种启发思路的策略，面对新问题未发现其内在规律时可以首先考虑用回溯法思想全盘的分析，以便逐步发现更好的解决方法。

　　回溯法的应用之一是N皇后问题。问题描述：在国际象棋棋盘上放置N个皇后，要求它们不能相吃。国际象棋中的皇后可以吃掉与它处于同一行、同一列及同一斜角线上的棋子。

　　源代码为：

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 #define N 4    //控制棋盘规模
  6 int chessboard[N][N];   //棋盘阵列
  7 int pos[N];    //皇后位置，其中pos[i],i代表行号，pos[i]代表列号
  8 
  9 void Board_Init()  //初始化棋盘
 10 {
 11     for(int i=0;i<N;i++)
 12     {
 13         for(int j=0;j<N;j++)
 14         {
 15             chessboard[i][j]=1;
 16         }
 17     }
 18 }
 19 void Pos_Init()  //初始化列号
 20 {
 21     for(int i=0;i<N;i++)
 22         pos[i]=-1;
 23 }
 24 void Print()  //输出结果
 25 {
 26     for(int i=0;i<N;i++)
 27     {
 28         cout<<"皇后位置：("<<i+1<<","<<pos[i]+1<<")	";
 29         for(int j=0;j<N;j++)
 30         {
 31             if(pos[i]==j)
 32                 cout<<1;
 33             else
 34                 cout<<0;
 35         }
 36         cout<<endl;
 37     }
 38 }
 39 void Input(int i,int j)
 40 {
 41     int n,m;
 42     pos[i]=j;   //记录皇后列号
 43     for(n=j;n<N;n++)
 44         chessboard[i][n]=0;  //行处理
 45     for(m=i;m<N;m++)
 46     {
 47         chessboard[m][j]=0;  //列处理
 48         n=j-i+m;
 49         if(n<N)
 50             chessboard[m][n]=0;   //斜处理
 51         n=j+i-m;
 52         if(n>=0)
 53             chessboard[m][n]=0;
 54     }
 55 }
 56 void Board_Update(int i)
 57 {
 58     Board_Init();
 59     if(i==0)
 60         return;
 61     for(int k=0;k<i;k++)
 62         Input(k,pos[k]);
 63     for(int s=0;s<=pos[i];s++)
 64         chessboard[i][s]=0;
 65     pos[i]=-1;
 66 }
 67 bool Deal(int i,int j)
 68 {
 69     if(i>N-1)
 70         return true;
 71     else if(i<0)
 72         return false;
 73     int column=j;
 74     while(column<N)
 75     {
 76         if(chessboard[i][column]==1)
 77         {
 78             Input(i,column);
 79             break;
 80         }
 81         column++;
 82     }
 83     if(pos[i]<0)
 84     {
 85         int nextColumn=pos[i-1]+1;
 86         Board_Update(i-1);
 87         Deal(i-1,nextColumn);
 88     }
 89     else
 90         Deal(i+1,0);
 91 }
 92 int main()
 93 {
 94     Board_Init();
 95     Pos_Init();
 96     if(Deal(0,0)==false)
 97         cout<<"无解！"<<endl;
 98     else
 99         Print();
100     return 0;
101 }