- https://www.luogu.com.cn/problem/P1219
- 这个有趣的问题我将分三个版本为您解释，主要差时间优化异体现在check函数上，实现原理分别从循环到坐标规律实现的O(1)操作，最后是位运算的极致优化
- check函数：
- 检测该位置放置王后是否合法，即检查行，列，主对角线，副对角线是否有王后。几种方式的差异体现在check函数的实现方式不同，从而导致了时间差异。在主体dfs部分，基本保持一致。
3.1 循环check
- 循环行，列，左上，右下，左下，右上（由于行列在dfs中我们就完成了规避，所以可以减少两次循环，别小看这两次循环，check在dfs中被大量调用，减少这两次循环通过时间可缩短至原来的4/5）
代码展示：
#include <iostream> #include <vector> using namespace std; const int N = 15; int gra[N][N], n, used[N], cnt = 0; vector <int> ans; bool check (int y, int x) { // ture -> 冲突 for (int i = y, j = x; i >= 1 && j >= 1; i--, j--) if (gra[i][j] == 1 && i != y && j != x) return true; for (int i = y, j = x; i <= n && j <= n; i++, j++) if (gra[i][j] == 1 && i != y && j != x) return true; for (int i = y, j = x; j >= 1 && i <= n; j--, i++) if (gra[i][j] == 1 && i != y && j != x) return true; for (int i = y, j = x; j <= n && i >= 1; j++, i--) if (gra[i][j] == 1 && i != y && j != x) return true; return false; } void set (int y, int x) { gra[y][x] = 1; } void unset (int y, int x) { gra[y][x] = 0; } void dfs(int f) { if (f > n) { cnt++; if (cnt <= 3) { for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << endl; } } for (int i = 1; i <= n; i++) { if (used[i - 1]) continue; if (check(f, i)) continue; set(f, i); used[i - 1] = true; ans.push_back(i); dfs(f + 1); ans.pop_back(); used[i - 1] = false; unset(f, i); } } int main() { cin >> n; dfs(1); cout << cnt << endl; return 0; }3.2 映射check
- 我们可以观察一下规律，那就是在一条主对角线上，每个坐标啊的横纵坐标差是一样的（注意，此处可能产生负数，所以在后续处理的时候我们会通过做差+n的方式来规避负数，因为差值最大也就为n了）
- 在每一条副对角线上，每个点的横纵坐标之和是一致的，也就是说，每一条主对角线差唯一，每一条副对角线和唯一。我们可以利用这个唯一的值来记录该直线上是否出现王后的状态。同上横纵在dfs过程就规避了，我们只需要处理对角线，只需要用两个一维数组记录每一条线是否出现王后
代码展示：
#include <iostream> #include <cmath> #include <vector> using namespace std; const int N = 15; int n, used[N], cnt = 0; int mia[60], dep[30]; vector <int> ans; bool check (int y, int x) { if (mia[y - x + n] == 1) return true; if (dep[y + x] == 1) return true; return false; } void set (int y, int x) { mia[y - x + n] = 1; dep[y + x] = 1; } void unset (int y, int x) { mia[y - x + n] = 0; dep[y + x] = 0; } void dfs(int f) { if (f > n) { cnt++; if (cnt <= 3) { for (int i = 0; i < ans.size(); i++) cout << ans[i] << " "; cout << endl; } } for (int i = 1; i <= n; i++) { if (used[i - 1]) continue; if (check(f, i)) continue; set(f, i); used[i - 1] = true; ans.push_back(i); dfs(f + 1); ans.pop_back(); used[i - 1] = false; unset(f, i); } } int main() { cin >> n; dfs(1); cout << cnt << endl; return 0; }3.3 状态压缩：
mask——安全滤镜：
- 为什么要用mask？
- 我们拿一个32比特位的int来说，假如说我们讨论的只是八皇后问题，就像从前我们用二维数组一样，需要确定一个边界，不能越界，这里的mask也是如此，是为了确保投影不会越界
- 怎么得到mask？
- 以一个8比特位的数据为例
0000 0001- 假如我们现在棋盘大小是4 * 4， 让1左移4位，可以直接用按位左移操作 <<
- 此时得到如下二进制数据
0001 0000- 接下来对其减一就可以得到4个1（就类似于十进制1000 - 1 = 999一样），稍后你会发现这四个一的神奇作用
0000 1111- mask模版：
int mask = (1 << n) - 1; //n表示棋盘的大小pos——安全域：
- 利用或运算( | )，合并所有的危险区域
0000 0001 0000 0010 0000 0100- 此时所有的1都表示危险区域
0000 0111- 再进行一次取反操作，此时1表示安全位置
1111 1000- 但是注意此时我们棋盘大小只有4位，前面的4位数其实是不能去的，这个时候就需要我们的mask了，利用与运算的特性，与1相与结果不变，与0相与，变为0
mask = 0000 1111 // 相与后结果如下 pos = 0000 1000- 该操作之后1就是安全的不越界的可放置位置，接下来， 我们只需要挨个尝试所有的“1”位置即可
- pos模版：
pos = mask & (~ (scp1 | scp2 | scp3));cas——位运算手术刀：
- 为什么叫手术刀？
- 他可以精准抓取Lowbit，即获得最右边的“1”
- 神奇的pos & -pos
- 请原谅我目前的水平暂时无法严格证明这个神奇手术刀成立，不过选取例子验证，不难发现是正确的，只能说发现这个规律的人非常厉害，从来我们是讲二进制码直接转为字符串然后开始从右计“1”，现在我们又了更快的工具——手术刀
- 举例尝试：
pos = 6 (0000 0110); -pos = 1111 1001 + 1 -> 1111 1010; pos & -pos = 0000 0010- 注意在取出来lowbit之后不要忘了在pos中把lowbit删掉哦～
- 删除操作只需要pos - p就好了，就相当于在二进制的世界里抹去了零头，和1320，抹去最低位的非零数，变成1300一样，也就是我们说的抹零
pos -= p- cas模版：
cas = pos & ~pos; pos -= p;循环计0与__builtin_ctz()硬件魔法
- 循环计0，也是比较简单的代码实现，不过多赘述
for (int i = 1; i <= n; i++) { if (cas & (1 << (i - 1))) { col_num = i; break; } }- cpu电路魔法__builtin_ctz() 返回从右边开始遇到第一个1之前有多少个0，对应坐标的话就+1
col_num = __builtin_ctz(cas) + 1代码示范：
#include <iostream> #include <vector> using namespace std; int mask, n, cnt = 0; vector<int> path; void dfs(int row, int col, int l, int r) { if (row > n) { cnt++; if (cnt <= 3) { for (auto x : path) cout << x << " "; cout << endl; } return; } int pos = mask & (~(col | l | r)); while (pos) { int cas9 = pos & -pos; pos -= cas9; int col_num = __builtin_ctz(cas9) + 1; path.push_back(col_num); dfs(row + 1, col | cas9, (l | cas9) << 1, (r | cas9) >> 1); path.pop_back(); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; mask = (1 << n) - 1; dfs(1, 0, 0, 0); cout << cnt << endl; }计0部分可用循环代替：
for (int i = 1; i <= n; i++) { if (cas9 & (1 << (i - 1))) { col_num = i; break; } }
