查看CodeVS/1295的源代码 ←CodeVS/1295

[[分类:深度优先搜索]]
==摘要==
{{信息题|N皇后问题 |http://www.codevs.cn/problem/1295/|1|100|time=2014/10/13 8:55:43}}
==题意==
N*N的棋盘上每行每列每斜行都只能有一个皇后，问摆满N个皇后的方案数。
==题解==
由于时限放宽了，dfs裸搜就好了。

记得这是好多年前我搜索入门第一题，最早是二维数组直接填充写的，后来才发现可以用j+i,j-i斜行记录，于是只用使用四个一维bool数组做记录就好了。

至于N皇后问题的优化，似乎可以用位运算替代数组。除此之外，还有有遗传算法，启发式搜索几种，但是都是比较高深的算法，这里暂时不提了（等我把CodeVS天梯都刷完闲得无聊了再来研究233）。
==代码==
{{折叠|1295.cpp代码已折叠
|<pre>#include<cstdio>
bool Ux[15]={},Uy[15]={},Ud1[30]={},Ud2[30]={};
int n,Ans=0; 
void dfs(const int& i)
{
    if(i>n)
    {
        ++Ans;
        return; 
    } 
    for(int j=1;j<=n;++j)
        if((!Ux[i])&&(!Uy[j])&&(!Ud1[i+j])&&(!Ud2[15+i-j]))
        {
            Ux[i]=1;
            Uy[j]=1;
            Ud1[i+j]=1;
            Ud2[15+i-j]=1;
            dfs(i+1);
            Ux[i]=0;
            Uy[j]=0;
            Ud1[i+j]=0;
            Ud2[15+i-j]=0;
        }
}   
int main()
{
    scanf("%d",&n);
    dfs(1);
    printf("%d",Ans);
    return 0;
}
</pre>
|code1295}}