LeetCode 37. 解数独（搜索+剪枝）

本文主要是介绍LeetCode 37. 解数独（搜索+剪枝），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路：

用数组 $x, y, z$ 记录每一行，每一列，和每一个 $3 * 3$ 小块里面0~9的使用情况。使用状态，0代表使用了，1代表没有使用。
然后搜索的时候遍历每一个格子，找到里面可选数字最少的那一个（也就是其行、列、小块的数字使用情况状态的与值中1最少的那个。
直到搜索到每个格子都被填完
加几个剪枝：如果中间有格子什么数都填不了，那就直接返回 $f a l s e$ 。

class Solution {
public:char s[105];int x[105],y[105],z[105];int X[105],Y[105],Z[105];int f[1005];int cnt[1005];int gx,gy,gz;int get_cnt(int i) {int num = 0;while(i) {num++;i -= i & -i;}return num;}void get(int i) {gx = X[i];gy = Y[i];gz = Z[i];}void work(int i,int now) {get(i);x[gx] ^= (1 << now);y[gy] ^= (1 << now);z[gz] ^= (1 << now);}bool dfs(int ans) {if(!ans) return true;int k = 10,w,t = -1;for(int i = 0;i < 81;i++) {if(s[i] == '.') {get(i);w = x[gx] & y[gy] & z[gz];if(w == 0) return false;if(cnt[w] < k) {k = cnt[w];t = i;}}}if(t == -1) return false;get(t);w = x[gx] & y[gy] & z[gz];while(w) {int now = f[w & -w];s[t] = now + '1';work(t,now);if(dfs(ans - 1)) return true;work(t,now);w -= w & -w;s[t] = '.';}return false;}void solve(vector<vector<char>>&board) {for(int i = 0;i < 9;i++) {x[i] = (1 << 9) - 1;y[i] = (1 << 9) - 1;z[i] = (1 << 9) - 1;}int ans = 0;for(int i = 0;i < 9;i++) {for(int j = 0;j < 9;j++) {s[i * 9 + j] = board[i][j];}}for(int i = 0;i < 81;i++) {if(s[i] != '.') work(i,s[i] - '1');else ans++;}dfs(ans);for(int i = 0;i < 9;i++) {for(int j = 0;j < 9;j++) {board[i][j] = s[i * 9 + j];}}}void init() {for(int i = 0;i < (1 << 9);i++) cnt[i] = get_cnt(i);for(int i = 0;i < 81;i++) {X[i] = i / 9;Y[i] = i % 9;Z[i] = X[i] / 3 * 3 + Y[i] / 3;}for(int i = 0;i < 9;i++) f[1 << i] = i;}void solveSudoku(vector<vector<char>>& board) {init();solve(board);}
};