AcWing 169 16×16数独 – 代码

对，这真的只是为了纪念调试了半天多才通过的这道毒瘤题目的。码长$5\textrm{KB}$。

剪枝框架是按照《进阶指南》写的，但具体实现仍然沿用了九宫格数独的方法——分别记录每一行、列、十六宫格的可填入数字的二进制数，然后取与运算。所以相对来说没有那么直观。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <bits/stdc++.h>
using namespace std;

template <typename T> inline bool read (T &x) {
	x = 0; int f = 1; char c = getchar ();
	for (; c != EOF && !isdigit (c); c = getchar ())
		if (c == '-') f = -1;
	if (c == EOF) return 0;
	for (; c != EOF && isdigit (c); c = getchar ())
		x = (x<<1) + (x<<3) + (c^48);
	x *= f; return 1;
}
template <typename T> void print (T x) {
	if (x < 0) putchar ('-'), x = -x;
	if (x > 9) print (x / 10);
	putchar ('0' + x % 10);
}
#define reint register int
#define inl inline
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
struct pint {
	short x, y;
	friend bool operator == (pint a, pint b) {
		return a.x == b.x && a.y == b.y; }
};

const int N = 18;
const pint PNUL = (pint){ -1, -1 }, OK = (pint) { 0, 0 };
char s[N][N];
int r[N], c[N], juro[N], ed, flag;
char mapp[65540], popc[65540], bel[N][N], haji[N][N];
struct modi { short x, y, num; } sta[256];

#define lowbit(x) x & -x
#define calc(x, y) (x - 1) / 4 * 4 + (y - 1) / 4 + 1
inl void _proc (modi &g, bool rev) {
	if (rev) s[g.x][g.y] = 0;
	else s[g.x][g.y] = g.num;
	r[g.x] ^= 1<<g.num-1, c[g.y] ^= 1<<g.num-1,
	juro[bel[g.x][g.y]] ^= 1<<g.num-1;
}
#define kekka(x, y, num) _proc (sta[ed] = (modi){ x, y, num }, 0), ++ed
inl void outp () {
	for (reint i = 1; i <= 16; ++i, puts (""))
		for (reint j = 1; j <= 16; ++j)
			putchar ('A' - 1 + s[i][j]);
	puts ("");
}

