引言
猜数字是一款经典的逻辑推理游戏，系统随机生成一个不重复数字组成的秘密数，玩家通过有限次数的猜测逐步缩小可能性空间。传统的二分搜索和信息论方法关注最坏情况下的最优策略，而本文将引入动态规划视角，将猜数字建模为状态空间上的最优决策问题，通过状态压缩和递推求解最优猜测序列。
问题建模
假设秘密数字由 $n$ 位不重复数字组成（标准版为4位，数字0-9）。每次猜测后获得反馈 $(A, B)$，表示：
– $A$：数字和位置都正确的个数（公牛）
– $B$：数字正确但位置不对的个数（奶牛）
所有可能的秘密构成状态空间 $S$，大小为 $P(10, n)$。每次猜测 $g$ 将状态空间划分为若干子集 $S_{(A,B)}$，每个子集包含所有对猜测 $g$ 产生相同反馈的候选秘密。
动态规划最优策略
定义 $dp(S)$ 为在候选集合 $S$ 下，保证猜中所需的最少次数。状态转移：
$$
dp(S) = 1 + \min_{g \in G} \max_{(A,B)} dp(S_{(A,B)})
$$
边界条件：$|S| = 1$ 时 $dp(S) = 0$，$|S| = 0$ 时为不可能状态。
对于4位标准猜数字，状态空间约 $10! / 6! = 5040$，可通过预计算和记忆化搜索高效求解。
Java实现
反馈计算与候选过滤
public class MastermindUtils {
/**
* 计算猜测guess对秘密secret的反馈 (A, B)
* A: 位置和数字都正确
* B: 数字正确但位置不对
*/
public static int[] getFeedback(String secret, String guess) {
int a = 0, b = 0;
boolean[] secretUsed = new boolean[secret.length()];
boolean[] guessUsed = new boolean[guess.length()];
// 先计算A
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
a++;
secretUsed[i] = true;
guessUsed[i] = true;
}
}
// 再计算B
for (int i = 0; i < guess.length(); i++) {
if (guessUsed[i]) continue;
for (int j = 0; j < secret.length(); j++) {
if (!secretUsed[j] && guess.charAt(i) == secret.charAt(j)) {
b++;
secretUsed[j] = true;
break;
}
}
}
return new int[]{a, b};
}
/**
* 生成所有n位不重复数字的候选集合
*/
public static List<String> generateCandidates(int n) {
List<String> candidates = new ArrayList<>();
boolean[] used = new boolean[10];
StringBuilder sb = new StringBuilder();
backtrack(candidates, used, sb, n);
return candidates;
}
private static void backtrack(List<String> candidates, boolean[] used, StringBuilder sb, int n) {
if (sb.length() == n) {
candidates.add(sb.toString());
return;
}
for (int i = 0; i <= 9; i++) {
if (used[i]) continue;
used[i] = true;
sb.append(i);
backtrack(candidates, used, sb, n);
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
/**
* 根据反馈过滤候选集合
*/
public static List<String> filterCandidates(List<String> candidates, String guess, int[] feedback) {
List<String> filtered = new ArrayList<>();
for (String secret : candidates) {
int[] fb = getFeedback(secret, guess);
if (fb[0] == feedback[0] && fb[1] == feedback[1]) {
filtered.add(secret);
}
}
return filtered;
}
}
动态规划求解器
import java.util.*;
public class MastermindDPSolver {
private int n; // 数字位数
private List<String> allCandidates;
// 记忆化：将候选集合编码为位掩码 -> 最优步数
private Map<Integer, Integer> memo;
private Map<Integer, String> bestGuessMemo;
public MastermindDPSolver(int n) {
this.n = n;
this.allCandidates = MastermindUtils.generateCandidates(n);
this.memo = new HashMap<>();
this.bestGuessMemo = new HashMap<>();
}
/**
* 将候选列表编码为位掩码（基于allCandidates的索引）
*/
private int encodeCandidates(List<String> candidates) {
int mask = 0;
for (String c : candidates) {
int idx = allCandidates.indexOf(c);
if (idx >= 0) mask |= (1 << idx);
}
return mask;
}
/**
* 从位掩码解码候选列表
*/
private List<String> decodeCandidates(int mask) {
List<String> list = new ArrayList<>();
for (int i = 0; i < allCandidates.size(); i++) {
if ((mask & (1 << i)) != 0) {
list.add(allCandidates.get(i));
}
}
return list;
}
/**
* 动态规划求解：返回在候选集合mask下保证猜中所需的最少次数
*/
public int solve(int mask) {
if (Integer.bitCount(mask) <= 1) return 0;
if (memo.containsKey(mask)) return memo.get(mask);
List<String> candidates = decodeCandidates(mask);
int minMaxDepth = Integer.MAX_VALUE;
String bestGuess = null;
// 遍历所有可能的猜测（包括不在候选中的猜测）
for (String guess : allCandidates) {
// 将候选按反馈分组
Map<String, List<String>> groups = new HashMap<>();
for (String secret : candidates) {
int[] fb = MastermindUtils.getFeedback(secret, guess);
String key = fb[0] + "," + fb[1];
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(secret);
}
// 计算最坏情况下的深度
int maxDepth = 0;
boolean valid = true;
for (List<String> group : groups.values()) {
if (group.size() == candidates.size()) {
// 这个猜测没有提供任何信息，跳过
valid = false;
break;
}
int subMask = encodeCandidates(group);
int depth = solve(subMask);
maxDepth = Math.max(maxDepth, depth);
}
if (!valid) continue;
// 选择最坏情况下最小的猜测
if (maxDepth < minMaxDepth) {
minMaxDepth = maxDepth;
bestGuess = guess;
}
}
memo.put(mask, minMaxDepth + 1);
bestGuessMemo.put(mask, bestGuess);
return minMaxDepth + 1;
}
/**
* 获取最优猜测
*/
public String getBestGuess(List<String> candidates) {
int mask = encodeCandidates(candidates);
// 确保已计算
solve(mask);
return bestGuessMemo.get(mask);
}
/**
* 完整游戏模拟
*/
public void playGame(String secret) {
List<String> candidates = new ArrayList<>(allCandidates);
int steps = 0;
System.out.println("秘密数字: " + secret);
System.out.println("初始候选数: " + candidates.size());
while (candidates.size() > 1) {
String guess = getBestGuess(candidates);
int[] fb = MastermindUtils.getFeedback(secret, guess);
steps++;
System.out.printf("第%d步: 猜测 %s -> 反馈 (%dA%dB), 剩余候选 %d%n",
steps, guess, fb[0], fb[1],
MastermindUtils.filterCandidates(candidates, guess, fb).size());
candidates = MastermindUtils.filterCandidates(candidates, guess, fb);
}
System.out.println("猜中! 总步数: " + steps + ", 答案: " + candidates.get(0));
}
}
简化版：Minimax启发式策略
public class MastermindMinimaxSolver {
private List<String> allCandidates;
public MastermindMinimaxSolver(int n) {
this.allCandidates = MastermindUtils.generateCandidates(n);
}
/**
* Minimax策略：选择使最大候选组最小的猜测
* 这是Knuth提出的经典策略，计算效率高但非严格DP最优
*/
public String minimaxGuess(List<String> candidates) {
String bestGuess = null;
int minMaxSize = Integer.MAX_VALUE;
for (String guess : allCandidates) {
Map<String, Integer> groupSizes = new HashMap<>();
for (String secret : candidates) {
int[] fb = MastermindUtils.getFeedback(secret, guess);
String key = fb[0] + "," + fb[1];
groupSizes.merge(key, 1, Integer::sum);
}
int maxSize = groupSizes.values().stream().mapToInt(Integer::intValue).max().orElse(0);
if (maxSize < minMaxSize) {
minMaxSize = maxSize;
bestGuess = guess;
}
}
return bestGuess;
}
/**
* 期望值策略：选择使期望候选数最小的猜测
*/
public String expectedValueGuess(List<String> candidates) {
String bestGuess = null;
double minExpectedSize = Double.MAX_VALUE;
for (String guess : allCandidates) {
Map<String, Integer> groupSizes = new HashMap<>();
for (String secret : candidates) {
int[] fb = MastermindUtils.getFeedback(secret, guess);
String key = fb[0] + "," + fb[1];
groupSizes.merge(key, 1, Integer::sum);
}
double expectedSize = 0;
for (int size : groupSizes.values()) {
double prob = (double) size / candidates.size();
expectedSize += prob * size;
}
if (expectedSize < minExpectedSize) {
minExpectedSize = expectedSize;
bestGuess = guess;
}
}
return bestGuess;
}
}
主程序
public class GuessNumberGame {
public static void main(String[] args) {
int n = 4; // 4位猜数字
// DP求解器（适用于小规模，预计算较慢）
MastermindDPSolver dpSolver = new MastermindDPSolver(n);
// Minimax求解器（高效实用）
MastermindMinimaxSolver minimaxSolver = new MastermindMinimaxSolver(n);
String secret = "1234";
System.out.println("=== DP策略模拟 ===");
dpSolver.playGame(secret);
System.out.println("\n=== Minimax策略模拟 ===");
List<String> candidates = MastermindUtils.generateCandidates(n);
int steps = 0;
while (candidates.size() > 1) {
String guess = minimaxSolver.minimaxGuess(candidates);
int[] fb = MastermindUtils.getFeedback(secret, guess);
steps++;
System.out.printf("第%d步: 猜测 %s -> 反馈 (%dA%dB)%n", steps, guess, fb[0], fb[1]);
candidates = MastermindUtils.filterCandidates(candidates, guess, fb);
}
System.out.println("猜中! 总步数: " + steps);
}
}
复杂度分析
- 候选生成：$O(P(10, n))$，4位时为5040。
- 反馈计算：$O(n)$ 每次比较。
- Minimax策略：每次猜测 $O(|C| \cdot P(10, n) \cdot n)$，$|C|$ 为当前候选数。
- DP策略：状态数为 $2^{P(10,n)}$，4位时约 $2^{5040}$ 不可行。实际实现中对小规模（$|C| \le 20$）可用位掩码优化。
注：对于标准4位猜数字，Minimax策略已能在最坏情况下5步内求解，DP最优解为5步。
总结
本文将猜数字游戏建模为状态空间上的最优决策问题，通过Minimax和期望值策略实现高效求解。动态规划框架理论上可求得最优解，但受限于状态空间规模。实践中，结合信息论下界和启发式剪枝的Minimax策略是最优的选择，能在极小步数内破解任何秘密数字。
