Description
检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行，每列，每条对角线(包括两条主对角线的所有对角线)上都至多有一个棋子。 列号
0 1 2 3 4 5 6
-------------------------
1 | | O | | | | |
-------------------------
2 | | | | O | | |
-------------------------
3 | | | | | | O |
-------------------------
4 | O | | | | | |
-------------------------
5 | | | O | | | |
-------------------------
6 | | | | | O | |
-------------------------
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下： 行号 1 2 3 4 5 6 列号 2 4 6 1 3 5 这只是跳棋放置的一个解。请遍一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。 特别注意: 对于更大的N(棋盘大小N x N)你的程序应当改进得更有效。不要事先计算出所有解然后只输出，这是作弊。如果你坚持作弊，那么你登陆USACO Training的帐号将被无警告删除
Input
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
Output
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
Sample Input
6
Sample Output
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4 解题思路：求解n皇后的裸题。
之前就一直想写写关于八皇后问题的博客，这次碰到裸题，就一起说了吧。 八皇后问题： 在棋盘上放置8个皇后，使得它们互不攻击，此时每一个皇后的攻击范围为同行同列和同对角线，要求找出所有的解。 分析：最简单的思路是把问题转化为"从64个格子中选取一个子集"，使得“子集中掐有8个格子，且任意两个选出的格子都不在同一行、同一列、同一个对角线上”，这正是子集的枚举问题，
然而64个格子的子集有2^64个，太大了，这并不是一个很好的模型。
第二个思路是把问题转化为“从64个格子中选8个格子”，这是组合生成问题。根据组合数学，有4.426*10^9种方案，比第一种优秀，但仍然不够很好。
经过思考，不难发现：恰好每行每列各放置一个皇后，如果用C[x]表示第x行皇后的编号，则问题变成了全排列生成问题。而0-7的排列一共有8！=40320个，枚举量不会超过它。 而至于如何枚举，则需要编写递归程序实现枚举。
当把问题分成若干步骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象叫做回溯。真因为这个原因，递归枚举算法常被称作回溯法。 关于代码说明。
1.既然是逐行放置，则皇后肯定不会横向攻击，因此只需要检查是否纵向和斜向攻击即可。
2.vis数组的使用：vis数组的确切意义是什么？它表示已经放置的皇后占据了那些列、主对角线、副对角线。vis[0][i]代表占据列；vis[1][x+i]代表占据副对角线;vis[2][x-i+n]代表
占据主对角线上的点，但y-x可能为负数，所以需要加n存取。 3.一般的，如果在回溯法中修改了辅助的全局变量，则一定要既是把它们恢复原状（除非故意保留所做修改！）
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 110
using namespace std;
int n;
int sum;
int ans[MAX];
int vis[][MAX];///vis[0]代表列，vis[1]代表副对角线，vis[2]代表主对角线
void DFS(int x)
{
int i;
if(x==n+)
{
sum++;
if(sum<=)
{
for(i=; i<=n; i++)
{
if(i==)
{
printf("%d",ans[i]);
}
else
{
printf(" %d",ans[i]);
}
}
printf("\n");
return ;
}
}
for(i=; i<=n; i++)
{
if(!vis[][i]&&!vis[][x+i]&&!vis[][x-i+n])
{
vis[][i]=vis[][x+i]=vis[][x-i+n]=;
ans[x]=i;
DFS(x+);
vis[][i]=vis[][x+i]=vis[][x-i+n]=;///状态恢复
}
}
}
int main()
{
scanf("%d",&n);
memset(ans,,sizeof(ans));
memset(vis,,sizeof(vis));
DFS();
printf("%d\n",sum);
}