CodeVS/1295

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
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; }