这两天在做搜索题，然后遇到了这个题，一不小心就解出来了，感觉还是有点意思，就拿出来分享一下。

题目描述
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

//以下的话来自usaco官方，不代表洛谷观点

特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出(或是找到一个关于它的公式），这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号删除并且不能参加USACO的任何竞赛。我警告过你了！

输入格式
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。

输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例
输入 #1 复制
6
输出 #1 复制
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

这个题应该是非常经典的递归+回溯题了，额，递归+回溯我就不写了，主要写一下这个题应该怎么写。
放置n个皇后，每放一个它要满足左右对角线没有皇后，横竖没有皇后，然后才可以放，这里可以用三个数组解决这个问题，放好一个的时候再放第二个，第二个皇后摆放位置的要求和第一个一样，并且所有的皇后摆放位置要求都是一样的，所以可以用递归来解决相同子结构问题。这题主要思想就是我可以放这个皇后我给她放上，然后打上标记说明当前放的皇后的左右对角线，横竖对角线都不可以再放皇后了，其他的也是这样，但是不是随便放都是解，当我们发现剩下的位置不能把皇后摆放完，这时候我们回溯到上一个皇后，让他换一个位置。
总之：就是递归+打标记
但是这里还要一个难点，怎么样确定我当前皇后的横竖，左右对角线不能再摆皇后，我拿个图来说明一下：

在棋盘上任取一个皇后，你会发现它左对角线都满足一个特点，要么x=y(横竖都相同),要么x-y=一个常数。例如：取(3,5)它的左对角线：（4,6),(5,7),(6,8)，4-6=5-7=6-8=-2，根据这个规律设置一个数组visd[x-y+n]表示左对角线不能放皇后，因为x-y有可能是负数，所以加了一个n，这个不会影响整体结果；
而右对角线就更加简单了，还是这个点(3,5)，它的右对角线皇后：（4,4）,(5,3),(6,8),(7,1)，你会发现它的右对角线各元素之和等于自己的和。3+5=4+4=5+3=4+8
根据这个特点可以设置一个数组visc[x+y]表示当前皇后的右对角线不能再放皇后了。
ac代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int path[50];
int vis[50];
int visc[50];
int visd[50];
int sum=0;
void dfs(int depth){
	if(depth>n){
		sum++;
		if(sum>3)
		return;
		for(int i=1;i<=n;i++){
			cout<<path[i]<<" ";
		}
		cout<<endl;
		return ; 
	}
	for(int i=1;i<=n;i++){
		if((!vis[i])&&(!visc[depth+i])&&(!visd[depth-i+n])){
			path[depth]=i;
			vis[i]=1;
			visc[depth+i]=1;
			visd[depth-i+n]=1;
			dfs(depth+1);
			vis[i]=0;
			visc[depth+i]=0;
			visd[depth-i+n]=0;
		}
	}
}

int main()
{
	cin>>n;
	dfs(1);
	cout<<sum<<endl;
	return 0;
}