前段时间，以黄绿色块矩阵图为交互界面的猜词游戏Wordle风靡社交网络，随后又诞生了各种变体游戏，比如中文成语变种、英语四词变种。如今风潮退去，让我们一起来看看“留在沙滩上的贝壳”。
Wordle游戏的规则非常简单，它要求玩家在6次之内猜出一个由5个字母组成的单词。每次输入单词时，如果输入的字母在目标单词中，但是位置不对，那么格子会显示成黄色；如果输入的字母在目标单词中，且位置正确，那么格子会显示成绿色；如果都不对，则会显示成灰色。玩家需要根据每次猜词后的反馈来调整自己的猜词策略，最终猜出单词。
虽然玩Wordle的大多数人都是自己乖乖猜词，但心思活络的人很自然就会想到：有没有可能借助计算机，弄出一个神奇的算法帮自己猜词呢？
玩Wordle时，一般人会先使用一两个固定的词打底，然后再猜符合之前提示的词，不断缩小范围直到猜出正确答案。通常情况下，这种思路行得通。但是，如果你遇到过下图中的情况，就会发现这种单纯的策略并不合适。我们需要更高级的策略。
在讨论算法之前，我们先来看一下手头可以使用的素材。Wordle所使用的单词表，可以在它的json代码里直接看到。单词表有两个，一个是从游戏上线第1天开始之后的2000多天，全部正确答案的列表；另一个，是这些正确答案以外可以合法猜测的单词列表，共10000多个。两个词表加起来的12972个单词，正好就是CSW19（Collins Scrabble Words，2019）中所有的五字母单词。
有了词表之后，初等的想法就是根据字母频率来选择单词。字母在词表里出现的次数越多，确定或排除之后就越好缩小范围。如果你在网上搜索一下，绝大多数讲Wordle猜词策略的文章，都是按照这个思路推荐的。所以，元音或常见字母多的adieu或是aisle就是很好的第一猜测。当然，这个算法相当简陋，但不需要电脑就可以做。接下来，让我们用数学化一点的思维，继续对这个想法进行分析。
从直觉上讲，猜一个词之后，颜色的提示根据黄绿灰3种颜色的不同，会有3^5=243种可能的组合。那么剩余的词表，也会按照上一个词的颜色提示拆成243个更小的词表。要是这些拆分后的小词表里，有一个包含的单词数量特别大，万一正确答案就在这个词表里，那么接下来就会很难猜。反之，拆分得越均匀，就说明不管正确答案在哪个词表里，都会相对好猜，这个第一次猜测的词也就越有效。
如何确定这种决策树存在或是证明其不存在呢？当然是靠试错和枚举。具体说来，第一层有一个词，这个词有12972种可能性。第一个词确定之后，第二层的词有最多243个词表，每一个词表又有12971种可能性……如果枚举完前5层所有可能的情况，就能找到一棵完整的树，那就说明一定有一个可行策略可以保证6次内猜中，如果没有，那就说明6次不够。
关于Wordle还有一些其他的进阶讨论。例如，倘若已知正解在那个2000多的词表里，则是最多5次猜中。在困难模式下，也就是每次猜的词，必须符合此前的所有提示的模式下，则需要7次才能保证猜中，平均需要4.52629次。对于词表甚至字母表都不同的变体（比如中文成语版本），找出多少步能保证猜中则是一个NP问题（Non-deterministic Polynomial，即多项式复杂程度的非确定性问题）。