目录

一、概述

·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三维字符数组。

写在前面

问：

这样的两个容器内，b内存放的是什么？

答：b内最终存放的是

1

1 2

1 2 3

 而访问b数组的形式为：

	for (int i = 0; i < b.size(); i++)//b.size=3,访问3行{for (int j = 0; j < b[i].size(); j++)//每一行的元素，列cout << b[i][j] << " ";cout << endl;}

二、C++代码实现

/*
*SetPos()设置位置，对01数组添加皇后后进行更新
*cn是当前走到的第几个皇后，n是总皇后个数
*mark是标记数组，定义的是二维整型数组，标记01
*/
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};//(x[],y[]是8个方向的攻击范围)mark[cn][n] = 1;//放置过皇后之后的mark标记：0->1int newx, newy;for (int i = 1; i < mark.size(); i++) //i是外循环，初始化为1是从第二行开始遍历放置皇后{for (int j = 0; j < 8; j++) //j是内循环{newx = cn + i * x[j];//cn：x轴newy = n + i * y[j];//n：y轴，(newx,newy)是更新新皇后的攻击范围if (newx >= 0 && newx < mark.size() && newy >= 0 && newy < mark.size())//当且仅当mark标记数组内的数为0，且(newx,newy)不越界的情况下，放置该皇后，并更新0->1{mark[newx][newy] = 1;}}}}/*
*函数参数说明：
**cn是当前走到的第几个皇后，n是总皇后个数
**ret_temp是临时结果数组，定义的是二维字符数组，标记*和q
**ret是最终结果数组，定义的是三维字符数组，标记*和q
***因为因为ret是一个保存很多二维数组的数组，每一个temp都是一种八皇后解法，
***ret是最终结果，把八皇后二维数组的92所有结果，保存在了ret三位数组中
**mark是标记数组，定义的是二维整型数组，标记01
*/
void fn(int cn, int n, vector& ret_temp, vector>& ret,vector>& mark)
{if (cn == n){ret.push_back(ret_temp);return;}//循环第cn行的n列，找可以放置的位置（哪个是0）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);//递归去下一行cn+1，放皇后//开始回溯ret_temp[cn][i] = '*';//把原来的q->*mark = temp; //把上一次temp->mark}}
}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<