洛谷P1219
题目传送门：https://www.luogu.com.cn/problem/P1219
题目简述：
输入n表示棋盘大小，n的范围是6<=n<=13
现在要按行顺序放置皇后，让皇后不互相攻击的情况下放置，也就是要安排列数，使得每一行每一列都有一个皇后
思路分析：
以n = 6为例子：
可以想象这道题的解答树，对于每一层有6个列数可以选择，然后每一个节点都有六个子节点，现在需要找出能走到要求深度的树的分支，输出前三个路径
比较显然的是会选择dfs来遍历树，但难点是每一次都要判断是否皇后之间有攻击
一开始的想法是弄一个vis表记录每一个禁着点，但是发现这太麻烦了，，
再思考一下其实是又数学关系的，一个是列数相等，一个是行差等于列差。
数据储存方式：
col[row]用这个储存列数，可以确定皇后的位置，row也就是dfs的深度
代码：
#include<cstdio>
#include<cstring>
#include<cmath>int n;
int col[15]; //col[row] = 列
int cnt;bool safe(int r, int c) {for (int i = 1; i < r; i++) {if (c == col[i])return 0;if (std::abs(c-col[i]) == r-i)return 0;}return 1;
}void dfs(int row) {if (row == n + 1) {cnt++;if (cnt <= 3) {for (int i = 1; i <= n; i++) {printf("%d ", col[i]);}printf("\n");}return;}for (int i = 1; i <= n; i++) {if (safe(row,i)) {col[row] = i;dfs(row + 1);}}
}int main() {scanf("%d", &n);cnt = 0;dfs(1);printf("%d\n", cnt);return 0;
}
最后：
