《进阶指南》0x23 C
Part 0 题外话
搜索当然可以做这道题。
这是书上的 DFS 例题，我做了半天，调了半天，总算 AC 了。
其实暴力出奇迹，虽然这是 DLX 的板子题，但是在考场上碰到这种题，并且像我这样还没学到这种高级数据结构的话，还是要打打暴力的。因为：暴搜+大量的剪枝优化=AC
书上说，算法思维能力的训练远比学习几个能直接拿来解决问题的数据结构更重要
若按 Luogu 的评级来看，这是我做的第一道黑题。
大佬们已经帮我们踩过坑了：注意多测，每组数据之后要输出一个空行。
Part 1 题意
填写 16*16 的数独，使得每行、每列、每个 4*4 的十六宫格内字母 A~P 各出现一次。
Part 2 思路
做过数独的人，都知道候选数法里面有两个最常用的东西，一个叫做 显式唯一法 ，一个叫做 隐式唯一法 ，利用这两个比较容易实现方法进行可行性剪枝，就差不多够用了，再选择可填的字母数量最少的位置来枚举，具体思路如下：
- 显式唯一法。考虑所有空位
- 若某个空位 A~P 都不可填，立即回溯
- 若某个空位只有一个字母可填，立即填入这个字母
- 隐式唯一法。考虑所有行、列、宫格
- 若某个字母不能填在该行/列/宫格的任何一个空位上，立即回溯
- 若某个字母只能填在该行/列/宫格的某一个空位上，立即在这个空位上填入这个字母
- 如果显式唯一法与隐式唯一法都填不了，选择可填的字母数量最少的位置来枚举填写的情况
Part 3 实现
我实现的方式和很多大佬不一样，将遍历检查 check() 与 dfs() 分开写。check() 负责检查现阶段的情况，dfs() 负责进行递归搜索与输出。
和 9*9 数独一样，一些最基本的预处理还是要有的。
为方便运算，空格的坐标从 0 开始，填入的数码也是从 0 开始。
代码量有点大，写到后面可能会有点疲惫，注意不要犯写反 i 和 j 变量名之类的低级错误。
有个问题我调了很久才明白，tmp[N][N] 不能放到全局，放到全局会被之后的搜索改动，失去了它的意义，必须作为局部变量。
敲完之后反思，其实实现隐式唯一法时，check() 里面三大段代码实际上唯一的区别在于将 i 和 j 转化成坐标的公式不一样。把这些公式打包成函数并存进数组里（应该做得到），再用个 for 循环，可以减少重复代码量，调试与维护还可以容易些。
- 处理行的公式：
x = i, y = j; - 处理列的公式：
x = j, y = i; - 处理宫格的公式：
x = i/4*4+j/4, j = i%4*4+j%4;
剩下的都在代码的注释里了，写代码的时候用的虚拟机，整不出中文输入法，所以写代码过程中的注释用的全英文，后面加的注释都用中文，请原谅我英文水平一般。
#include <stdio.h>
#define N 16
#define SQRTN 4
int maze[N][N], choice[N][N];
int Pow[N], Log[1 << N], Count1[1 << N];
int check(int &bestX, int &bestY, int &onlyChoice) {
// 各种返回值的含义如下：
// ret = 0 -> no solution
// ret = 1 -> solved the problem
// ret = 2 -> only one choice
// ret = 3 -> several choices
// global:
int mininum = N + 1;
int only, all, locked;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (maze[i][j] == -1) { // which is not assured
if (!choice[i][j]) { // no solution for this point
return 0;
}
int cnt = Count1[choice[i][j]];
if (cnt == 1) {
bestX = i;
bestY = j;
onlyChoice = Log[choice[i][j]];
return 2;
} else if (cnt < mininum) {
mininum = cnt;
bestX = i;
bestY = j;
}
}
}
}
if (mininum == N + 1) return 1;
// row:
for (int i = 0; i < N; ++i) {
only = (1 << N) - 1, all = locked = 0;
for (int j = 0; j < N; ++j) {
only &= ~(all & choice[i][j]);
all |= choice[i][j];
if (~maze[i][j]) locked |= choice[i][j];
}
if (all != (1 << N) - 1) return 0;
for (; only; only ^= only & (-only)) {
int lbt = only & (-only);
if (!(locked & lbt)) {
onlyChoice = Log[lbt];
bestX = i;
for (int j = 0; j < N; ++j) {
if (choice[i][j] & lbt) {
bestY = j;
return 2;
}
}
}
}
}
// column:
for (int i = 0; i < N; ++i) {
only = (1 << N) - 1, all = locked = 0;
for (int j = 0; j < N; ++j) {
only &= ~(all & choice[j][i]);
all |= choice[j][i];
if (~maze[j][i]) locked |= choice[j][i];
}
if (all != (1 << N) - 1) return 0;
for (; only; only ^= only & (-only)) {
int lbt = only & (-only);
if (!(locked & lbt)) {
onlyChoice = Log[lbt];
bestY = i;
for (int j = 0; j < N; ++j) {
if (choice[j][i] & lbt) {
bestX = j;
return 2;
}
}
}
}
}
// grid:
for (int i = 0; i < N; ++i) {
only = (1 << N) - 1, all = locked = 0;
int x, y;
for (int j = 0; j < N; ++j) {
x = (i / SQRTN) * SQRTN + j / SQRTN;
y = (i % SQRTN) * SQRTN + j % SQRTN;
only &= ~(all & choice[x][y]);
all |= choice[x][y];
if (~maze[x][y]) locked |= choice[x][y];
}
if (all != (1 << N) - 1) return 0;
for (; only; only ^= only & (-only)) {
int lbt = only & (-only);
if (!(locked & lbt)) {
onlyChoice = Log[lbt];
for (int j = 0; j < N; ++j) {
x = (i / SQRTN) * SQRTN + j / SQRTN;
y = (i % SQRTN) * SQRTN + j % SQRTN;
if (choice[x][y] & lbt) {
bestX = x;
bestY = y;
return 2;
}
}
}
}
}
return 3;
}
void cpy(int arr1[N][N], int arr2[N][N]) { // 手写一个memcpy，使得 arr1 = arr2
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
arr1[i][j] = arr2[i][j];
}
}
}
void lock(int x, int y, int num) { // 锁定 (x, y) 的值为 num，并修改相关空格的候选数
maze[x][y] = num;
int p = Pow[num];
// row & column:
for (int i = 0; i < N; ++i) {
choice[x][i] &= ~p;
choice[i][y] &= ~p;
}
// grid:
int xst = x / SQRTN * SQRTN;
int yst = y / SQRTN * SQRTN;
for (int i = 0; i < SQRTN; ++i) {
for (int j = 0; j < SQRTN; ++j) {
choice[xst+i][yst+j] &= ~p;
}
}
choice[x][y] = p;
}
void init() { // 多测清空
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
maze[i][j] = -1;
choice[i][j] = (1 << N) - 1;
}
}
}
bool dfs() {
// ret = 0 -> no solution
// ret = 1 -> have solution
int bestX, bestY, onlyChoice, tmp[N][N];
// Attention: tmp[N][N] must be a local variable instead of a global one
switch (check(bestX, bestY, onlyChoice)) {
case 0:
return 0;
case 1:
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
printf("%c", maze[i][j] + 'A');
}
printf("\n");
}
return 1;
case 2:
cpy(tmp, choice);
lock(bestX, bestY, onlyChoice);
if (dfs()) return 1;
cpy(choice, tmp);
maze[bestX][bestY] = -1;
return 0;
case 3:
for (int best = choice[bestX][bestY]; best; best ^= best & (-best)) {
int sid = Log[best & (-best)];
cpy(tmp, choice);
lock(bestX, bestY, sid);
if (dfs()) return 1;
cpy(choice, tmp);
maze[bestX][bestY] = -1;
}
return 0;
}
return 0; // 没有这行编译可能不给过
}
int main() {
// 预处理 Pow[N], Log[1<<N], Count1[1<<N]
for (int i = 0; i < N; ++i) {
Pow[i] = 1 << i;
Log[1 << i] = i;
}
for (int i = 1; i < 1 << N; ++i) {
for (int j = i; j; j -= j & (-j)) {
++Count1[i];
}
}
char str[100];
bool flag = 0;
while (~scanf("%s", str)) {
// 那个输出的坑
if (flag) printf("\n");
else flag = 1;
init(); // 只要是多测，这行必须有（多测清空）
for (int j = 0; j < N; ++j) {
if (str[j] != '-') {
lock(0, j, str[j] - 'A');
}
}
for (int i = 1; i < N; ++i) {
scanf("%s", str);
for (int j = 0; j < N; ++j) {
if (str[j] != '-') {
lock(i, j, str[j] - 'A');
}
}
}
dfs();
}
return 0;
}
Part 4 验证
由 Luogu 转交到 UVa 的评测记录： https://www.luogu.com.cn/record/99044482
AC 130ms
Nowcoder 上的评测记录： https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60181284
AC 203ms
好吧，说明代码运行效果还行，Luogu 基本上都看不到大佬的代码，不知道那些 DLX 的大佬运行速度怎样。只找到了 Nowcoder 的大佬，也是用的 DFS，用时 80ms。
京公网安备 11010502036488号