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 1111mask模版int mask (1 n) - 1; //n表示棋盘的大小pos——安全域利用或运算( | )合并所有的危险区域0000 0001 0000 0010 0000 0100此时所有的1都表示危险区域0000 0111再进行一次取反操作此时1表示安全位置1111 1000但是注意此时我们棋盘大小只有4位前面的4位数其实是不能去的这个时候就需要我们的mask了利用与运算的特性与1相与结果不变与0相与变为0mask 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 - pcas模版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对应坐标的话就1col_num __builtin_ctz(cas) 1代码示范#include iostream #include vector using namespace std; int mask, n, cnt 0; vectorint 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; } }
八皇后问题的多种解法 #DFS #位运算 #状态压缩
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 1111mask模版int mask (1 n) - 1; //n表示棋盘的大小pos——安全域利用或运算( | )合并所有的危险区域0000 0001 0000 0010 0000 0100此时所有的1都表示危险区域0000 0111再进行一次取反操作此时1表示安全位置1111 1000但是注意此时我们棋盘大小只有4位前面的4位数其实是不能去的这个时候就需要我们的mask了利用与运算的特性与1相与结果不变与0相与变为0mask 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 - pcas模版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对应坐标的话就1col_num __builtin_ctz(cas) 1代码示范#include iostream #include vector using namespace std; int mask, n, cnt 0; vectorint 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; } }
