AcWing166. 数独-DFS剪枝与优化

本文主要是介绍AcWing166. 数独-DFS剪枝与优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

思路

1. 思考问题：搜索顺序->考虑剪枝
2. 搜索顺序：先随意选择一个空格子，枚举该格子可填写的数字，当所有格子都填完的时候，说明可以退出了
3. 剪枝：
   1. 优化搜索顺序：随意选择一个空格子：应该优先搜索分支数量较少的方案，如果分支数量相同，则选择前者
   2. 可行性剪枝：当前数字不能与行，列，九宫格有重复
4. 本题用到了位运算优化：9位的01串：0表示尚未用过，1表示用过；与运算
      行：123456789
   行01：001101010
   列01：...
   九01：...
   lowbit运算：返回01串的1
5. AcWing 801. 二进制中1的个数 - AcWing

代码

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 9, M = 1 << N;int ones[M], map[M]; //one:一个串有多少个1：打表;
int row[N], col[N], cell[3][3]; //行，列，9宫格
char str[100]; //棋盘void init()
{for (int i = 0; i < N; i ++ )row[i] = col[i] = (1 << N) - 1;for (int i = 0; i < 3; i ++ )for (int j = 0; j < 3; j ++ )cell[i][j] = (1 << N) - 1;
}void draw(int x, int y, int t, bool is_set)
{if (is_set) str[x * N + y] = '1' + t;else str[x * N + y] = '.';int v = 1 << t;if (!is_set) v = -v;row[x] -= v;col[y] -= v;cell[x / 3][y / 3] -= v;
}int lowbit(int x)
{return x & -x;
}int get(int x, int y)
{return row[x] & col[y] & cell[x / 3][y / 3];
}bool dfs(int cnt)
{if (!cnt) return true;int minv = 10;int x, y;for (int i = 0; i < N; i ++ )for (int j = 0; j < N; j ++ )if (str[i * N + j] == '.'){int state = get(i, j);if (ones[state] < minv){minv = ones[state];x = i, y = j;}}int state = get(x, y);for (int i = state; i; i -= lowbit(i)){int t = map[lowbit(i)];draw(x, y, t, true);if (dfs(cnt - 1)) return true;draw(x, y, t, false);}return false;
}int main()
{for (int i = 0; i < N; i ++ ) map[1 << i] = i;for (int i = 0; i < 1 << N; i ++ )for (int j = 0; j < N; j ++ )ones[i] += i >> j & 1;while (cin >> str, str[0] != 'e'){init();int cnt = 0;for (int i = 0, k = 0; i < N; i ++ )for (int j = 0; j < N; j ++, k ++ )if (str[k] != '.'){int t = str[k] - '1';draw(i, j, t, true);}else cnt ++ ;dfs(cnt);puts(str);}return 0;
}

这篇关于AcWing166. 数独-DFS剪枝与优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---