给定一个 N×N 的棋盘，请你在上面放置 N 个棋子，要求满足：
- 每行每列都恰好有一个棋子
- 每条对角线上都最多只能有一个棋子
1 2 3 4 5 6
-------------------------
1 | | O | | | | |
-------------------------
2 | | | | O | | |
-------------------------
3 | | | | | | O |
-------------------------
4 | O | | | | | |
-------------------------
5 | | | O | | | |
-------------------------
6 | | | | | O | |
-------------------------
上图给出了当 N=6 时的一种解决方案，该方案可用序列 2 4 6 1 3 5 来描述，该序列按顺序给出了从第一行到第六行，每一行摆放的棋子所在的列的位置。
请你编写一个程序，给定一个 N×N的棋盘以及 NN个棋子，请你找出所有满足上述条件的棋子放置方案。
输入格式
共一行，一个整数 N。
输出格式
共四行，前三行每行输出一个整数序列，用来描述一种可行放置方案，序列中的第 ii个数表示第 ii行的棋子应该摆放的列的位置。
这三行描述的方案应该是整数序列字典序排在第一、第二、第三的方案。
第四行输出一个整数，表示可行放置方案的总数。
数据范围
6≤N≤13
输入样例：
6
输出样例：
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
这题就是八皇后，就是输出的时候需要注意一下格式，只需要我们输出前三种方案和方案总数，那么只需要在输出的代码前加上约束条件，if（ans<=3）时，进行输出
八皇后的难点就是如何对不符合要求的格子进行染色：
皇后所在的行和列以及斜边不能够有别的皇后在，否则便会相互攻击到。
因为我们使用深搜的每一层递归相当于是一行，在每一次递归当中选中其中的一列，所以可以定义一个r数组和一个c数组以及L数组和R数组，相当于皇后所在的行和列以及斜边上进行染色
对于斜边 ： y = kx+b; 等价于 b=y-kx; 需要注意的是 k=1或k=-1;
所以 b=y-x 或者 b=y+x
因为y-x有可能小于0，所以我们需要加上一个参数把它的值调回正数
所以数组染色的表示为 r[x] , c[i] ,L[y+x] ,R[y-x+10];
重申：r[x]表示这一行是否有皇后 、 c[i]表示这一列是否有皇后
因为本题对无解的n和n==1时没有特殊要求，所以只需要考虑一般情况，具体代码如下：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 const int N = 20; 5 int a[N]; 6 int c[N],r[N],L[N],R[N]; 7 int ans; 8 int n; 9 10 inline bool check(int x,int y){ 11 if( x<1 || x>n ||y<1 || y>n) return 0; //地图之外不能放棋子 12 if(r[x] || c[y] || L[y+x] || R[y-x+10]) return 0; //染色了的格子也不能放 13 return 1; 14 } 15 16 inline void dfs(int x){ 17 if(x>n){ //递归出口 18 ans++; 19 if(ans<=3){ //约束条件 20 for(int i = 1;i<=n;++i){ 21 printf("%d ",a[i]); 22 } 23 printf(" "); 24 } 25 return ; 26 } 27 28 for(int i = 1;i<=n;++i){ 29 if(check(x,i)){ 30 r[x] = c[i] = 1; 31 L[i+x] = R[i-x+10] = 1; 32 a[x] = i; 33 //进入下一层递归 34 dfs(x+1); 35 //记得要回溯 36 r[x] = c[i] = 0; 37 L[i+x] = R[i-x+10] = 0; 38 } 39 } 40 } 41 42 43 int main() 44 { 45 scanf("%d",&n); 46 ans = 0; 47 dfs(1); 48 printf("%d ",ans); 49 return 0; 50 }