剪枝 | 搜索

参考《算法竞赛进阶指南》、AcWing题库

剪枝

剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条，故被称为 “剪枝”。在深度优先搜索中，有以下几类常见的剪枝方法：

1. 优化搜索顺序：
   在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。优先搜索分支较少的节点。例如：
   (1) 在上一节的“小猫爬山”问题中，把小猫按照重量递减的顺序进行搜索。
   (2) 在上一节的“Sudoku" 问题中，优先搜索“能填的合法数字“最少的位置。
2. 排除等效冗余
   在搜索过程中, 如果我们能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的, 那么只需要对其中的一条分支执行搜索。我们会在 “Sticks" 问题中看到该剪枝的应用。
   另外, 就如我们在 “Sudoku” 问题中提出的, 一定要避免重叠、 混淆 “层次”与 “分支”, 避免遍历若干棵覆盖同一状态空间的等效搜索树。
3. 可行性剪枝
   在搜索过程中, 及时对当前状态进行检查, 如果发现分支已经无法到达递归边界, 就执行回溯。这就好比我们在道路上行走时, 远远看到前方是一个死胡同, 就应该立即折返绕路, 而不是走到路的尽头再返回。
   某些题目条件的范围限制是一个区间, 此时可行性前枝也被称为 “上下界剪枝”。
4. 最优性剪枝
   在最优化问题的搜索过程中, 如果当前花费的代价已经超过了当前搜到的最优解, 那么无论采取多么优秀的策略到达递归边界, 都不可能更新答案。此时可以停止对当前分支的搜索, 执行回溯。
5. 记忆化
   可以记录每个状态的搜索结果, 在重复遍历一个状态时直接检索并返回。这就好比我们对图进行深度优先遍历时, 标记一个节点是否已经被访问过。
   不过, 读者可能已经发现, 在 “小猫爬山" 与 “Sudoku" 问题中, 我们的搜索算法遍历的状态空间其实是 “树” 形, 不会重复访问, 所以不需要进行记录。

---

167. 木棒

题目描述

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 $50$ 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 $64$ 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 $50$。

输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0 

输出样例：

6
5 

算法分析

我们可以从小到大枚举原始木棒的长度 len (也就是枚举答案)。当然, len 应该是所有木棍长度总和 sum 的约数, 并且原始木棒的根数 cnt 就等于 sum/len。

对于枚举的每个 len, 我们可以依次搜索每根原始木棒由哪些木棒拼成。具体地讲, 搜索所面对的状态包括: 已经拼好的原始木棒根数, 正在拼的原始木棒的当前长度, 每 个木棍的使用情况。在每个状态下, 我们从尚末使用的木棍中选择一个, 尝试拼到当前 的原始木棒里, 然后递归到新的状态。递归边界就是成功拼好 $c n t$ 根原始木棒, 或者 因无法继续拼接而宜告失败。

这个算法的效率比较低, 我们来依次考虑几类剪枝:

1. 优化搜索顺序
   把木棍长度从大到小排序, 优先尝试较长的木棍。
