昨天晚上写了一个OJ上的八皇后问题，然后居然TLE了。。。。(本人弱鸡)。。。然后就躺在床上想怎么优化，想着想着就睡着了，做了一个令人感到忧伤的梦，然后醒了，然后就想到了怎么优化了。。。。当然我很菜。。。用的还是简单回溯的算法，其实就是DFS，皇后多了还是很耗时的，所以，各位皇帝麻烦您们专一一点好吧。
好吧，先说回溯法吧，回溯法和DFS差不多，其思想就是：“我就是要一条路走到黑，走到黑了然后感觉不对，就赶紧返回上一层，看看有没有其他的路，如果没有走到黑，反而走到白了，那就恭喜我，我成功搞出一条通天大道，那么，我。。我。。我我我还是要返回上一层。。。。看看有没有其他的路。。。“讲道理一条路就中了，但可恶的出题人太贪心，总喜欢让我们把所有的路都找到，这不是坑爹呢吗。。。。
大致的框架可以写为：
void func(int step){
1判断路是不是死路，如果是就返回;
2如果判断是不是已经走出一条通天大道了，如果已经是了，那就在这里搞一些操纵，然后。。。还是要返回上一层。。。
for chioce in allOption{
标记一下这个chioce被选过了(某些情况下需要)
func(step+1);//走下一步
}
}
注意，一定不要把1嵌入2里面，如果这样做的话，会DFS出所有选择的全排列，然后再判断是否可行，这样就没有剪枝的效果了。
好吧我知道本人讲的很渣渣，很坑爹，应该没有人能看懂。。。。嗯。。。如果能画图就好了。。。。但是我很懒。。不想画完图用手机拍照然后再传到电脑上然后在传到博客上。。。。。。。
题目：
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
解法(代码里面的注释应该很清楚)：
#include <iostream>
using namespace std;
void queen(int step);
int n;//有多少个皇后
int count;//记录成功的方案
int book[14];//标记
int a[14];//a[1]表示第一行的皇后在第几列，a[2]表示第二行的。。。。。
int main(){
cin>>n;
queen(n);
cout<<count;
return 0;
}
void queen(int step){
int LastLine=n-step;//上一步摆下来的皇后，因为摆放皇后时候已经用了book数组进行标记约束，所以不需要判断行列
for(int i=1;i<LastLine;i++){//判断是否在同同一斜线上
if(a[LastLine]-a[i]==LastLine-i||a[LastLine]-a[i]==i-LastLine){
return;
}
}
/*for(int i=1;i<=n-step;i++){//这里是原来的判断是否在同一条斜线上的算法，但是算法复杂度很高，分析原因发现
for(int j=i+1;j<=n-step;j++){//这个算法是，对于每一行，都有对比其他的行，重复了很多
if(a[j]-a[i]==j-i||a[j]-a[i]==i-j){//仔细思考发现，只需要判断新加入的皇后符不符合要求就行，所以
return;//换成了上面的算法，复杂度是o(N)
}
}
}*/
if(step==0){//拜访了最后一个皇后，已经得出了一种解法
count++;
if(count<=3){
for(int i=1;i<=n;i++){
cout<<a[i]<<' ';
}
cout<<endl;
}
}else{
//进行本次放置，然后递归下一次
for(int i=1;i<=n;i++){//每次摆放这一行的皇后的时候，都有N列可以摆，意思就是有N个岔路口。
//我们选一个深入，等这个返回之后，再选下一个进行深入，所以是一个for循环
if(!book[i]){//如果第i列还没有黄后占场子
book[i]=1;//标记一下我要占上
a[n+1-step]=i;//摆放皇后
queen(step-1);//深入下一个路口
book[i]=0;//返回了，就要开始走下一个差路口（下一列），所以这一列的标记取消掉
}
}
}
}