问题 U: 【回溯】n皇后问题

时间限制: 1 Sec  内存限制: 128 MB

提交: 4  解决: 4

[][][]

题目描述

在一个国际象棋棋盘上，放置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 
     
      #include 
      
       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