Wordle是风靡全球的文字猜词游戏，玩家需在6次机会内猜出一个5字母单词。每次猜测后，系统反馈每个字母的位置状态（绿、黄、灰）。本文用Java实现Wordle求解器，讲解信息论熵减策略与贪心最优猜测算法。
问题建模与信息论基础
Wordle的核心是信息获取：每次猜测后，根据反馈将候选词空间大幅缩小。信息论中的信息熵可量化一次猜测的期望信息量，贪心策略即选择期望熵减最大的单词。
import java.io.*;
import java.nio.file.*;
import java.util.*;
public class WordleSolver {
static List<String> wordList; // 候选词表
static final int WORD_LEN = 5;
// 反馈状态：0=灰色(不存在), 1=黄色(存在但位置错), 2=绿色(位置正确)
static class Feedback {
int[] state = new int[WORD_LEN];
Feedback(int[] s) { System.arraycopy(s, 0, state, 0, WORD_LEN); }
@Override
public boolean equals(Object o) {
if (!(o instanceof Feedback)) return false;
return Arrays.equals(state, ((Feedback) o).state);
}
@Override
public int hashCode() { return Arrays.hashCode(state); }
}
// 计算猜测guess对答案answer的反馈
static Feedback computeFeedback(String guess, String answer) {
int[] state = new int[WORD_LEN];
boolean[] used = new boolean[WORD_LEN];
// 先标记绿色
for (int i = 0; i < WORD_LEN; i++) {
if (guess.charAt(i) == answer.charAt(i)) {
state[i] = 2;
used[i] = true;
}
}
// 再标记黄色
for (int i = 0; i < WORD_LEN; i++) {
if (state[i] == 2) continue;
for (int j = 0; j < WORD_LEN; j++) {
if (!used[j] && guess.charAt(i) == answer.charAt(j)) {
state[i] = 1;
used[j] = true;
break;
}
}
}
return new Feedback(state);
}
熵计算与最优猜测选择
// 计算某个猜测的期望信息熵（香农熵）
static double computeEntropy(String guess, List<String> candidates) {
Map<Feedback, Integer> patternCount = new HashMap<>();
for (String answer : candidates) {
Feedback fb = computeFeedback(guess, answer);
patternCount.merge(fb, 1, Integer::sum);
}
double entropy = 0.0;
int total = candidates.size();
for (int count : patternCount.values()) {
if (count > 0) {
double p = (double) count / total;
entropy -= p * (Math.log(p) / Math.log(2)); // 以2为底
}
}
return entropy;
}
// 从候选词中选择熵最大的作为最优猜测
static String chooseBestGuess(List<String> candidates, List<String> allWords) {
String best = null;
double maxEntropy = -1;
// 限制评估数量以加速，优先从候选词中选
List<String> toEvaluate = new ArrayList<>(candidates);
if (toEvaluate.size() < 50) {
// 候选较少时，也考虑所有词
for (String w : allWords) {
if (!toEvaluate.contains(w)) toEvaluate.add(w);
}
}
for (String guess : toEvaluate) {
double ent = computeEntropy(guess, candidates);
if (ent > maxEntropy) {
maxEntropy = ent;
best = guess;
}
}
return best;
}
候选词过滤与求解流程
// 根据反馈过滤候选词
static List<String> filterCandidates(List<String> candidates,
String guess, Feedback fb) {
List<String> filtered = new ArrayList<>();
for (String w : candidates) {
if (computeFeedback(guess, w).equals(fb)) {
filtered.add(w);
}
}
return filtered;
}
// 求解指定答案，返回猜测次数
static int solve(String answer, List<String> allWords) {
List<String> candidates = new ArrayList<>(allWords);
int turns = 0;
while (turns < 20) {
String guess = chooseBestGuess(candidates, allWords);
turns++;
if (guess == null) return -1;
Feedback fb = computeFeedback(guess, answer);
if (Arrays.equals(fb.state, new int[]{2,2,2,2,2})) {
return turns;
}
candidates = filterCandidates(candidates, guess, fb);
if (candidates.isEmpty()) return -1;
}
return turns;
}
主程序与统计
public static void main(String[] args) throws IOException {
// 加载5字母词表（约2300个常见词）
wordList = Files.readAllLines(Path.of("words.txt"));
wordList.removeIf(w -> w.length() != WORD_LEN);
wordList.replaceAll(String::toLowerCase);
System.out.println("词表大小: " + wordList.size());
// 统计所有词的平均猜测次数
int totalTurns = 0;
int solved = 0;
Map<Integer, Integer> distribution = new HashMap<>();
Random rand = new Random(42);
// 抽样测试1000个词
for (int i = 0; i < 1000; i++) {
String answer = wordList.get(rand.nextInt(wordList.size()));
int turns = solve(answer, wordList);
if (turns > 0) {
totalTurns += turns;
solved++;
distribution.merge(turns, 1, Integer::sum);
}
}
System.out.printf("平均猜测次数: %.2f%n", (double) totalTurns / solved);
System.out.println("分布: " + distribution);
// 演示一局
String demoAnswer = "apple";
System.out.println("\n=== 演示: 答案=" + demoAnswer + " ===");
List<String> candidates = new ArrayList<>(wordList);
for (int turn = 1; turn <= 6; turn++) {
String guess = chooseBestGuess(candidates, wordList);
Feedback fb = computeFeedback(guess, demoAnswer);
System.out.printf("第%d次: %s -> %s%n", turn, guess,
Arrays.toString(fb.state).replace("0","灰").replace("1","黄").replace("2","绿"));
if (Arrays.equals(fb.state, new int[]{2,2,2,2,2})) break;
candidates = filterCandidates(candidates, guess, fb);
}
}
}
算法分析
信息熵策略：每次选择能将候选空间平均分割得最均匀的单词，最大化期望信息量。首词”slate”或”crane”因字母分布均匀，常作为最佳开局。
时间复杂度：每轮计算熵为 O(N^2)，其中 N 为候选词数（初始约2300）。通过缓存优化可将首词计算降至可接受范围。
空间复杂度：存储词表 O(N)，候选过滤 O(N)。
