AcWing 169 16×16数独 – 代码

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

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

#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;
}