计蒜课--2n皇后、n皇后的解法（一般操作hhh）

给定一个

输入格式

　　输入的第一行为一个整数

　　接下来

输出格式

输出一个整数，表示总共有多少种放法。

样例输入1

样例输出1

样例输入2

样例输出2

要想理解2n皇后的做法就需要我们先理解n皇后问题。

这里贴上百度的解释：https://baike.baidu.com/item/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98/11053477?fr=aladdin

n皇后问题其实不是很难。它用到思想是算法中的回溯思想。

如果我想找到所有的n皇后的有效解个数，那么我们应该从第一层开始。在这里我准备边讲代码边分析、

开始的时候我们先定义三个全局的数组变量

int num[8][8];
int location[8];
int maxn=-1;

这三个变量分别表示为不同位置的权值（因为这道8皇后问题是为了找到所有情况中权值和最大的那个情况）、这八行数的各行的位置记录、所有情况中的最大值是多少。

这里为什么要定义全局变量呢？我下面会讲到。

之后就要看主函数了，

int main(){
    int k;
    cin>>k;
    while(k--){
        for(int i=0;i<8;i++){
            for(int h=0;h<8;h++){
                cin>>num[i][h];
            }
        }
    Queen(0);
    cout<<maxn<<endl;
    
    }
    
    
}

主函数很简单，就是循环赋值然后调用Queen回溯，然后得出来最大值maxn并输出。

下面是关键代码：

int valid(int rows,int columns){
    for(int i=0;i<rows;i++){
        if(columns==location[i]||abs(rows-i)==abs(columns-location[i])) return 0;
        
    }
    return 1;
}

这里给出的函数是一个“剪枝函数”，（例如现在走到了第三行，就要循环第一、第二行，找出前两行的皇后存在的位置，然后与第三行的皇后位置比较-----①如果第三行皇后与以上两行任意一个皇后在同一列②或者同一对角线（主对角线或者非主对角线均可以，代码：abs(rows-i)==abs(columns-location[i])），那么返回0，否则说明第三行的这个位置可以放皇后，就返回1）

此时我们知道了“剪枝函数”也就体现了回溯算法的思想了，因为按照我的理解，回溯就是（完全遍历的所有情况-大部分一开始就不满足条件的情况），所以这个函数其实很重要。

之后我们写出来回溯的函数

int Queen(int row){
    if(row == 8) {
        int current_max=0;
        for(int i=0;i<8;i++){
            current_max+=num[i][location[i]];
        }
    maxn=max(current_max,maxn);
    }
    else{
        for(int n=0;n<8;n++){
            if(valid(row,n)){
                location[row]=n;
                Queen(row+1);
            }
        }
    }
}

在这个函数中，我们传入的row是行号，第一个if是跳出循环的条件——当row循环了八次之后完成循环（也就说明这八次循环得到了一种最优解的情况），else里面是循环八次分别找每一行的符合要求的解。

如果满足valid，那么记录第row行的列号，然后递归到下一层函数。

*****这里我们为什么要定义全局变量呢？这里，我们要知道程序在计算的时候是按照顺序执行的。只有8^8种情况中的第一种结束了，才会计算下一种情况。所以这个全局变量会被每一个子问题分别使用，并且下一个子问题会不断覆盖上一个子问题的全局变量中的值。

之后我们有了n皇后的基础之后，解决2n或者多n皇后问题就很简单了。

在2n皇后的要求中（我开始写的计蒜课的算法题目），我们知道它多了一个条件，就是我令一部分位置不能放棋子。这个时候我们就要在　Queen函数中循环列的时候判断一下这个位置是否可用，只有可用的时候才能进入判读。

而2n皇后其实就是先计算第一个n皇后，然后得出来一个n皇后的表，之后在计算另一个皇后，这个时候第二种皇后的情况就要除去第一个n皇后已经放入的位置。就是相当于那个”能否使用表”稍微复杂了一点而已。。。

这里放上代码：

#include<iostream>
#include<cmath>
using namespace std;
int board[8][8];
int all=0;
int black_location[8];
int white_location[8];
int w_valid(int rows,int columns){
    for(int i=0;i<rows;i++){
        if(columns==white_location[i]||abs(rows-i)==abs(columns-white_location[i])) return 0;
        
    }
    return 1;
}

int b_valid(int rows,int columns){
    for(int i=0;i<rows;i++){
        if(columns==black_location[i]||abs(rows-i)==abs(columns-black_location[i])) return 0;
        
    }
    return 1;
}
int Queen_b(int cur,int n){
    if(cur==n){
        all++;
    }
    else{
        for(int h=0;h<n;h++){
            if(h==white_location[cur]||board[cur][h]==0) continue;
            else{
                if(b_valid(cur,h)){
                    black_location[cur]=h;
                    Queen_b(cur+1,n);
                }
            }
        }
    }
}

int Queen_w(int cur,int n){
    if(cur==n) {
         Queen_b(0,n);
    }
    else{
        for(int i=0;i<n;i++){
            if(board[cur][i]==0) continue;
            if(w_valid(cur,i)){
                white_location[cur]=i;
                Queen_w(cur+1,n);
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int h=0;h<n;h++)
            cin>>board[i][h];
    }
    Queen_w(0,n);
    cout<<all;
}

多注意细节就好，代码量有点大，有什么不懂的地方大家给我留言。

--------------------------------------------------------------------------------------Made By Pinging