【N皇后问题】

题目描述

在N*N的棋盘上放置N个皇后而彼此不受攻击(即在棋盘的任一行,任一列和任一对角线上不能放),编程求出所有合法的摆放方案数。

下图是N=8的两种摆放方案:

输入格式

输入一个正整数 N(1<=N<=10) 。

输出格式

输出一个整数,表示合法的摆放方案总数。

样例数据 1

输入

6

输出

4

样例数据 2

输入

3

输出

0

经典的DFS题,尝试了一下非递归写法……注意到每一行总是要放一个皇后的于是直接把第k个皇后放在第k行,然后调整列数就行了,这样做就直接处理了不能放在同一行的条件。于是第k个皇后的坐标就是(k,pos[k]),设第i个皇后坐标为(i,pos[i]),稍微推一下不难发现若是在对角线上则abs(k-i)=abs(pos[k]-pos[i]),而若在同一列上就是pos[k]=pos[i]了,于是每放置一个看一下是否冲突就行了。下面是代码:
递归解法:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*