前几天一直在忙一些事情，所以一直没来得及开始这个搜索专题的训练，今天做了下这个专题的第一题，皇后问题在我没有开始接受Axie的算法低强度训练前，就早有耳闻了，但一直不知道是什么类型的题目，今天一看，原来是搜索题，还是入门的深搜题，关于题目的意思recwert在这就不解释了。直接讲讲思路吧。
按照深度优先搜索的理念，应该是从上到下搜索（如果你硬要说可以从下到上。。但是仔细想想其实是一个意思。。）在二叉树的DFS中，我们是假定了左孩子优先，所以在这题，我们也可以假定行优先（行优先和列优先是一个结果，或者说根本就说一个思路）。
让我们先画一个棋盘：（4*4棋盘，不多也不少）
( 0,0) ( 0,1) ( 0,2) ( 0,3) ( 1,0) ( 1,1) ( 1,2) ( 1,3) ( 2,0) ( 2,1) ( 2,2) ( 2,3) ( 3,0) ( 3,1) ( 3,2) ( 3,3) 我们需要开一个保存当前已经搜索的进度，用一个一维数组即可：queen[4], queen[i]代表第i行选择的queen[i]列。如下代码表示了该题需要存的所有数据
int queen[MAXN]; //皇后位置的选取情况
int sum = ; //迭代结果变量
int result[MAXN] = {}; //保存结果变量，防止测试量多的情况下发生超市
int m; //题目输入变量，皇后数（棋盘边长）接下来我们开始DFS, 从第一行开始搜索，每行的搜索按照从左到右的顺序，那第一行搜索结果应该是这样的。(红色为选中)
( 0,0) ( 0,1) ( 0,2) ( 0,3) ( 1,0) ( 1,1) ( 1,2) ( 1,3) ( 2,0) ( 2,1) ( 2,2) ( 2,3) ( 3,0) ( 3,1) ( 3,2) ( 3,3) 接下来搜索第二行
结果应该是这样的：（至于为什么是这个结果根据题意就可以明白了）
( 0,0) ( 0,1) ( 0,2) ( 0,3) ( 1,0) ( 1,1) ( 1,2) ( 1,3) ( 2,0) ( 2,1) ( 2,2) ( 2,3) ( 3,0) ( 3,1) ( 3,2) ( 3,3) 在接下来搜索第三行的时候会发现不管选择哪一个都是不行的。通过什么方法来判断行或者不行呢。写一个check()方法来检测, 参数n表示检测第n行
bool check( int n ){
for( int i = ; i < n; i++ ){
//检查在第n行之前是否有在同一列或者45度对角线上
if( queen[i] == queen[n] || abs( queen[i] - queen[n]) == ( n - i )){
return false;
}
}
return true;
}
在发现此次搜索失败后，应该做什么呢。呵呵，当然是什么都不做啦。那具体我们如何实现这个dfs呢。看看下面的代码：
void put( int n ){
//从第n行开始dfs，搜索第n行的m列
for( int i = ; i < m; i++ ){
queen[n] = i;
//检测成功
if( check(n) ){
//搜索到最后一行了
if( n == m - ){
sum++;
}
else{
put( n + );
}
}
}
}
如果皇后数量为4，那么这里的m应该为4，put函数中初始传入的参数为0，表示从第0行开始搜索，对第0行的没一列都要搜索，如果搜索成功了但没到最后一行，就继续搜索下一行，如果到最后一行了，sum自增，如此递归，就能将结果搜索出来了。我们来看一个可以满足条件的结果
搜索第0行：
0,0) ( 0,1) ( 0,2) ( 0,3) ( 1,0) ( 1,1) ( 1,2) ( 1,3) ( 2,0) ( 2,1) ( 2,2) ( 2,3) ( 3,0) ( 3,1) ( 3,2) ( 3,3) 搜索第1行：
0,0) ( 0,1) ( 0,2) ( 0,3) ( 1,0) × ( 1,1) × ( 1,2) × ( 1,3) ( 2,0) ( 2,1) ( 2,2) ( 2,3) ( 3,0) ( 3,1) ( 3,2) ( 3,3) 搜索第2行：
0,0) ( 0,1) ( 0,2) ( 0,3) ( 1,0) × ( 1,1) × ( 1,2) × ( 1,3) ( 2,0) ( 2,1) ( 2,2) ( 2,3) ( 3,0) ( 3,1) ( 3,2) ( 3,3) 搜索第3行（最后一行）
0,0) ( 0,1) ( 0,2) ( 0,3) ( 1,0) × ( 1,1) × ( 1,2) × ( 1,3) ( 2,0) ( 2,1) ( 2,2) ( 2,3) ( 3,0) × ( 3,1) × ( 3,2) sum++ ( 3,3) 然后接着从(0,2)搜索起，相信这么一个图解过程，应该能看懂了吧。下面贴出题目AC的完整代码：
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 16
int queen[MAXN]; //皇后位置的选取情况
int sum = ; //迭代结果变量
int result[MAXN] = {}; //保存结果变量，防止测试量多的情况下发生超市
int m; //题目输入变量，皇后数（棋盘边长）
bool check( int n ){
for( int i = ; i < n; i++ ){
//检查在第n行之前是否有在同一列或者45度对角线上
if( queen[i] == queen[n] || abs( queen[i] - queen[n]) == ( n - i )){
return false;
}
}
return true;
}
void put( int n ){
//从第n行开始dfs，搜索第n行的m列
for( int i = ; i < m; i++ ){
queen[n] = i;
//检测成功
if( check(n) ){
//搜索到最后一行了
if( n == m - ){
sum++;
}
else{
put( n + );
}
}
}
}
int main()
{
while( cin>>m, m ){
sum = ;
if( result[m] != ){
cout<<result[m]<<endl;
}
else{
put();
result[m] = sum;
cout<<result[m]<<endl;
}
}
return ;
}