2. 排除等效冗余
   (1) 可以限制先后加入一根原始木棒的木棍长度是递减 $(\geq)$ 的。这是因为先拼上一根长度为 $x$ 的木棍, 再拼上一根长为 $y$ 的木棍 $(x<y)$, 与先拼上 $y$ 再拼上 $x$ 显然是等效的, 只需要搜索其中一种。即按照组合数方式枚举。
   (2) 对于当前原始木棒, 记录最近一次尝试拼接的木棍长度。如果分支搜索失败回溯, 不再尝试向该木棒中拼接其他相同长度的木棍 (必定也会失败)。
   (3) 如果在当前原始木棒中 “尝试拼入的第一根木棍” 的递归分支就返回失败, 那 么直接判定当前分支失败, 立即回溯。这是因为在拼入这根木棍前, 面对的原始木棒都是 “空” 的 (还没有进行拼接), 这些木棒是等效的。木棍拼在当前的木棒中失败, 拼在其他木棒中一样会失败。如下图所示。
   
   (4) 如果在当前原始木棒中拼入一根木棍后, 木棒恰好被拼接完整, 并且 “接下来拼接剩余原始木棒” 的递归分支返回失败, 那么直接判定当前分支失败, 立即回溯。该剪枝可以用贪心来解释, “再用 1 根木棍恰好拼完当前原始木棒” 必然比 “再用若干根木棍拼完当前原始木棒” 更好。如下图所示。
   
   上述 (1) 至 (4) 分别利用 “同一根木棒上木棍顺序的等效性” “等长木棍的等效性” “空木棒的等效性” 和 “贪心”, 剪掉了搜索树上诸多分支, 使得搜索效率大大提 升。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100], v[100], n, len, cnt;

// 正在拼第stick根原始木棒（已经拼好了stick-1根）
// 第stick根木棒的当前长度为cab
// 拼接到第stick根木棒中的上一根小木棍为last
bool dfs(int stick, int cab, int last) {
	// 所有原始木棒已经全部拼好，搜索成功
	if (stick > cnt) return true;
	// 第stick根木棒已经拼好，去拼下一根
	if (cab == len) return dfs(stick + 1, 0, 1);
	int fail = 0; // 剪枝(2)
	// 剪枝(1)：小木棍长度递减（从last开始枚举）
	for (int i = last; i <= n; i++)
		if (!v[i] && cab + a[i] <= len && fail != a[i]) {
			v[i] = 1;
			if (dfs(stick, cab + a[i], i + 1)) return true;
			fail = a[i];
			v[i] = 0; // 还原现场
			if (cab == 0 || cab + a[i] == len) return false; // 剪枝(3,4)
		}
	return false; // 所有分支均尝试过，搜索失败
}

int main() {
	while (cin >> n && n) {
		int sum = 0, val = 0, m = 0;
		for (int i = 1; i <= n; i++) {
			int x;
			scanf("%d", &x);
			if (x <= 50) {
				a[++m] = x;
				sum += a[m];
				val = max(val, a[m]);
			}
		}
		n = m;
		sort(a + 1, a + n + 1);
		reverse(a + 1, a + n + 1); 
		for (len = val; len <= sum; len++) {
			if (sum % len) continue;
			cnt = sum / len; // 原始木棒长度为len，共cnt根
			memset(v, 0, sizeof(v));
			if (dfs(1, 0, 1)) break;
		}
		cout << len << endl;
	}
}

Solution

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;

int n;
int w[N], sum, len;
bool used[N];

bool dfs(int u, int curl, int start) {
  if (u * len == sum) return true;
  //当前大木棒已经拼好了，成功与否完全看后面大木棒拼接情况
  if (curl == len) return dfs(u + 1, 0, 0); 
  
  for (int i = start; i < n; ++i) {
    if (used[i]) continue;
    if (curl + w[i] > len) continue;
    
    used[i] = true;
    if (dfs(u, curl + w[i], i + 1)) return true;
    
    //当前加入第 i 个小木棒失败了之后的处理逻辑
	  
    used[i] = false;
    
    if (curl == 0) return false;
    if (curl + w[i] == len) return false;
    
    int j = i;
    while (j < n && w[j] == w[i]) ++j;
    i = j - 1; //因为后面有 ++i，所以要回退一个
  }
  return false;// 所有分支均尝试过，搜索失败
}

int main() {
  while (cin >> n, n) {
    memset(used, 0, sizeof used);
    sum = 0;
    for (int i = 0; i < n; ++i) {
      cin >> w[i];
      sum += w[i];
    }
    
    sort(w, w + n, greater<int>());
    
    len = 1;
    while (true) {
      if (sum % len == 0 && dfs(0, 0, 0)) {
        cout << len << endl;
        break;
      }
      ++len;
    }
  }
}

