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

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

阅读量：4487 次

发布时间：2019-06-08

本文共 2675 字，大约阅读时间需要 8 分钟。

给定一个

输入格式

　　输入的第一行为一个整数

　　接下来

输出格式

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

样例输入1

41 1 1 11 1 1 11 1 1 11 1 1 1

样例输出1

样例输入2

41 0 1 11 1 1 11 1 1 11 1 1 1

样例输出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<
     
      <

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

下面是关键代码：

int valid(int rows,int columns){    for(int i=0;i

这里给出的函数是一个“剪枝函数”，（例如现在走到了第三行，就要循环第一、第二行，找出前两行的皇后存在的位置，然后与第三行的皇后位置比较-----①如果第三行皇后与以上两行任意一个皇后在同一列②或者同一对角线（主对角线或者非主对角线均可以，代码：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
     
      #include
      
       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
       
        >n;    for(int i=0;i
        
         >board[i][h];    }    Queen_w(0,n);    cout<

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

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

转载于:https://www.cnblogs.com/Pinging/p/7818653.html

你可能感兴趣的文章