摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
N皇后问题 ★☆☆☆☆ 答案正确 100 2014/10/13 8:55:43

题意

N*N的棋盘上每行每列每斜行都只能有一个皇后,问摆满N个皇后的方案数。

题解

由于时限放宽了,dfs裸搜就好了。

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

至于N皇后问题的优化,似乎可以用位运算替代数组。除此之外,还有有遗传算法,启发式搜索几种,但是都是比较高深的算法,这里暂时不提了(等我把CodeVS天梯都刷完闲得无聊了再来研究233)。

代码

1295.cpp代码已折叠
展开折叠内容
#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;
}

著作权声明[编辑]

关于[编辑]