N皇后问题 深搜+剪枝 hdu-2553

N 皇后问题在此就不多介绍了,相信CS的同学都应经清楚了,不清楚也可自行Google(听说国内用不了Google了?令人发指!)。在此以一道例题为引。

hdu-2553 1 #include <iostream>

 #include <math.h>
using namespace std; #define MAX 12 int n;
int solution_num;
int row[MAX]={};
int result[MAX];
int is_valid(int posted_num){
for(int i = ; i < posted_num; i++){
if(row[i] == row[posted_num] || abs((row[posted_num] - row[i])) == abs(posted_num - i) )
return ;
}
return ;
} void test(int posted_num){
//under which condition RETURN
if(posted_num == n){
solution_num++;
return;
}
for(int i = ;i <= n; i++){
row[posted_num] = i;
if(is_valid(posted_num)){
test(posted_num+);
}
}
} int main(int argc, const char * argv[]) { for(n = ;n <= MAX-;n++){
solution_num = ;
test();
result[n] = solution_num;
}
while(cin>>n,n){
cout<<result[n]<<endl;
}
return ;
}

其实上述代码就是暴力解决,先在第一列某一位置放置一个皇后,标记行号row[i](row[i]不能再放皇后了,否则会冲突),再在第二列寻找可能合法的位置,blablabla,直到N个皇后全部放好后,递归结束。可能会有人在判断可行性的时候会有疑惑。横竖判断肯定没问题,在判断斜线时,我们利用斜率不等于正负1来判断,而这两点在棋盘中的坐标,恰好可以利用(posted_num,row[posted_num])和(i,row[i])来表示,这个小技巧优化了存储空间和代码复杂度。

为不超时,采用了打表的方法进行提交并通过。

有递归不超时的算法??下次为大家带来超强位运算解NQUEEN问题的详解!

上一篇:no2222


下一篇:Nginx安装教程