168. 生日蛋糕

题目描述

$7$ 月 $17$ 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $Nπ$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 $i$ 层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。

当 $i < M$ 时，要求 $R_i > R_{i+1}$ 且 $H_i > H_{i+1}$。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。

令 $Q = Sπ$ ，请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S$ 最小。

除 $Q$ 外，以上所有数据皆为正整数。

输入格式

输入包含两行，第一行为整数 $N$，表示待制作的蛋糕的体积为 $Nπ$。

第二行为整数 $M$，表示蛋糕的层数为 $M$。

输出格式

输出仅一行，是一个正整数 $S$（若无解则 $S = 0$）。

数据范围

$1 \le N \le 10000$,
$1 \le M \le 20$

输入样例：

100
2 

**
输出样例：**

68 

算法分析

搜索框架: 从下往上搜索, 枚举每层的半径和高度作为分支。

搜索面对的状态有: 正在搜索蛋糕第 $d e p$ 层, 当前外表面面积 $s$, 当前体积 $v$, 第 $d e p+1$ 层的高度和半径。不妨用数组 $h$ 和 $r$ 分别记录每层的高度和半径。

整个蛋糕的 “上表面” 面积之和等于最底层的圆面积, 可以在第 $M$ 层直接累加到 $s$ 中。这样在第 $M-1$ 层往上的搜索中, 只需要计算侧面积。

剪枝：

1. 上下界剪枝
   在第 $d e p$ 层时, 只在下面的范围内枚举半径和高度即可。
   首先, 枚举 $R \in[\operatorname{dep}, \min (\lfloor\sqrt{N-v}], r[d e p+1]-1)]$ 。
   其次, 枚举 $H \in\left[\operatorname{dep}, \min \left(\left\lfloor(N-v) / R^{2}\right\rfloor, h[\operatorname{dep}+1]-1\right)\right]$ 。
   上面两个区间右边界中的式子可以通过圆柱体积公式 $\pi R^{2} H=\pi(N-v)$ 得到。
2. 优化搜索顺序
   在上面确定的范围中, 使用倒序枚举。
3. 可行性剪枝
   可以预处理出从上往下前 $i(1 \leq i \leq M)$ 层的最小体积和侧面积。显然, 当第 $1 \sim i$ 层的半径分别取 $1,2,3, \cdots, i$, 高度也分别取 $1,2,3, \cdots, i$ 时, 有最小体积与侧面积。
   如果当前体积 $v$ 加上 1 dep-1 层的最小体积大于 $N$, 可以剪枝。
4. 最优性剪枝一
   如果当前表面积 $s$ 加上 $1 \sim \operatorname{dep}-1$ 层的最小侧面积大于已经搜到的答案, 剪枝。
5. 最优性剪枝二
   利用 $h$ 与 $r$ 数组, $1\sim dep-1$ 层的体积可表示为 $n-v=\sum_{k=1}^{d e p-1} h[k] * r[k]^{2}$, 1 dep-1 层的表面积可表示为 $2 \sum_{k=1}^{\operatorname{dep}-1} h[k] * r[k]$ 。
   因为 $2 \sum_{k=1}^{\text {dep-1 }} h[k] * r[k]=\frac{2}{r[\text { dep }]} * \sum_{k=1}^{\text {dep-1 }} h[k] * r[k] * r[$ dep $] \geq \frac{2}{r[\text { dep }]} * \sum_{k=1}^{\text {dep-1 }} h[k] *$ $r[k]^{2} \geq \frac{2(n-v)}{r[d e p]}$, 所以当 $\frac{2(n-v)}{r[d e p]}+s$ 大于已经搜到的答案时, 可以剪枝。

加入以上五个剪枝后, 捜索算法就可以快速求出该问题的最优解了。

