回溯法之n皇后问题总结_用回溯法求解n皇后问题的思路

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

一、问题

在nxn格的棋盘上放置彼此不受攻击的n格皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

二、算法与分析

用数组x[i]（1≤i≤n）表示n后问题的解。其中x[i]表示皇后i放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列，所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题，这一隐约束条件可以化成显约束形式。设2个皇后放置位置为(i,j),(k,l)：

显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，n皇后问题的可能解用一个n元向量X=(x1, x2, …, xn)表示，其中，1≤i≤n并且1≤xi≤n，即第i个皇后放在第i行第xi列上

由于两个皇后不能位于同一列上，所以，解向量X必须满足约束条件：

xi≠xj （式1）

若两个皇后摆放的位置分别是(i, xi)和(j, xj)，在棋盘上斜率为-1的斜线上，满足条件i－j= xi－xj，在棋盘上斜率为1的斜线上，满足条件i＋j= xi＋xj，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足约束条件：

|i－xi|≠|j－xj| （式2）

为了简化问题，下面讨论四皇后问题。

四皇后问题的解空间树是一个完全4叉树，树的根结点表示搜索的初始状态，对应Backtrack(1,x);从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。

完全4叉树，我只画了一部分，完整的应该是除了叶结点，每个内部结点都有四个子结点，k表示层数：

回溯法之n皇后问题总结_用回溯法求解n皇后问题的思路

剪枝之后：

回溯法求解4皇后问题的搜索过程：

当然这个图只表示到找到的第一个解，我们知道还有另外一个解。

三、c++代码

变量sum记录可行方案个数，初始为1；

n表示皇后个数，由用户输入；

x[]数组保存问题的解，表示皇后i放在棋盘的第i行第x[i]列,初始时各元素都为0，而我们目的是求出有多少组（x[1],x[2],x[3]……x[n]）满足摆放条件；

output(int x[])函数作用是输出当前找到的一个可行解，只在搜索到叶节点时才会调用；

Place(int k,int x[])函数作用是，对当前行k以上的所有行（即1到k-1行）逐行进行检查，如果该行与上面任何一行相互攻击（即位于同一对角线上了或同列了：abs(i-k)==abs(x[i]-x[k]) || x[i]==x[k]），那么返回false，否则返回true；

Backtrack(int k,int x[])函数表示搜索解空间中第k层子树，k>n时，算法搜索至叶节点，得到一个新的n皇后互不攻击放置方案，那么输出该方案，可行方案数sum加1；k<=n时，当前扩展节点是解空间的内部节点，该节点有x[1],x[2],x[3]……x[n]共n个子节点，对每一个子节点，用函数Place检查其可行性，如果可行，以深度优先的方式递归地对可行子树搜索，如果不可行剪枝。

#include <iostream>
#include <cmath>
using namespace std;
int sum=0;
int n;

int output(int  x[]){
    int i;
    for(i=1;i<=n;i++){
      cout << "(" << i << "," << x[i] << ")" << " ";                                   
    }
    cout << endl;
    return 0;
}


bool Place(int k,int  x[]){
     int i;
     for(i=1;i<k;i++){
     if(abs(i-k)==abs(x[i]-x[k]) || x[i]==x[k])
         return false;                     
     } 
     return true;
     
}
     
     
     
int Backtrack(int k,int  x[]){
    int i;
     if(k>n){//如果是叶节点，直接输出找到的一个解 
          output(x);
          sum++; 
     }
     else{//内部节点，如果满足约束条件，继续深度搜索 。i代表列数，从1到n 
         for(i=1;i<=n;i++){
               x[k]=i;
               if(Place(k,x))
               Backtrack(k+1,x);
         } 
     }
     
     
}

int main(){
    int *x,i;    
    cout << "输入皇后个数:" << endl;
    cin >> n;
    cout << endl;
    x=new int[n+1];
    for(i=0;i<=n;i++){
      x[i]=0;                
    }    
    Backtrack(1,x);
    cout << endl;
    cout << "解的个数：" << sum << endl;
    system("pause"); 
    return 0;
}

以上的程序易于理解，但如果表示成非递归方式，可进一步省去O（n）递归栈空间，使用非递归的迭代回溯法：

#include <iostream>
#include <cmath>
using namespace std;
int sum=0;
int n;

int output(int  x[]){
    int i;
    for(i=1;i<=n;i++){
      cout << "(" << i << "," << x[i] << ")" << " ";                                   
    }
    cout << endl;
    return 0;
}


bool Place(int k,int  x[]){
     int i;
     for(i=1;i<k;i++){
     if(abs(i-k)==abs(x[i]-x[k]) || x[i]==x[k])
         return false;                     
     } 
     return true;
     
}
     
     
     
void Backtrack(int k,int  x[]){
    x[k]=0;
    while(k>0){
        x[k]+=1;
        while(x[k]<=n && !Place(k,x)) x[k]++;   //找到第k行满足约束条件的那一列，以便对子结点继续深度搜索 
        if(x[k]<=n){//找到了满足条件的子结点 
             if(k==n){//是叶结点 
                   output(x);
                   sum++;  
             }else{
                  k++;
                  x[k]=0; 
             }
                    
        }else{//对该行各列已经检查完 
             k--; 
        }  
           
            
    }
          
}

int main(){
    int *x,i;    
    cout << "输入皇后个数:" << endl;
    cin >> n;
    cout << endl;
    x=new int[n+1];
    for(i=0;i<=n;i++){
      x[i]=0;                
    }    
    Backtrack(1,x);
    cout << endl;
    cout << "解的个数：" << sum << endl;
    system("pause"); 
    return 0;
}

运行结果：