AcWing 169. 数独2（复杂的搜索+剪枝）

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

在这里插入图片描述

思路：

可以看出来，这就是数独加强版， $9 * 9$ 变成了 $16 * 16$ 。对应的算法效率要求也更高。一开始想在 $9 * 9$ 的代码上加剪枝水过去，搜索功力还是不足过不去。。。
参考了《进阶指南》的思路和代码。
思路就是搜索的时候遍历每个点，如果这个点不能选数了，那么剪掉，如果只能选一个数，那就选上。（这里以及下面所有“点”都是针对空格点）
遍历每一行，如果这一行没数可选那就剪掉，如果只能选一个数那就选上。列和每个4*4小块同理。
最后再按照常规思路，遍历每个格子选出可选数最少的格子从这里开始枚举选哪个数搜索下去。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
char s[16][16];
int cnt[1 << 16],f[1 << 16],num[16][16];
vector<int>e[1 << 16];
void work(int i,int j,int k) {for(int t = 0;t < 16;t++) {num[i][t] &= ~(1 << k);num[t][j] &= ~(1 << k);}int x = i / 4 * 4,y = j / 4 * 4;for(int ti = 0;ti < 4;ti++) {for(int tj = 0;tj < 4;tj++) {num[x + ti][y + tj] &= ~(1 << k);}}
}
bool dfs(int ans) {if(!ans) return true;int pre[16][16];memcpy(pre,num,sizeof(num));//遍历所有格子for(int i = 0;i < 16;i++) {for(int j = 0;j < 16;j++) {if(s[i][j] == '-') {if(!num[i][j]) return false; //有格子选不了直接剪掉if(cnt[num[i][j]] == 1) { //只能选这一个数，选上s[i][j] = f[num[i][j]] + 'A';work(i,j,f[num[i][j]]);if(dfs(ans - 1)) return true;s[i][j] = '-';memcpy(num,pre,sizeof(num));return false;}}}}//遍历每一行for(int i = 0;i < 16;i++) {int w[16],o = 0;memset(w,0,sizeof(w));for(int j = 0;j < 16;j++) {if(s[i][j] == '-') {o |= num[i][j];for(int k = 0;k < e[num[i][j]].size();k++) {++w[e[num[i][j]][k]];}} else {o |= (1 << (s[i][j] - 'A'));w[f[1<<(s[i][j] - 'A')]] = -1;}}if(o != (1 << 16) - 1) return false;for(int k = 0;k < 16;k++) {if(w[k] == 1) {for(int j = 0;j < 16;j++) {if(s[i][j] == '-' && ((num[i][j] >> k) & 1)) {s[i][j] = k + 'A';work(i,j,k);if(dfs(ans - 1)) return true;s[i][j] = '-';memcpy(num,pre,sizeof(num));return false;}}}}}//遍历每一列for(int j = 0;j < 16;j++) {int w[16],o = 0;memset(w,0,sizeof(w));for(int i = 0;i < 16;i++) {if(s[i][j] == '-') {o |= num[i][j];for(int k = 0;k < e[num[i][j]].size();k++) {++w[e[num[i][j]][k]];}} else {o |= (1 << (s[i][j] - 'A'));w[f[1<<(s[i][j] - 'A')]] = -1;}}if(o != (1 << 16) - 1) return false;for(int k = 0;k < 16;k++) {if(w[k] == 1) {for(int i = 0;i < 16;i++) {if(s[i][j] == '-' && ((num[i][j] >> k) & 1)) {s[i][j] = k + 'A';work(i,j,k);if(dfs(ans - 1)) return true;s[i][j] = '-';memcpy(num,pre,sizeof(num));return false;}}}}}//遍历每一个4*4小块for(int i = 0;i < 16;i += 4) {for(int j = 0;j < 16;j += 4) {int w[16],o = 0;memset(w,0,sizeof(w));for(int p = 0;p < 4;p++) {for(int q = 0;q < 4;q++) {if(s[i + p][j + q] == '-') {o |= num[i + p][j + q];for(int k = 0;k < e[num[i + p][j + q]].size();k++) {++w[e[num[i + p][j + q]][k]];}} else {o |= (1 << (s[i + p][j + q] - 'A'));w[f[1 << (s[i + p][j + q] - 'A')]] = -1;}}}if(o != (1 << 16) - 1) return false;for(int k = 0;k < 16;k++) {if(w[k] == 1) {for(int p = 0;p < 4;p++) {for(int q = 0;q < 4;q++) {if(s[i + p][j + q] == '-' && ((num[i + p][j + q] >> k) & 1)) {s[i + p][j + q] = k + 'A';work(i + p,j + q,k);if(dfs(ans - 1)) return true;s[i + p][j + q] = '-';memcpy(num,pre,sizeof(num));return false;}}}}}}}//选择可选数最少的那个格子int k = 17,tx,ty;for(int i = 0;i < 16;i++) {for(int j = 0;j < 16;j++) {if(s[i][j] == '-' && cnt[num[i][j]] < k) {k = cnt[num[i][j]];tx = i;ty = j;}}}for(int i = 0;i < e[num[tx][ty]].size();i++) {int tz = e[num[tx][ty]][i];work(tx,ty,tz);s[tx][ty] = tz + 'A';if(dfs(ans - 1)) return true;s[tx][ty] = '-';memcpy(num,pre,sizeof(num));}return false;
}
void solve() {for(int i = 1;i < 16;i++) scanf("%s",s[i]);for(int i = 0;i < 16;i++) {for(int j = 0;j < 16;j++) {num[i][j] = (1 << 16) - 1;}}int ans = 0;for(int i = 0;i < 16;i++) {for(int j = 0;j < 16;j++) {if(s[i][j] != '-') {work(i,j,s[i][j] - 'A');} else {ans++;}}}if(dfs(ans)) {for(int i = 0;i < 16;i++) {for(int j = 0;j < 16;j++) {printf("%c",s[i][j]);}printf("\n");}} else {printf("DEBUG\n");}printf("\n");
}
int get_cnt(int i) {int k = i & -i;e[i].push_back(f[k]);for(int j = 0;j < e[i - k].size();j++) {e[i].push_back(e[i - k][j]);}return cnt[i - k] + 1;
}
void init() {for(int i = 0;i < 16;i++) f[1 << i] = i;cnt[0] = 0;for(int i = 1;i < (1 << 16);i++) {cnt[i] = get_cnt(i);}
}
int main() {init();while(~scanf("%s",s[0])) {solve();}return 0;
}