Mastermind（珠玑妙算）是一款经典的密码破译桌游。游戏设定为：隐藏答案由 4 个颜色 peg 组成，每个 peg 可以是 6 种颜色之一，允许重复。猜测者每次提交一个 4 色组合，系统返回两个数值——黑色 peg 数（颜色和位置都正确）和白色 peg 数（颜色正确但位置错误）。本文用 Java 实现基于 Donald Knuth 最小最大算法的 Mastermind 求解器，保证在 5 步内破解任意密码。
核心算法思路
Knuth 于 1977 年提出的算法是 Mastermind 的最优策略之一，其核心思想是”最小最大原则”：
- 初始候选集：所有 6⁴ = 1296 种可能的密码组合。
- 评分函数：对于每个候选猜测，模拟它在当前候选集上可能得到的各种反馈（黑/白 peg 组合）。每种反馈会将候选集划分为一个子集。该猜测的”最坏情况得分”就是这些子集中剩余候选数的最大值。
- 选择策略：选择具有最小”最坏情况得分”的猜测。如果多个猜测得分相同，优先选择本身属于当前候选集的猜测（因为它可能是正确答案）。
这种策略保证每一步都将候选集缩小到尽可能小的规模，从而在理论上最多 5 步内找到答案。
Java 实现
import java.util.*;
public class MastermindSolver {
// 6 种颜色，用数字 1-6 表示
private static final int COLORS = 6;
private static final int SLOTS = 4;
// 所有可能的密码组合（1296 个）
private List<int[]> allCodes;
// 当前候选集
private List<int[]> candidates;
public MastermindSolver() {
this.allCodes = generateAllCodes();
this.candidates = new ArrayList<>(allCodes);
}
/**
* 生成所有 6^4 = 1296 种组合
*/
private List<int[]> generateAllCodes() {
List<int[]> codes = new ArrayList<>();
int[] code = new int[SLOTS];
generateRecursive(codes, code, 0);
return codes;
}
private void generateRecursive(List<int[]> codes, int[] code, int pos) {
if (pos == SLOTS) {
codes.add(code.clone());
return;
}
for (int c = 1; c <= COLORS; c++) {
code[pos] = c;
generateRecursive(codes, code, pos + 1);
}
}
/**
* 评估猜测与答案的反馈（黑 peg 数，白 peg 数）
* @return int[2] = {black, white}
*/
public int[] evaluate(int[] guess, int[] answer) {
int black = 0, white = 0;
boolean[] guessUsed = new boolean[SLOTS];
boolean[] answerUsed = new boolean[SLOTS];
// 统计黑色 peg（位置颜色都正确）
for (int i = 0; i < SLOTS; i++) {
if (guess[i] == answer[i]) {
black++;
guessUsed[i] = true;
answerUsed[i] = true;
}
}
// 统计白色 peg（颜色正确位置错误）
for (int i = 0; i < SLOTS; i++) {
if (guessUsed[i]) continue;
for (int j = 0; j < SLOTS; j++) {
if (!answerUsed[j] && guess[i] == answer[j]) {
white++;
answerUsed[j] = true;
break;
}
}
}
return new int[]{black, white};
}
/**
* 将反馈编码为字符串，用于 Map 的 Key
*/
private String encodeFeedback(int[] feedback) {
return feedback[0] + "B" + feedback[1] + "W";
}
/**
* 根据猜测和反馈过滤候选集
*/
public void filterCandidates(int[] guess, int[] feedback) {
List<int[]> filtered = new ArrayList<>();
for (int[] candidate : candidates) {
if (Arrays.equals(evaluate(guess, candidate), feedback)) {
filtered.add(candidate);
}
}
candidates = filtered;
}
/**
* 计算某个猜测在当前候选集上的最坏情况剩余候选数（Knuth 最小最大评分）
*/
public int minMaxScore(int[] guess) {
Map<String, Integer> partitionSizes = new HashMap<>();
for (int[] candidate : candidates) {
int[] fb = evaluate(guess, candidate);
String key = encodeFeedback(fb);
partitionSizes.merge(key, 1, Integer::sum);
}
// 最坏情况 = 最大分区大小
int maxSize = 0;
for (int size : partitionSizes.values()) {
if (size > maxSize) maxSize = size;
}
return maxSize;
}
/**
* 选择最优猜测（最小最大原则）
*/
public int[] chooseBestGuess() {
int[] bestGuess = null;
int bestScore = Integer.MAX_VALUE;
boolean bestInCandidates = false;
// 遍历所有可能的猜测（全 1296 个）
for (int[] guess : allCodes) {
int score = minMaxScore(guess);
boolean inCandidates = false;
for (int[] c : candidates) {
if (Arrays.equals(guess, c)) {
inCandidates = true;
break;
}
}
// 优先选择得分更低的；得分相同时优先选择候选集中的
if (score < bestScore || (score == bestScore && inCandidates && !bestInCandidates)) {
bestScore = score;
bestGuess = guess;
bestInCandidates = inCandidates;
}
}
return bestGuess;
}
/**
* 求解流程
*/
public List<int[]> solve(int[] secret, int maxSteps) {
List<int[]> history = new ArrayList<>();
candidates = new ArrayList<>(allCodes);
// Knuth 建议第一步固定用 1122（两种颜色各两个）
int[] firstGuess = new int[]{1, 1, 2, 2};
history.add(firstGuess);
if (Arrays.equals(firstGuess, secret)) {
System.out.println("Solved in 1 step!");
return history;
}
int[] fb = evaluate(firstGuess, secret);
filterCandidates(firstGuess, fb);
for (int step = 1; step < maxSteps; step++) {
if (candidates.isEmpty()) {
System.out.println("Error: no candidates left!");
break;
}
int[] guess = chooseBestGuess();
history.add(guess);
if (Arrays.equals(guess, secret)) {
System.out.println("Solved in " + (step + 1) + " steps!");
break;
}
fb = evaluate(guess, secret);
filterCandidates(guess, fb);
}
return history;
}
private String codeToString(int[] code) {
return Arrays.toString(code).replace(" ", "");
}
public static void main(String[] args) {
MastermindSolver solver = new MastermindSolver();
Random rand = new Random();
// 随机生成一个秘密密码
int[] secret = new int[]{rand.nextInt(6) + 1, rand.nextInt(6) + 1,
rand.nextInt(6) + 1, rand.nextInt(6) + 1};
System.out.println("Secret: " + solver.codeToString(secret));
List<int[]> result = solver.solve(secret, 10);
System.out.println("Steps: " + result.size());
for (int i = 0; i < result.size(); i++) {
int[] fb = solver.evaluate(result.get(i), secret);
System.out.println("Step " + (i + 1) + ": " + solver.codeToString(result.get(i))
+ " -> " + fb[0] + "B" + fb[1] + "W");
}
}
}
算法分析
时间复杂度：每次选择最优猜测需要遍历全部 1296 种组合，对每个组合计算最坏情况分区大小需要遍历候选集（最坏 1296 个），每次评估需要 O(SLOTS²) = O(16)。因此单次选择的复杂度约为 O(1296² × 16) ≈ 2700 万次操作。对于 5 步求解来说，在现代 CPU 上可在毫秒级完成。
空间复杂度：存储所有组合和候选集，O(1296 × 4) 可忽略不计。
理论保证：Knuth 证明，使用最小最大策略从 1122 开始，最多 5 步即可破解任意 Mastermind 密码。该算法不是平均步数最优的，但最坏情况最优。
扩展优化
- ** Irving 改进**：在评分时不仅考虑最坏情况，还同时考虑平均情况的分区大小，可略微降低平均步数。
- 遗传算法：对于颜色数更多、槽位更多的变体（如 8 色 5 槽），穷举搜索不可行，可用遗传算法近似求解最优猜测。
- Web 版本：将求解器封装为 REST API，用户输入反馈即可获取 AI 推荐的下一次猜测。
总结
Mastermind 求解器展示了最小最大原则在组合搜索问题中的强大威力。通过将密码空间系统性地划分为反馈等价类，并在每一步选择能将最大等价类最小化的猜测，我们得到了一个理论上保证 5 步内求解的最优策略。这一思想同样适用于诊断测试设计、实验规划等信息获取场景。
