八皇后问题

小灰灰 2022-06-11 08:49 286阅读 0赞

**回溯法求解八皇后问题**

n皇后问题：n皇后问题是指在一个n\*n的国际象棋棋盘上放置n个皇后，使得这n个皇后两两不在同一行，同一列，同一条对角线上，求合法的方案数。 如下图是N=5的情况，其中图(a)是一个合法的方案，而图(b)由于有两个皇后在同一条对角线上，因此不是合法的方案。

![Center][] ![Center 1][]

![Image 1][] ![Image 1][]  （a） （b）

对于这个问题，如果采用组合数的方式来枚举每一种情况（从n\*n个位置中选择n个位置），那么将需要 ![Center 2][] 的枚举量，当n=8时，就是54502232次枚举，如果n很大，那么就会无法承受。

但是换个思路，考虑到每行只能放置一个皇后，每列也只能放置一个皇后，那么如果把n列皇后所在的行号依次写出，那么就会是1~n的一个排列。 对于图(a)来说对应的排列是24135，对于图(b)来说就是35142。 于是就只需要枚举1~n的所有排列，查看每个排列对应的方案是否合法，统计合法的方案即可。由于一共有n!个排列，因此当n=8时，需要40320次枚举，该算法比之前优秀很多。

于是可以在全排列的基础上进行求解。生成一个全排列，只需要判断两两皇后是否在同一条对角线上（不在同一行、同一列是显然的）。代码如下：

#include <iostream>
    #include <vector>
    using namespace std;
    
    /*回溯法求解n皇后问题*/
    /*该问题可以归结为全排列问题，即对数字1-8进行全排列，在所有全排列中选择合法的全排列*/
    void generateP(int n, int index, int p[], bool HashTable[], int &count)
    {
           /*
           param
           n:                                皇后的个数
           index:                            当前皇后所在的列号(1 <= index <= n)
           p:                                用来表示当前n皇后的摆放位置
           HashTable:                        表示某个位置是否已经放置皇后
           count:                            合法放置的个数
           */
           if (index == n + 1) {                                            //递归边界，生成一个合法的方案
                  count++;
                  for (int i = 1; i <= n; ++i)                              //显示出合法方案
                         cout << p[i] << " ";
                  cout << endl;
                  return;
           }
           for (int x = 1; x <= n; ++x) {                                   //第x行,相当于皇后编号
                  if (HashTable[x] == false) {                              //第x行还没有皇后
                         bool flag = true;                                  //flag为true表示当前皇后不会和之前的皇后冲突
                         for (int pre = 1; pre < index; ++pre) {            //遍历之前的皇后，index是当前列
                               if (abs(index - pre) == abs(x - p[pre])) {   //这里只需要判断是否在一条对角线上即可，因为转换为全排列，不可能在同一行或同一列
                                      flag = false;                         //与之前的皇后在一条对角线，冲突
                                      break;
                               }
                         }
                         if (flag)                                          //如果可以把皇后放在第x行
                         {
                               p[index] = x;                                //令第index列皇后的行号为x
                               HashTable[x] = true;                         //第x行被占用
                               generateP(n, index + 1, p, HashTable, count);          //递归处理第index+1行皇后
                               HashTable[x] = false;                        //递归完毕，还原第x行为未占用
                         }
                  }
           }
    }
    
    int main()
    {
           const int n = 8;
           int p[n + 1];
           bool HashTable[n + 1] = { false };
           int count = 0;
           generateP(n, 1, p, HashTable, count);
           cout << count << endl;
    }

输出结果为92。

[Center]: https://img-blog.csdn.net/20170803163710733?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvWUZfTGkxMjM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220611/8c7f10ef965b4c06a98cdb363aa267d7.png
[Image 1]: 
[Center 2]: /images/20220611/3cb63a422e854ab7b7bb000063d5fb4f.png