实际上, 搜索算法面对的状态可以看作一个多元组, 其中每一元都是问题状态空间中的一个 “维度”。例如本题中, 层数 dep、表面积 $s$ 、体积 $v$ 、第 $\operatorname{dep}+1$ 层的高度和半径就构成状态空间中的五个维度, 其中每一项发生变化, 都会移动到状态空间中的另一个 “点”。这些维度通常在题目描述中也有所体现, 它们一般在输入变量、限制条件、待求解变量等非常关键的位置出现。读者一定要注意提取这些 “维度”, 从而设计出合适的搜索框架。

搜索过程中的剪枝, 其实就是针对每个 “维度” 与该维度的边界条件, 加以缩放、 推导, 得出一个相应的不等式, 来减少搜索树分支的扩张。例如本题中的剪枝 1 、剪枝 3 和剪枝 4 , 就是考虑与半径、高度、体积、表面积这些维度的上下界进行比较后直接得到的。

为了进一步提高剪枝的效果, 除了当前花费的 “代价” 之外, 我们还可以对未来至少需要花费的代价进行预算, 这样更容易接近每个维度的上下界。例如本题中的前 dep-1 层最小体积、最小侧面积就是这种想法。剪枝 5 则通过表面积与体积之间的关系, 对不等式进行缩放, $2(n-v) / r[\mathrm{dep}]$ 这个式子也是对前 $d e p-1$ 层侧面积的一个估计。这告诉我们在一般的剪枝不足以应对问题的时候, 也可以结合各维度之间的联系得到更加精准的前枝。在 $A^\ast$ 算法中, 我们会更详细地讲解这种 “未来预算”理论。

#include <cmath> 
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x7fffffff;
int n, m, minv[30], mins[30], ans = INF;
int h[30], r[30], s = 0, v = 0;

void dfs(int dep) {
	if (!dep) {
		if (v == n) ans = min(ans, s);
		return;
	}
	for (r[dep] = min((int)sqrt(n - v), r[dep + 1] - 1); r[dep] >= dep; r[dep]--)
		for (h[dep] = min((int)((double)(n-v) / r[dep] / r[dep]), h[dep+1] - 1); h[dep] >= dep; h[dep]--) {
			if (v + minv[dep-1] > n) continue;
			if (s + mins[dep-1] > ans) continue;
			if (s + (double)2 * (n - v) / r[dep] > ans) continue;
			if (dep == m) s += r[dep] * r[dep];
			s += 2 * r[dep] * h[dep];
			v += r[dep] * r[dep] * h[dep];
			dfs(dep - 1);
			if (dep == m) s -= r[dep] * r[dep];
			s -= 2 * r[dep] * h[dep];
			v -= r[dep] * r[dep] * h[dep];
		}
}

int main() {
	cin >> n >> m;
	minv[0] = mins[0] = 0;
	for (int i = 1; i <= m; i++) {
		minv[i] = minv[i-1] + i * i * i;
		mins[i] = mins[i-1] + i * i;
	}
	h[m+1] = r[m+1] = INF;
	dfs(m);
	cout << ans << endl;
	return 0;
}

Solution

---

169. 数独2

题目描述

请你将一个 $16 \times 16$ 的数独填写完整，使得每行、每列、每个 $4 \times 4$ 十六宫格内字母 $A \sim P$ 均恰好出现一次。

保证每个输入只有唯一解决方案。

输入格式

输入包含多组测试用例。

每组测试用例包括 $16$ 行，每行一组字符串，共 $16$ 个字符串。

第 $i$ 个字符串表示数独的第 $i$ 行。

字符串包含字符可能为字母 $A \sim P$ 或 -（表示等待填充）。

测试用例之间用单个空行分隔，输入至文件结尾处终止。

输出格式

对于每个测试用例，均要求保持与输入相同的格式，将填充完成后的数独输出。

每个测试用例输出结束后，输出一个空行。

输入样例：

--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- 

输出样例：

FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK 

算法分析

