目录

一、概述

·N皇后问题是什么？

·怎么解决该问题？

二、C++代码实现

一、概述

·N皇后问题是什么？

        N皇后问题是计算机科学中最为经典的问题之一，该问题可追溯到1848年，由国际西洋棋棋手马克斯.贝瑟尔提出了8皇后问题。
        将N个皇后摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆放方式具体是怎么？
        若在棋盘上已放置一个皇后，它实际上占据了哪些位置？以这个皇后为中心，上，下，左，右，左上，左下，右上，右下，8个方向的位置全部被占据。

·怎么解决该问题？

步骤：

1. 标记数组，标记待放置下一个皇后前的状态
2. 第一行内放置第一个皇后，数组初始化都为“*”,有皇后就赋值为“q”
3. 临时01数组，用来存储更新后的标记数组。0初始化数组，1标记当前皇后的攻击范围（8个方向）
4. 临时*q数组，存放更新后的原始数组.
5. 递归的在标志数组内找下一行0的位置，如果有0就放置第二个皇后，没有0全是1的话就说明改行无法放置皇后，回溯到上一行。
   1. 该行无法放置皇后说明上一行皇后放置的位置不合理，需要对上一行内的皇后重新放置
   2. 此时需要回到上一个状态进行重新放置皇后，也就是“1”记录的位置（也就说明了为什么要标记的原因）
   3. 在该情况下放置皇后
6. 重复12345...直至每一行都放上皇后为止

其中，需要使用到的一些数组为：

1. 临时位置ret_temp的数组（是“*”还是“q”）（放置当前皇后之后的结果）
2. 存储最终结果ret的数组（是“*”还是“q”）（最后一次就是把最后的临时结果赋值给最终结果）
3. 访问mark数值，存储每一次访问过的结果（是0还是1）
4. 临时范围数组temp，保存上一次结果，用来回溯（是0还是1）

简言之，过程为：

• 递归：放皇后->记录01位置->放皇后->..放满为止
• 回溯：当准备放下一个皇后时发现改行全是1放不进去了，就回溯到上一行重新放置上一个皇后。
• 此处需要注意的细节问题就是，需要 标记 放置当前皇后之前和之后的位置。

代码讲解：
        借助vector容器来定义数组，vector是一维整型数组，vector>是二维整型数组vector是二维字符数组，vector三维字符数组。

二、C++代码实现

void SetPos(int cn, int n, vector>& mark)
{static int x[8] = {-1,1,0,0,-1,1,-1,1};static int y[8] = {0,0,-1,1,-1,-1,1,1};mark[cn][n] = 1;int newx, newy;for (int i = 1; i < mark.size(); i++){for (int j = 0; j < 8; j++){newx = cn + i * x[j];newy = n + i * y[j];if (newx >= 0 && newx < mark.size() && newy >= 0 && newy < mark.size()){mark[newx][newy] = 1;}}}}
void fn(int cn, int n, vector& ret_temp, vector>& ret,vector>& mark)
{if (cn == n){ret.push_back(ret_temp);return;}//循环第cn行的n列，找可以放置的位置for (int i = 0; i < n; i++){if (mark[cn][i] == 0) //即是可以放置皇后{vector>temp = mark;ret_temp[cn][i] = 'q';//cn行i列所攻击的8个方向的mark置为1SetPos(cn, i, mark);fn(cn + 1, n, ret_temp, ret, mark);ret_temp[cn][i] = '*';mark = temp;}}
}
void main()
{vector> ret;//存放最终结果vector ret_temp;  //存放每一次皇后的放置结果vector> mark; //标识数组int n = 8;//初始化数组for (int i = 0; i < n; i++){mark.push_back(vector());for (int j = 0; j < n; j++)mark[i].push_back(0);ret_temp.push_back("");ret_temp[i].append(n, '*');}fn(0, n, ret_temp, ret, mark);//打印结果for (int i = 0; i < ret.size(); i++){cout << "i = " << i<