【回溯】n皇后问题
<center>
提交: 4 解决: 4
[提交][状态][讨论版] </center>
问题 U: 【回溯】n皇后问题
时间限制: 1 Sec 内存限制: 128 MB提交: 4 解决: 4
[提交][状态][讨论版] </center>
题目描述
在一个国际象棋棋盘上，放置n个皇后（n＜10），使她们相互之间不能进攻。求出所有布局。
输入
一个整数n（0<n<10）
输出
每行输出一种方案，每种方案顺序输出皇后所在的列号，各个数之间用空格分隔。
样例输入
4
样例输出
2 4 1 3 3 1 4 2
解题思路：一上午都没做出题来，开始看回溯了，总是不能理解，今下午看刘汝佳的算法竞赛，上面有n皇后问题，讲解地很细致。
看完后然后终于能敲出代码了。
c[i]保存第i行的列，比如 3 2 4 0 5 ，3表示第零行放在第三列，2表示第一行放在第2列，4表示第二行放在第4列，0表示第三行放在第0列...（从0开始）
函数backtrack（int line）需要设置结束条件，当行数==n时，就可以输出c[i]保存的结果了。
当没到结束条件时，就开始从i到n遍历一遍，i到n指每一列，然后用函数 condition(line,i) 判断第line行，i列是否可以放皇后。
在 condition(line,i) 里面有个v[3][2n]数组， v[0][],v[1][],v[2],分别表示第i列，副对角线，主对角线是否已经有皇后放置。
line+i和line-i只要有一个是1，就说明这个位置的主对角线，或副对角线上已经有皇后了，便不能再放了，但由于line-i可能为负数，便用+n来保存。
另外要注意backtrack（line+1）之后吧这三个数组的值还原成0；
代码：
#include <iostream> #include <cstdio> using namespace std; int n; int c[15]={0}; int v[3][25]={0}; bool condition(int line,int i){ return !v[0][i] && !v[1][line+i] && !v[2][line-i+n]; } void backtrack(int line){ if(line==n){ for(int i=0;i<n;i++){ printf(" %d",c[i]+1); } printf("\n"); }else{ for(int i=0;i<n;i++){ //分别试试放哪一列上 if(condition(line,i)){ c[line]=i; v[0][i]=v[1][line+i]=v[2][line-i+n]=1; backtrack(line+1); v[0][i]=v[1][line+i]=v[2][line-i+n]=0; } } } } int main() { scanf("%d",&n); backtrack(0); return 0; }
CVTE公司福利 265人发布
投递网易有道等公司10个岗位 >