背景分析
这个问题自提出以来，许多数学家纷纷给出了自己的答案，在计算机出现后，解法渐渐尘埃落定。我尝试着分析下这个问题的要点。令棋盘为chess[8][8]。行为row[8]，列为column[8]
斜边判定为hypotenuse[8][8]
1、 任何两个皇后不能再同一条横线上
意味着每一行只能有一个皇后，即对于行i，row[i]=0，才能落子
2、 任何两个皇后不能再同一条纵线上
意味着每一列只能有一个皇后，即对于列i，column[i]=0，才能落子
3、 任何两个皇后不能再同一条斜线上
意味着每一斜边只能有一个皇后，即对于点i、j，只有
算法思路出来了，我们可以做些优化。
1、 是不是每个点都需要去判断？
不是，既然没行只能一个且必须一个，因此可以一次判断一行。
2、 能不能同时确定行和列？
不行，你无法同时假定两个互相关联的变量。
3、 终止条件？
搜索出所有的可能值。
因为可以一次前进一行，且每次处理的方法都一样，处理完之后还有回到上一部，尝试下一个点。因此可以使用回溯的思想，递归的算法结构。
此外对于强大的计算机，穷举也是解决之道。
最后我也会介绍一种位运算的方法。
递归
先上代码。
int eightQueen1(int n){if(n == N)return 1;int result = 0;for(int i = 0;i<N;i++){if(column[i]||hypotenuse1[i-n+N]||hypotenuse2[i+n])continue;column[i]=hypotenuse1[i-n+N] = hypotenuse2[i+n] = 1;result += eightQueen1(n+1);column[i]=hypotenuse1[i-n+N] = hypotenuse2[i+n] = 0;}return result;}
这是典型的递归思路，在这里只需要考虑列冲突和斜边冲突，见图1
图1
现有一皇后在(1,2)处。那么三条虚线经过的位置都不能放棋盘，这些地方有什么特点呢？对于竖线，为column[1]=1，对于左斜线为，hypotenuse1[1-2]=1,对于右斜线为hypotenuse[1+2]=1。
由于数组索引必须为正，因此我让hypotenuse1[1-2+N]=1。
因此判断一个点能不能放皇后，要满足以下条件：column[i]=hypotenuse1[i-n+N] = hypotenuse2[i+n] = 0。I为行，n为列。
穷举
对于这类问题，还有个朴素的方法，即罗列出所有的排列。一个个的尝试，选取所有符合要求的排列。代码见下
int eightQueen2(int n){vector<int> queen(N);for_each(queen.begin(),queen.end(),[](int &value){static int a = 0;value = a++;});int result = 0;while(next_permutation(queen.begin(), queen.end())){set<int> s1,s2;int i =0;for(const auto& qe : queen){s1.insert(qe + i);s2.insert(qe – i++);}if(s1.size() == N && s2.size() == N)++result;}return result;}
Queen是皇后在每一行的位置。比如queen[0]=1，代表在第0行第1列。S1是用来判断右斜线无冲突。比如queen[0] =2,queen[1] =1。由于2+0 = 1+1。因此s1.Size()< N，这种排列不满足条件。S2是用来判断左斜线无冲突。
这种方法来自于一个python解法的变异。Python解法见
from itertools import *cols = range(8)for vec in permutations(cols): if (8 == len(set(vec[i]+ifor i in cols))== len(set(vec[i]-i for i in cols))):print vec
位运算
有一种巧妙的方法是位运算，先上代码。
int eightQueen3(int row, int ld, int rd){int ret = 0, pos = ((1<<N)-1) & ~(row | ld | rd);for(int k = pos & (-pos);pos;pos -= k, k = pos & (-pos)){ret += eightQueen3(row + k ,(ld + k)<<1,(rd+k)>>1);}return row+1 == (1<<N) ? 1:ret;}
Row = 10000000，代表位置1上不能放皇后，ld =00000001，代表最后不能放皇后。Rd = 00000010，，代表倒数第2个位置不能放皇后。那么能放的位置pos = ((1<<N)-1) & ~(row | ld | rd)。k = pos& (-pos)。表示k为下一个可以放的位置。Row+k表示k所在位置也不能放，(ld+k)<<1和(rd+k)>>1即是斜边不能放。
总结
八皇后问题是新手常见问题。解法也有多种，上面就介绍了集中代表性的解法，仅供参考。
我要扼住命运的咽喉。