inl pint check () {
	// 考虑所有单点。
	short cnt = 0, x, y, mn = 1024; int tmp, ima;
	for (reint i = 1; i <= 16; ++i)
		for (reint j = 1; j <= 16; ++j)
			if (!s[i][j]) {
				if (!(tmp = r[i] & c[j] & juro[bel[i][j]])) return PNUL;
				else if (popc[tmp] == 1) kekka (i, j, mapp[tmp]), ++cnt;
			} else ++cnt;
	if (cnt == 256) return OK;
	// 考虑所有的行。
	for (reint i = 1; i <= 16; ++i) {
		tmp = 0;
		for (reint j = 1; j <= 16; ++j) // 遍历行内所有点。 
			tmp |= !s[i][j] ? r[i] & c[j] & juro[bel[i][j]] : 1<<s[i][j] - 1;
		if (tmp != (1<<16) - 1) return PNUL;
		tmp = r[i];
		while (tmp) {
			ima = mapp[lowbit(tmp)]; cnt = 0;
			for (reint j = 1; j <= 16; ++j)
				if (!s[i][j] && ((c[j] & juro[bel[i][j]])>>ima - 1) & 1)
					++cnt, y = j;
			if (!cnt) return PNUL;
			if (cnt == 1) kekka (i, y, ima);
			tmp -= lowbit(tmp);
		}
	}
	// 考虑所有的列。
	for (reint j = 1; j <= 16; ++j) {
		tmp = 0;
		for (reint i = 1; i <= 16; ++i) // 遍历列内所有点。 
			tmp |= !s[i][j] ? r[i] & c[j] & juro[bel[i][j]] : 1<<s[i][j] - 1;
		if (tmp != (1<<16) - 1) return PNUL;
		tmp = c[j];
		while (tmp) {
			ima = mapp[lowbit(tmp)]; cnt = 0;
			for (reint i = 1; i <= 16; ++i)
				if (!s[i][j] && ((r[i] & juro[bel[i][j]])>>ima - 1) & 1)
					++cnt, x = i;
			if (!cnt) return PNUL;
			if (cnt == 1) kekka (x, j, ima);
			tmp -= lowbit(tmp);
		}
	} 
	// 考虑所有的子十六宫格。
	for (reint ura = 1; ura <= 16; ++ura) {
		tmp = 0;
		for (reint i = haji[ura][0]; i < haji[ura][0] + 4; ++i)
			for (reint j = haji[ura][1]; j < haji[ura][1] + 4; ++j)
				tmp |= !s[i][j] ? r[i] & c[j] & juro[ura] : 1<<s[i][j] - 1;
		if (tmp != (1<<16) - 1) return PNUL;
		tmp = juro[ura];
		while (tmp) {
			ima = mapp[lowbit(tmp)]; cnt = 0;
			for (reint i = haji[ura][0]; i < haji[ura][0] + 4; ++i)
				for (reint j = haji[ura][1]; j < haji[ura][1] + 4; ++j)
					if (!s[i][j] && ((r[i] & c[j])>>ima - 1) & 1)
						++cnt, x = i, y = j;
			if (!cnt) return PNUL;
			else if (cnt == 1) kekka (x, y, ima);
			tmp -= lowbit(tmp);
		}
	}
	// 再次考虑所有单点。
	cnt = 0;
	for (reint i = 1; i <= 16; ++i)
		for (reint j = 1; j <= 16; ++j)
			if (!s[i][j]) {
				if (!(tmp = r[i] & c[j] & juro[bel[i][j]])) return PNUL;
				else if (popc[tmp] < mn)
					mn = popc[tmp], x = i, y = j;
			} else ++cnt;
	return cnt == 256 ? OK : (pint) { x, y };
}

inl void dfs () {
	short umaed = ed, oried, tmp, ima;
	pint fr = check ();
	if (fr == OK) return flag = 1, outp ();
	else if (fr == PNUL) {
		while (ed > umaed) _proc (sta[ed - 1], 1), --ed;
		return; }
	tmp = r[fr.x] & c[fr.y] & juro[bel[fr.x][fr.y]];
	while (tmp) {
		ima = mapp[lowbit(tmp)], oried = ed;
		kekka (fr.x, fr.y, ima); dfs ();
		if (flag) return;
		while (ed > oried) _proc (sta[ed - 1], 1), --ed;
		tmp -= lowbit(tmp);
	}
	while (ed > umaed) _proc (sta[ed - 1], 1), --ed;
}

int main () {
	/*  */
// 预处理以O(1)查询 
for (reint i = 1; i <= 1<<16; ++i)
	popc[i] = popc[i - (lowbit(i))] + 1;
for (reint i = 1; i <= 16; ++i)
	for (reint j = 1; j <= 16; ++j)
		bel[i][j] = calc (i, j);
for (reint i = 1; i <= 16; ++i)
	haji[i][0] = 1 + (i - 1) / 4 * 4,
	haji[i][1] = 1 + (i - 1) % 4 * 4;
for (reint i = 0; i < 16; ++i)
	mapp[1<<i] = i + 1;

while (~scanf ("%s", s[1] + 1)) {
	for (reint i = 2; i <= 16; ++i)
		scanf ("%s", s[i] + 1);
	for (reint i = 1; i <= 16; ++i)
		r[i] = c[i] = juro[i] = (1<<16) - 1;
	for (reint i = 1; i <= 16; ++i)
		for (reint j = 1; j <= 16; ++j) {
			s[i][j] = s[i][j] == '-' ? 0 : s[i][j] - 'A' + 1;
			if (!s[i][j]) continue;
			r[i] ^= 1<<s[i][j]-1, c[j] ^= 1<<s[i][j]-1,
			juro[bel[i][j]] ^= 1<<s[i][j]-1;
		}
	ed = flag = 0; dfs ();
}

	return 0;
}