一、    简述

这里八皇后问题使用递归式深搜解法。要点在于：首先深搜方法得出部分排列，再判断这样的排列是否满足不互相攻击，满足则进行下一阶段搜索，否则搜索本阶段下一个部分排列，至本阶段搜索完则回溯。

二、    难点

主要的两个难点是深搜函数和判断是否会相互攻击。前者已经有详细的讲解，故不做过多叙述；主要对后者做讨论。我们把问题作简化：很容易知道，对于每行与每列，有且只有一个皇后。如果对64个点选出8个做深搜进行判断，既不利于判断函数编写，也不利于程序的效率（程序需要运行64！/56！次）。既然具备简化问题的条件，我们应该积极地寻求解决问题的方法。我们利用下标存储行号，建立数组存储每一行对应的列，就极大地简化了数据量。

接下来是判断函数的编写。做一个简单的推理：添加一个新的皇后时，只需检查它与之前的皇后是否有冲突。同时由于新皇后一定在旧后的下边，故简化后我们只需判断新皇后是否在如图线上：（为节省时间简化问题至6个皇后）（黄色六芒星表示皇后，红色圆表示攻击范围）。

http://s13/bmiddle/bebf89f3tde02e9fbbf1c&690

对问题再次做简化以适应于简易的算法：我们得到需要判断的某行，在这样的一行，对于某个皇后，最多只有两个位置可被攻击到。进行一次循环并判断，即可得到所求的解。这样的点可以用简单的几何方法求得。

至此把判断的问题难点已经攻破。

三、    代码展示

如下：

#define STATUS int  //沿用我曾看过的一本数据结构书的方法 把返回状态的函数返回值类型

              //定义为status

#define Q 8      //皇后数

#include

#include   //提供getch()方法以中断程序提供视点

#include  //提供memset方法但似乎没用上。。

              //好多东西说成了java的方式。。

int wer=0,ans[100];//wer存储题解个数 ans数组存储解并即时输出

STATUS vis[100]; //vis 数组表示当前的访问状态  

void dfs(int);  //深度搜索的函数声明

void print();   //输出的函数声明

int judge(int,int);//判断函数声明

void print()

{

   for(int i=1;i<=Q;i++)

   printf("%d",ans[i]);//依序输出当前取得的解

   printf("\n");    //换行

   wer++;           //解的个数自增

   if(wer==0)getch();//每输出10个暂停一下

}

 

STATUS judge(int n,int p)//这里判断是否放置的皇后会互相攻击

{                //传来的参数表示新皇后放置 第n行第p列 

                   

   for(int i=1;i对于从第一个到第n个每一个皇后进行下列检测

   {

       //if(p==ans[i])return -1;//首先判断是否处于同一列上

       //突然意识到没有这样做的必要,因为八皇后问题实质上是全排列的特例,

       //不可能出现两皇后同列

       int shift=n-i;//存储“偏移量”，对应新添加的n+1层在对角线上的点

                  //相对第一层列坐标的位置变化，详见我编完程序画张图~

       if(p==ans[i]+shift||p==ans[i]-shift)  return -1;

                 //判断是否在一条对角线上

                 //i+-shift可能会溢出，但是溢出后不会相等，故无需做判断         

   }

   return 0;  //检测通过             

}                        

 

void dfs(int n)

{

    if(n==Q+1)//递推至n+1层

    {

        print();//输出答案

        return;//回溯

    }

    

       

   for(int i=1;i<=Q;i++)//升序搜索满足条件的答案

   {

      if(!vis[i])//如果这一列没有皇后

      {

       

        if(judge(n,i)==0)//如果对于新皇后放置在第n行第p列的情况不致互相攻击

        { 

           ans[n]=i;//把第n行的皇后放置在第i列

           vis[i]=1;//第i列已放置皇后

           dfs(n+1);//进行下一行的搜索

           vis[i]=0;//此时已经是回溯到上一行的搜索，重新把第i列置空

        }

      }

   }

}

       

int main()

{

   dfs(1);//从第1行进行皇后的搜索

   printf("%d\n",wer);//输出解的个数

   getch();//全部运行完毕 制造断点供观看

}

四、    结语

这是我第一次做这样的解题报告，排版什么的都很渣，希望勿怪。部分思路沿用自网上及此前的知识储备，还有很多想法是自己想到的。

值得注意的是，与上一次的全排列不同，主函数调用dfs函数时参数是1，否则无法产生正确结果。计算机世界千变万化，有时候我们需要存储更多的数据来减少计算（动态规划等）；有时候我们却在简化存储方式的同时也简化了问题。我们致力于做更好的算法，这条路任重道远，我们会继续下去！

黑科大Acm小组

姜志鹏

2013.5.27