1432. 棋盘挑战

给定一个 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("\n");
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\n",ans);
49     return 0;
50  } 

1432. 棋盘挑战

原文：https://www.cnblogs.com/ssfannnnn/p/14312405.html