本文主要是介绍166. 数独(DFS之剪枝与优化:位运算优化，优化搜索顺序，.可行性剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
166. 数独 - AcWing题库
数独 是一种传统益智游戏，你需要把一个9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
| 难度：中等 |
| 时/空限制：1s / 64MB |
| 总通过数：12606 |
| 总尝试数：22720 |
| 来源：《算法竞赛进阶指南》, POJ3074 , kuangbin专题 |
| 算法标签 |
解析：
DFS之剪枝与优化主要方法:
1.优化搜索顺序：大部分情况下，我们应该优先搜索分支较少的节点
2.排除等效冗余
3.可行性剪枝
4.最优性剪枝
5.记忆化搜索（dp)
1.优化搜索顺序：
先搜索可选状态少的。可以使用 row[i] (i:0~8)表示第0行到第8行所用过的数字，1表示当前位置对应的数字没有使用过，可以使用；0表示当前位置对应的数字没有使用过，不可以使用。
同样的 col[i] 记录列的状态，cel[i] 记录九宫格的状态
2. 可行性剪枝
同样的，通过上述数组判断某个数字在某个位置是否可行
同时，此题对时间的要求很高，所以我们还要使用 lowbit 函数提高判断速度，使用 one 和 mp 数组记录某个数 1 的个数和表示 lowbit 函数返回的数字表示 1~9 中的哪个数
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 1 << 9;
string s;
int row[10], loc[10], cel[3][3];
int mp[N], one[N];void init() {for (int i = 0; i < 9; i++) {row[i] = (1 << 9) - 1;loc[i] = (1 << 9) - 1;}for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {cel[i][j] = (1 << 9) - 1;}}
}int lowbit(int x) {return x & -x;
}void change(int a, int b, int num, int flg) {if (flg) {row[a] -= 1 << num;loc[b] -= 1 << num;cel[a / 3][b / 3] -= 1 << num;s[a * 9 + b] = num + '1';}else {cel[a / 3][b / 3] += 1 << num;row[a] += 1 << num;loc[b] += 1 << num;s[a * 9 + b] = '.';}
}int dfs(int cnt) {if (cnt == 0) {cout << s << endl;return 1;}int mn = 10;int a=0, b=0;for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (s[i * 9 + j] == '.') {int x = row[i] & loc[j] & cel[i / 3][j / 3];if (one[x] < mn) {mn = one[x];a = i;b = j;}}}}int x= row[a] & loc[b] & cel[a / 3][b / 3];while (x) {change(a, b, mp[lowbit(x)], 1);if (dfs(cnt - 1))return 1;change(a, b, mp[lowbit(x)], 0);x -= lowbit(x); }return 0;
}int main() {//预处理one和mp数组for (int i = 0; i < 9; i++) {mp[1 << i] = i;}for (int i = 0; i < 1 << 9; i++)for (int j = 0; j < 9; j++)one[i] += i >> j & 1;while (cin >> s) {if (s == "end")break;int cnt = 0;init();for (int i = 0,a=0,b=0; i < 9; i++) {for (int j = 0,pos=0; j < 9; j++) {pos = i * 9 + j;if (s[pos] == '.') {cnt++;}else {row[i] -= 1 << (s[pos] - '1');loc[j] -= 1 << (s[pos] - '1');cel[i/3][j/3]-= 1 << (s[pos] - '1');}}}dfs(cnt);}return 0;
}
这篇关于166. 数独(DFS之剪枝与优化:位运算优化，优化搜索顺序，.可行性剪枝）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
