思路：
dfs + 剪枝
首先，如果这个位置只能填一种字母，那就直接填
其次，如果对于每一种字母，如果某一列或者某一行或者某一块只能填它，那就填它
然后，对于某个位置如果不能填字母了，或者某种字母在一行一列或一块中出向了两次以上，说明当前方案不成立
最后贪心地从可选情况少的往下搜
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 17; int mp[N][N]; int st[N][N]; int sum = 0; char s[N][N+5]; void add(int x, int y, int t) { mp[x][y] = t; sum++; for (int i = 1; i <= 16; i++) { st[i][y] |= 1<<t-1; st[x][i] |= 1<<t-1; } int xx = (x+3)/4, yy = (y+3)/4; for (int i = (xx-1)*4 + 1; i <= xx*4; i++) { for (int j = (yy-1)*4 + 1; j <= yy*4; j++) { st[i][j] |= 1<<t-1; } } } void print() { for (int i = 1; i <= 16; i++) { for (int j = 1; j <= 16; j++) { putchar(mp[i][j]-1+'A'); } puts(""); } puts(""); } bool dfs() { if(sum == 256) { print(); return true; } for (int i = 1; i <= 16; i++) { for (int j = 1; j <= 16; j++) { if(!mp[i][j]) { int cnt = 0, t = 0; for (int k = 1; k <= 16; k++) { if((st[i][j] & (1<<k-1)) == 0) { cnt++; t = k; if(cnt == 2) break; } } if(!cnt) return false; if(cnt == 1) add(i, j, t); } } } for (int i = 1; i <= 16; i++) { for (int k = 1; k <= 16; k++) { int cnt1 = 0, cnt2 = 0, y; for (int j = 1; j <= 16; j++) { if(mp[i][j] == k) cnt1++; if(cnt1 == 2) return false; if(!mp[i][j] && (st[i][j] & (1<<k-1)) == 0) cnt2++, y = j; } if(!cnt1 && !cnt2) return false; if(!cnt1 && cnt2 == 1) add(i, y, k); } } for (int j = 1; j <= 16; j++) { for (int k = 1; k <= 16; k++) { int cnt1 = 0, cnt2 = 0, x; for (int i = 1; i <= 16; i++) { if(mp[i][j] == k) cnt1++; if(cnt1 == 2) return false; if(!mp[i][j] && (st[i][j] & (1<<k-1)) == 0) cnt2++, x = i; } if(!cnt1 && !cnt2) return false; if(!cnt1 && cnt2 == 1) add(x, j, k); } } for (int i = 1; i <= 16; i++) { int x = (i+3)/4, y = i - (x-1)*4; for (int k = 1; k <= 16; k++) { int cnt1 = 0, cnt2 = 0, xx, yy; for (int ii = (x-1)*4+1; ii <= x*4; ii++) { for (int jj = (y-1)*4+1; jj <= y*4; jj++) { if(mp[ii][jj] == k) cnt1++; if(cnt1 == 2) return false; if(!mp[ii][jj] && (st[ii][jj] & (1<<k-1)) == 0) cnt2++, xx = ii, yy = jj; } } if(!cnt1 && !cnt2) return false; if(!cnt1 && cnt2 == 1) add(xx, yy, k); } } if(sum == 256) { print(); return true; } int mn = N, x, y; for (int i = 1; i <= 16; i++) { for (int j = 1; j <= 16; j++) { if(!mp[i][j]) { int cnt = 0; for (int k = 1; k <= 16; k++) { if((st[i][j] & (1<<k-1)) == 0) { cnt++; if(cnt >= mn) break; } } if(cnt < mn) { mn = cnt; x = i; y = j; } } } } int tst[N][N], tmp[N][N]; memcpy(tst, st, sizeof(st)); memcpy(tmp, mp, sizeof(mp)); int tsum = sum; for (int k = 1; k <= 16; k++) { if((st[x][y] & (1<<k-1)) == 0) { add(x, y, k); bool f = dfs(); if(!f) { memcpy(st, tst, sizeof(tst)); memcpy(mp, tmp, sizeof(tmp)); sum = tsum; } else return true; } } return false; } int main() { while(scanf("%s", s[1]+1) != EOF){ for (int i = 2; i <= 16; i++) { scanf("%s", s[i]+1); } sum = 0; mem(mp, 0); mem(st, 0); for (int i = 1; i <= 16; i++) { for (int j = 1; j <= 16; j++) { if(isalpha(s[i][j])) add(i, j, s[i][j] - 'A' + 1); } } dfs(); } return 0; } /* --A----C-----O-I -J--A-B-P-CGF-H- --D--F-I-E----P- -G-EL-H----M-J-- ----E----C--G--- -I--K-GA-B---E-J D-GP--J-F----A-- -E---C-B--DP--O- E--F-M--D--L-K-A -C--------O-I-L- H-P-C--F-A--B--- ---G-OD---J----H K---J----H-A-P-L --B--P--E--K--A- -H--B--K--FI-C-- --F---C--D--H-N- */