关于 “N皇后问题” 的解决

最近，老湿才提起，原来我们还有一门课叫“数据结构课程设计”……

呐，我就说嘛，咋在学校网站的 “ 网上教学质量评价 ” 里面，忽然冒出了“数据结构课程设计”这门课，而且也是“数据结构”老湿上滴呢。

看来，该上的课，虽然课表上没有，但是躲也躲不掉的……

老湿说了，有的题目，不一定全靠你自己可以写的出来，所以，这次的目的——就是要训练你们 “ 上网查资料 ” 的能力，以便为日后的毕业论文做准备。

哦，原来如此，要我们 “ 上网查资料 ” 啊o(∩∩)o

不晓得老湿怎么分的组，还是我“姐姐”是学习委员的原因，这次偶又遇到了最简单的题目……

我在第四组，所以就做第四个题，题目如下：

“ N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，求解可能的方案及方案数。 ”

就是 “八皇后 ” 问题的加强版嘛。

我们这组的 “ XX同学 ” 更加 “ 干脆 ”，直接从搞ACM的同学哪里把源码搞来给我看，并且，直接通知俺们的“姐姐”说 —— “ 一切都OK了 ” ……

囧，这“XX同学”，太没 “ 团体意识 ” 了。

好吧，对于 鹚，肯定不会干像 “ 直接把别人写的代码Copy一下 ” 就交的事情，所以还是按照 鹚 写 Code 的 原则，将代码 “ 优化 ” 了下。

好吧，鹚写的代码如下（PS：第一次装代码高亮插件，试试效果如何^_^） ：

#include 
#include 
#include 
using namespace std;

int check(int i,int queen[],int safe[],int rdo[],int ldo[],int nqueen)
{
    int j,k;
    static int num=0;
    for(j=1;j<=nqueen;j++)
    {
        if((safe[j]==0)&&(rdo[i+j]==0)&&(ldo[i-j+nqueen+1]==0))
        {
            queen[i]=j;
            safe[j]=1;
            rdo[i+j]=1;
            ldo[i-j+nqueen+1]=1;
            if(i>nqueen;
    operate(nqueen);
    return 0;
}

然后嘛，鹚开始对这份 Code 进行 “ 性能力 ” 测试。

测试平台：Ubuntu Linux 10.10

代码编写 IDE： CodeBlocks

笔记本： Y450

CPU： Intel Core AT6600 双核 ，主频 2.2G

首先是算 “8皇后”：不要 1S 出答案。

然后是 “11皇后”：大概花了 4S 。

接着是 “15皇后”：算了我 4分多钟。

嗯，看来接下来的 “ 16皇后 ” 计算，我得做好心里准备了。

于是，我输入 “ 16 ” 之后，按下 “回车”。

接下来嘛，我就去超市买零食去了。

挑选了半天的零食，回到寝室，小y还在疯狂的 “ 挣扎 ” 。

竟然运算了接近半个小时……

如图：

好吧，我因此变得Crazy起来，我想试试 —— 到底我小y的 “ 性能力 ” 咋样。

于是，我开始从 “17皇后” ，进行 “ 可行性 ” 分析。

于是我输入 “17、18、19……28…… ”。

果然，当我输入 “ 30 ” 之后，程序没有反应了，直接 “僵死” 掉……

呐，看来，这个 “ N皇后 ” 的 “ 可行性 ” 也就如此而已。

而我的小y的，“ 性能力 ” ，也就那样……

好吧，学弟学妹们，如果那天，你们的老湿也要你们搞课程设计，

你也是碰到了 “ N皇后 ” 这样的问题的话，那么，把哥哥的代码直接Copy一下也行哈。

老湿嘛， “ 忽悠 ” 一下就OK啦o(∩∩)o

……………………………………………………………………

“ To iterate is human, to recurse divine . ” —— L. Peter Deutsch

“人理解迭代，神理解递归。 ” —— L. Peter Deutsch