在不少校园活动或趣味数学节中，你很可能遇到过这样一个经典小游戏：“数位匹配”（或被称为 Bulls and Cows）。
上图清晰地展示了游戏规则：工作人员随机写下一个三位数（为简化后续分析，我们约定数字可以重复），参与者不断报出数字猜测。工作人员会根据你的猜测，给出“几个数字正确并且位置正确（A）”和“几个数字正确但是位置不正确（B）”的反馈，你需要根据这些反馈最终推理出正确答案。例如，若答案是 976，猜测 716 会得到“1A1B”，猜测 769 会得到“0A3B”。
据说，如果在 7 次内猜中就成功，3 次内猜中更能获得“欧皇”称号。我当初只用了三次就猜中了，但遗憾的是并未收到传说中的“独特奖励”，在此对主办方提出小小的“谴责”。抛开奖励不谈，这个游戏背后其实蕴含着深刻的数学原理。今天，我们就用信息论的视角，并借助计算机算法，来分析一下这个游戏的理论最优策略。
1. 建立数学模型
首先，让我们将游戏规则形式化。
设数字集合为 $D = \{0, 1, 2, ..., 9\}$，那么所有可能的有序三位数集合 $S$ 为：
$S = D \times D \times D$
这个集合的基数（总可能性）为 $|S| = 10^3 = 1000$。
我们用 $g$ 表示猜测值，$t$ 表示目标值。每次猜测后得到的反馈结果记为 $fb(g, t) = (A, B)$。
- $A$：满足 $g[i] = t[i]$ 的下标 $i$ 的个数，即数字和位置都正确的数量。
- $B$：满足 $g[i] = t[j]$ 且 $i \ne j$ 的下标对 $(i, j)$ 的个数。简单说，就是数字正确但位置不对的数量（需要排除已计入 $A$ 的数字）。
所有可能的反馈结果集合 $R$ 为：
$R = \{(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (2,0), (2,1), (3,0)\}$
注意：反馈 $(2, 1)$ 是不可能出现的。因为如果已经有两个数字位置完全正确（2A），剩下那个正确的数字（1B）只能放在唯一剩下的那个位置上，这就变成了 3A。
因此，总共有 10 种可能的反馈结果。
2. 信息论视角的推导
从信息论的角度看，每一次猜测的本质，是获取信息以减少候选答案集合的不确定性。
-
初始熵：假设目标数字在 1000 种可能性中均匀分布，初始的不确定性（信息熵）为：
$H_0 = \log_2 1000 \approx 9.97 \text{ bits}$
-
单次猜测的最大信息增益：理想情况下，如果我们的一次猜测 $g$ 能将当前的 $N$ 个候选组合完美地、均匀地划分到所有可能的反馈分类中，那么这次猜测能获得的最大信息量为：
$I_{\max} = \log_2 |R| = \log_2 10 \approx 3.32 \text{ bits}$
-
理论最少步数下界：根据 $H_0 / I_{\max}$，在最理想的均匀划分下，我们至少需要：
$steps_{\min} \ge \lceil \frac{H_0}{I_{\max}} \rceil \approx \lceil \frac{9.97}{3.32} \rceil = \lceil 3.00 \rceil = 3 \text{ 次}$
然而，这个“3次”只是理论下界。在实际游戏中，反馈结果的分布几乎不可能是完全均匀的，而且我们讨论的是“保证在任何情况下都能猜出”的策略，因此实际所需步数必然大于这个下界。
3. 极大极小策略
为了找到保证获胜的最少次数，我们需要一个确定性策略。Donald Knuth 在 1977 年提出的极大极小算法正是解决此类问题的经典方法。其核心思想非常直接：在当前步骤，选择一个猜测 $g$，使得对于所有可能的反馈结果 $r$，剩余的候选答案集合 $S_r$ 的规模中的最大值最小化。
通俗讲，就是做最坏的打算（得到最不利于缩小范围的反馈），争取最好的结果（即使最坏情况下，剩下的可能答案也尽可能少）。
分割函数：对于给定的猜测 $g$ 和当前的候选集 $C$，我们可以根据反馈 $r$ 将 $C$ 划分为多个互不相交的子集：
$C_r(g) = \{ t \in C \mid fb(g, t) = r \}$
显然，所有 $C_r(g)$ 的并集就是 $C$ 本身。
决策准则：我们需要找到一个猜测 $g$（注意，$g$ 可以不在当前候选集 $C$ 中），使得以下值最小化：
$V(g) = \max_{r \in R} |C_r(g)|$
这个 $V(g)$ 代表了选择 $g$ 后，在最坏反馈下会剩下多少个可能的答案。策略就是选择使 $V(g)$ 最小的 $g$ 作为本次猜测。得到真实反馈 $r‘$ 后，将候选集更新为 $C_{r’}(g)$，然后重复上述过程。你可以到云栈社区的算法与数据结构板块了解更多关于此类优化策略的讨论。
4. 结论与最少步数证明
通过计算机穷举搜索（是的，这已经超出了人脑手工计算的范围），我们可以证明以下结论：
- 4 次猜测不足以覆盖所有情况：存在某些“狡猾”的目标数字，使得任何预设的 4 步猜测序列都无法在第 4 步时将其唯一锁定。
- 5 次猜测是充分的：存在一种由极大极小算法生成的具体策略，使得无论目标数字是什么，在第 5 次猜测时（或之前）一定能得到 $3A0B$ 的反馈，即猜中答案。
最终结论：对于数字可重复的三位数猜谜游戏，在最坏情况下，保证一定能猜出来的最少次数为 5 次。
（至于这个策略具体是什么，以及穷举证明的详细过程……或许可以期待哪位高手在云栈社区写一篇更深入的续篇。）
5. C++ 代码实现：一个交互式求解器
理论很美，但实践更有趣。我编写了一个基于上述极大极小策略的 C++ 程序，它可以作为你的“游戏外挂”，在最多 5 步内猜出你心中所想的三位数。
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
// 计算两个三位数之间的反馈结果 (nA mB)
pair<int, int> get_feedback(const string& guess, const string& secret) {
int a = 0, b = 0;
int g_count[10] = {0}, s_count[10] = {0};
for (int i = 0; i < 3; ++i) {
if (guess[i] == secret[i]) {
a++; // 位置正确且数字正确
} else {
g_count[guess[i] - '0']++;
s_count[secret[i] - '0']++;
}
}
// 统计数字正确但位置不正确的数量
for (int i = 0; i < 10; ++i) {
b += min(g_count[i], s_count[i]);
}
return {a, b};
}
int main() {
// 1. 初始化所有 1000 个可能的组合 (000 - 999)
vector<string> all_codes;
for (int i = 0; i < 1000; ++i) {
string s = to_string(i);
while(s.length() < 3) s = "0" + s;
all_codes.push_back(s);
}
// 当前剩余的有效候选集
vector<string> candidates = all_codes;
cout << "=======================================\n";
cout << " 3位数字猜谜求解器 (基于 Minimax 算法) \n";
cout << "=======================================\n";
cout << "请在心中想好一个三位数字（例如 042，数字可重复）。\n";
cout << "对于我的每次猜测，请回复 'n m'（例如 1 1），\n";
cout << "如果你想结束或者我猜中了，请直接输入 'yes'。\n\n";
int attempt = 1;
while (true) {
string best_guess = candidates[0]; // 默认取第一个
// 2. 使用极大极小算法寻找最优猜测 (如果候选集较大)
// 为了加快开局速度，第一步通常固定猜 "012"
if (candidates.size() == 1000) {
best_guess = "012";
} else if (candidates.size() > 1) {
int min_max_size = 10000;
// 遍历所有可能的猜测，寻找能将最大剩余子集最小化的猜测
for (const string& guess : all_codes) {
map<pair<int, int>, int> feedback_counts;
for (const string& cand : candidates) {
feedback_counts[get_feedback(guess, cand)]++;
}
int max_size = 0;
for (auto& p : feedback_counts) {
if (p.second > max_size) max_size = p.second;
}
// 优先选择能缩小最大子集的猜测；
// 如果效果相同，优先选择本身就是候选答案的数字
bool is_cand = (find(candidates.begin(), candidates.end(), guess) != candidates.end());
bool best_is_cand = (find(candidates.begin(), candidates.end(), best_guess) != candidates.end());
if (max_size < min_max_size || (max_size == min_max_size && is_cand && !best_is_cand)) {
min_max_size = max_size;
best_guess = guess;
}
}
}
// 3. 输出猜测并读取用户输入
cout << "[第 " << attempt << " 次猜测] 我猜是: " << best_guess << endl;
cout << "请输入反馈 (n m) 或 yes: ";
string input;
cin >> input;
if (input == "yes" || input == "Yes" || input == "YES") {
cout << "\n太棒了！游戏结束，只用了 " << attempt << " 次就找到了答案！\n";
break;
}
// 解析输入的 n 和 m
int n = stoi(input);
int m;
cin >> m;
if (n == 3) {
cout << "\n太棒了！游戏结束，只用了 " << attempt << " 次就找到了答案！\n";
break;
}
// 4. 根据反馈过滤候选集
vector<string> next_candidates;
for (const string& cand : candidates) {
pair<int, int> fb = get_feedback(best_guess, cand);
if (fb.first == n && fb.second == m) {
next_candidates.push_back(cand);
}
}
candidates = next_candidates;
if (candidates.empty()) {
cout << "\n[错误] 没有符合条件的数字了！请检查之前的反馈是否给错。\n";
break;
}
cout << " -> 剩余可能答案数量: " << candidates.size() << "\n\n";
attempt++;
}
return 0;
}
你可以将这段 C++ 代码复制到本地编译运行，亲自体验这个“最强大脑”算法如何在 5 步之内破解你的数字。下次再玩这个游戏时，无论是作为参与者还是“庄家”，你都能洞悉其中的数学奥秘了。
发表于 3 小时前
|
查看: 1|
回复: 0
