N皇后问题： 国际象棋中皇后的势力范围覆盖其所在的行、列以及两条对角线，现在考察如下问题：如何在n x n的棋盘上放置n个皇后，使得她们彼此互不攻击 对于任何整数：n>=4，这就是n皇后问题。我们常说的8皇后问题也就是n为8的时候 首先，讲一讲思路，大致思路就是：我们把n个皇后分别放在n行中的第一个位置，然后挨行试探，回溯 譬如，第一个皇后在第一行第一列，试探下一行的皇后，将其放在不会与之前所有皇后冲突的某一列，然后再试探下一行的皇后，再把其放在不会与之前所有的皇后冲突的某一列，若当前皇后找不到一个不冲突的列放置，那就是说明上一个皇后放置的位置不对，我们再退回到上一行，把上一行的皇后位置往后挪，然后继续重复这个过程。 可见， 1、我们需要保存之前暂时确定下来的位置（因为需要判断当前皇后的位置会不会与之前所有的皇后位置起冲突） 2、并且可能需要回溯的做法，也就是把之前的一个位置删除，修改 所以，暂时看来，stack结构非常适合用来保存皇后的坐标，入栈出栈操作很方便
3、判断皇后位置是否冲突，也就是两个皇后的势力范围有没有交集，如（x1,y1） (x2,y2)这两个皇后的坐标，当且仅当： x1 != x2 且 y1 != y2 且 (x1+y1) != (x2+y2) 且 (x1-y1) != (x2-y2) 的时候，这两个皇后才不冲突，所以定义一个皇后类（保存皇后坐标），重载其相等运算符，只要上面四个条件有一个不满足，则我们就认为这两个皇后相等，也就是“相冲突”
4、判断一个皇后是否与之前所有的皇后冲突，就要一一去遍历保存下来的皇后，判断其与当前的位置相等吗，而c++标准库的stack并不支持遍历操作，只能操作栈顶的元素，详情见我的另一篇博客： stl：stack详解 所以这里我们不能用c++标准库的stack来保存坐标（当然自己定义的stack类，添加遍历功能的话还是可以用的），所以我选用了vector保存坐标，因为 1、vector模拟stack的入栈出栈很方便简洁 2、vector进行元素遍历很方便 ，另注意，我们需要对vector保存的queen类元素进行赋值操作，所以还要重载皇后类的赋值运算符 所以定义如下皇后类：
struct Queen { unsigned int x, y; Queen(unsigned int xx = 0, unsigned int yy = 0) :x(xx), y(yy){}; //重载相等与不等运算符 bool operator==(const Queen& qa)const { return(x == qa.x || y == qa.y || (x + y) == (qa.x + qa.y) || (x - y) == (qa.x - qa.y)); } bool operator!=(Queen const& qa)const { return !(*this == qa); } //重载赋值运算符 Queen& operator=(Queen const& qa) { x = qa.x; y = qa.y; return *this; } };问题分析完了，数据结构选用完了，下面就是实现这个算法了，代码与注释如下：
//皇后类 #include<stack> #include<vector> #include<algorithm> void myN_Queens(unsigned int N) { vector<Queen> result; Queen q(0, 0); unsigned int row = 0;//标记当前在操作的行，当操作到了最后一行的后面，就代表可以结束了 while (row < N) { while ((q.y < N) && (result.end() != find(result.begin(), result.end(), q))) //直到在本行找到一个位置或者到了行尾,不然就一直往右移试探本行的下一位置 { q.y++; } if (N > q.y)//如果没到行尾，也就是在本行找到了一个合适的位置 { result.insert(result.end(), q);//把此时的位置入栈 q.x++; q.y = 0;//转到下一行的行首 row++; } else//到了行尾 { q = result[result.size() - 1];//把上一行的坐标再拿出来 result.erase(result.end() - 1);//删除之，其实就是出栈的过程 row--; q.y++;//本行当前位置不合适，继续往后找一个合适的位置 } } for (auto i : result) cout << (i).x << " " << (i).y << endl; cout << "ok" << endl; }4皇后，运行结果：
5皇后，运行结果： 6皇后，运行结果： 7皇后，运行结果： 8皇后，运行结果：