在 $9 * 9$ 的数独问题中, 我们只使用了 “优先选择能填的数字最少的位置” 这一策略, 并且只有当某个位置无法填数时才判定失败进行回溯。不过, 请读者考虑下面这个 $16 * 16$ 数独的局部情况:

如上图所示, 虽然每个位置都还有能填的数, 但是因为图中圈出的两个 $B$ 的影响, 导致 $B$ 不可能填入第一行中的任何一个空位。类似的还有其他更加复杂的情况。也就是说, 我们需要对数独进行更加全面的可行性判定, 尽早发现无解的分支执行回溯。

我们加入以下的可行性剪枝:

1. 遍历当前所有的空格
   (1) 若某个位置 $A \sim P$ 都不能填, 立即回溯。
   (2) 若某个位置只有 1 个字母可填, 立即填上这个字母。
2. 考虑所有的行
   (1) 若某个字母不能填在该行的任何一个空位上, 立即回溯。
   (2) 若某个字母只能填在该行的某一个空位上, 立即填写。
3. 考虑所有的列, 执行与第 2 步类似的过程。
4. 考虑所有的十六宫格, 执行类似的过程。

之后, 我们再选择可填的字母最少的位置, 枚举填写哪个字母作为分支。

使用位运算来进行常数优化仍然是必要的。不过, 因为上述剪枝较为复杂, 按照上一节中 $9 * 9$ 数独的位运算记录方法, 实现起来比较困难, 所以在本题中, 我们直接对每个位置保存一个 16 位二进制数, 存储该位置能填的数字情况, 一共 $16 * 16=256$ 个这样的二进制数。在每次递归前, 我们简单地把这 256 个数的副本记录在局部变量上, 在还原现场时直接恢复即可。

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
char s[16][16];
int cnt[1<<16], f[1<<16], num[16][16], n = 0;
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 1;
	int pre[16][16];
	memcpy(pre, num, sizeof(pre));
	for (int i = 0; i < 16; i++)
		for (int j = 0; j < 16; j++)
			if (s[i][j] == '-') {
				if (!num[i][j]) return 0;
				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 1;
					s[i][j] = '-';
					memcpy(num, pre, sizeof(num));
					return 0;
				}
			}
	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 (unsigned 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 0;
		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 1;
						s[i][j] = '-';
						memcpy(num, pre, sizeof(num));
						return 0;
					}
	}
	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 (unsigned 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 0;
		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 1;
						s[i][j] = '-';
						memcpy(num, pre, sizeof(num));
						return 0;
					}
	}
	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 (unsigned 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 0;
			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 1;
								s[i+p][j+q] = '-';
								memcpy(num, pre, sizeof(num));
								return 0;
							}
		}
	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 (unsigned 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 1;
		s[tx][ty] = '-';
		memcpy(num, pre, sizeof(num));
	}
	return 0;
}

void Sudoku() {
	for (int i = 1; i < 16; i++) cin >> 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;
	dfs(ans);
	for (int i = 0; i < 16; i++) {
		for (int j = 0; j < 16; j++) cout << s[i][j];
		cout << endl;
	}
	cout << endl;
}

int get_cnt(int i) {
	int k = i & -i;
	e[i].push_back(f[k]);
	for (unsigned int j = 0; j < e[i-k].size(); j++)
		e[i].push_back(e[i-k][j]);
	return cnt[i-k] + 1;
}

int main() {
	memset(f, 0, sizeof(f));
	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);
	while (cin >> s[0]) Sudoku();
	return 0;
}

数独可以转化为精确覆盖问题, 使用一种叫做 Dancing Links 的数据结构求解。这超出了我们的讨论范围, 学有余力的读者可以自行查阅相关资料。不过, 建议读者还是使用搜索算法实现深度优先遍历一节与本节中的共计三道数独问题, 因为算法思维能力的训练远比学习几个能直接拿来解决问题的数据结构重要。

Solution