题目： 

N皇后在一个N*N的棋盘上，使其不能相互攻击，即任意两个皇后不得处于同一行，同一列或一条对角线上。

(皇后的攻击是米字型,即不能同行不能同列,不能同对角线)

 

思路:

我们先假设n为一个小一点的数字,让问题看起来简单些,这里假设n==4;

 一行不可能放入两个皇后,  而所有的皇后都要放进去, 所以每个皇后都在不同的行,每行必有一个皇后

我们从第一行开始,每取出一个皇后，放入一行,共有4种不同的放法;

然后再放第二个皇后,还是有4种不同的放法

此时就是一个四叉树的结构

 于是我们可以用一个四叉树来描述这个过程。从根节点开始，树每增加一层，便是多放一个皇后，

 直到第四层（根节点为0层），最后得到一个完全四叉树。　　

紧接着我们开始用深度优先遍历这个四叉树，在遍历的过程中，进行相应的条件的判断。以便去掉不合规则的子树。

　   那么具体用什么条件来进行剪枝呢？

　   我们先对问题解的结构做一个约定。

   　用a[i]来表示 ,a[i]为第i行皇后所在的列数 (a实际为一种映射关系)

这时我们考虑第一个条件，不能在同一行，同一列于是我们得到a[i]不能相同。

剩下一个条件是不能位于对角线上，这个条件不是很明显，但我们知道对角线的45°即斜率为1;

那么设两个不同的皇后分别在i，j行上，a[i],a[j]分别表示在i,j行哪一列上。

那么在同一对角线的条件可以写为abs((j-i))==abs(a[i]-a[j])，其中abs为求绝对值的函数(c++在<cmath>的头文件里>

#include 
     
      #include 
      
       using namespace std;#define N 8int sum=0;int a[N+1]; //a为层数到列数的映射关系void  dfs(int ceng){    if(ceng==N+1)    {        for(int i=1;i
      
     

0-0然后就可以了

这个方法是纯暴力,把所有的可能情况都试了一遍,所以极其慢,要过hdu的话需要打表骗分

后来想了下,这道题用全排列可能写起来更容易些,

嘛,电脑快没电了,宿舍还没来电,

等来电了再补上吧,

溜了溜了