八皇后问题应该是回溯法的教学典范。在本科的时候，有一门课叫面向对象。最后的附录有这个问题的源码。当时根本不懂编程，照抄下来，执行一下出了结果都非常开心，哎。
皇后们的限制条件是不能同行同列，也不能同对角线。
那么显然每一列上都要有一个皇后，仅仅须要用一个一维数组记录皇后在每一行上的位置就能够了。
算法的思想是：从第一行開始，尝试把皇后放到某一列上，能够用一个vis数组保存已经有皇后的列，当找到一个还没有皇后的列时，就尝试着把当前皇后放上，然后看看有没有之前放好的皇后跟这个皇后同对角线，假设同对角线的话，就仅仅能尝试后面的位置。
所有位置都尝试完成之后。说明在前面放的皇后的位置不正确。就要进入传说中的回溯环节，回溯过程中，行是要退回到上一行这是没有疑问的。关键是这一行应该从哪个位置開始继续尝试呢，用递归的话当然不用操心，他会从进入递归的下一位置開始，循环的话呢？应该从当前分配给他的下一个位置開始。同一时候。他之前所在的那一列应该释放掉。
循环的实现还有个问题，什么时候推出？假设仅仅求一组解的话好说，找到解，也就是所有的皇后都归位之后。就退出。可是生成所有解的话。在得到一组解之后，还要做回溯。我一開始对这样的时候的回溯想错了，想着如今应该让第一行的皇后移到下一个位置了，结果少了非常多解。
非常可能前面的几个皇后是不用更改，仅仅调换一下后面的几个就能够了，因此这样的情况的回溯跟尝试失败的回溯是全然一样的。
再来说退出条件。想一下回溯到最后会如何。会到达第一行。第一行将皇后移动到当前放置位置的下一个位置，因此当第一行尝试了所有的列，即下一列就超出棋盘的时候，就应该停止了。
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
int pos[n];
vector<vector<string> > res;
if(n == 0) return res;
vector<string> tpres;
memset(pos, 0, sizeof(pos));
int i=0, j=0, start=0;
bool flag, vis[n];
memset(vis, 0, sizeof(vis));
string line(n, '.'), tpline(n, '.');
while(i<n){
for(j=start;j<n;j++){
if(vis[j]) continue;
flag = true;
for(int k=0;k<i;k++){
if(abs(k-i) == abs(pos[k] - j)){
flag = false;
break;
}
}
if(!flag) continue;
pos[i] = j;
vis[j] = 1;
break;
}
if(j==n){
--i;
vis[pos[i]] = 0;
start = pos[i]+1;
if(i==0&&start>=n) break;
continue;
}else{
i++;
start = 0;
}
if(i == n){
for(i=0;i<n;i++){
line = tpline;
line[pos[i]] = 'Q';
tpres.push_back(line);
}
res.push_back(tpres);
tpres.clear();
--i;
vis[pos[i]] = 0;
start = pos[i]+1;
if(i==0&&start>=n) break;
}
}
return res;
}
};