八皇后问题

转自我的CSDN博客： http://blog.csdn.net/njdragonfly

8皇后问题和由他推广得到的N皇后问题来源于国际象棋的玩法，因为皇后所在的位置可以纵向、横向、两个斜向四个方向的“捕捉”，所以8皇后问题就是要求如何布置8个皇后在8*8的棋盘上而使他们互相无法“捕捉”。也就是说不存在两个皇后同行或同列，或在同一斜线上。而N皇后问题就是如何布置N个皇后在N*N棋盘里使不存在两个皇后在同行同列和同一斜线上。因为8皇后问题可以归为N皇后问题，所以下面按照N皇后问题来进行讨论。

解决N皇后问题的最好最著名的算法就是回溯法。在算法设计的基本方法中，回溯法是最一般的方法之一。在那些涉及到寻找一组解的问题或者求满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

一般回溯法可用递归来实现，下面是从网上找来的一个非常典型的递归程序结构。

procedure try(i:integer);
var
begin
     if i>n then 输出结果
     else   for j:=下界 to 上界 do
          begin
           x[i]:=h[j];
           if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;
        end;
end;

说明：
i是递归深度；
n是深度控制，即解空间树的的高度；
可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层，直到最后的叶子输出结果。

回到N皇后问题的解决来，看看如何用回溯法解。首先找出解空间：给棋盘的行和列都编上1到N的号码，皇后也给编上1到N的号码。由于一个皇后应在不同的行上，为不失一般性，可以假定第i个皇后将放在第i行上的某列。因此N皇后问题的解空间可以用一个N元组（X1，X2，…..Xn）来表示，其中Xi是放置皇后i所在的列号。这意味着所有的解都是N元组（1，2，3，…….，N）的置换。解空间大小为N！。其次我们看约束条件：因为解空间已经给我们排除了不在同一行（因为每个皇后分别已经对应不同的行号）的约束条件。我们要判断的是不在同一列和不在同一斜线的约束。因为Xi表示皇后所在的列号，所以如果存在X（k）=X（i）那么肯定存在第k个皇后和第i个皇后同列。所以不同列的判段条件是X（k）！=X（i），1<k<i 。又因为同一斜线的特征是要么行号和列号之和不变（右高左低）要么是行号和列号只差相等（左高右低），所以同斜线的判断条件是 i+X（i）=  k+X（k) 或 i-X(i) =k-X(k),两式合并得 |X(i)-X(k)|=|i-k|  。

编程基本思路：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。

#include <iostream.h>
#include <math.h>
/*检查可不可以放置一个新的皇后*/
bool place(int k, int *X)
{
        int i;
        i=1;
        while(i<k)
        {
                  if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))
                  return false;
                  i++;
         }
        return true;
}

/*求解问题的所有解*/
void Nqueens(int n,int *X)
{
       int k;
       X[1]=0;k=1;
       while(k>0)
       {
             X[k]=X[k]+1; //不断的在解空间里从小到大的试探

             while((X[k]<=n)&&(!place(k, X)))
                      X[k]=X[k]+1;                     //不符合条件的马上再取解空间的下一个值来试探。

             if(X[k]<=n)   //找到了一个位置，而且是合法的
                  if(k==n)   //是不是最后一个皇后，若是则得出一个完整解
                 {
                          for(int i=1;i<=n;i++)
                          cout<<X[i]<<" ";
                          cout<<"/n";
                   }
                  else    //若不是最后一个皇后，则给下一个皇后找位置
                 {
                          k=k+1;
                          X[k]=0;
                 }

             else      k=k-1;  //若是找了全部的列都无法放置某个皇后，则回溯到上一个k的情况，让上一个k再往下试
        }

}
/*主函数*/

void main()
{
        cout<<"|--------------N皇后问题--------------|"<<endl;
        cout<<"|-------------------------------------|"<<endl<<endl;
        int n;
        int *X;
        int i;
        while(i)
       {
                 cout<<"请输入皇后的个数:";
                 cin>>n;
                 X=new int[n];
                 cout<<"问题的解有:"<<endl;
                 Nqueens(n,X);
                 cout<<"Press<1> to run again"<<endl;
                 cout<<"Press<0> to exit"<<endl;
                 cin>>i;
         }