论文标题
寻找Wordle的获胜策略已完成
Finding a Winning Strategy for Wordle is NP-complete
论文作者
论文摘要
在本文中，我们对流行的单词猜测游戏Wordle给出了正式定义。我们表明，总的来说，确定给定的Wordle实例是否承认获胜策略是NP完成的。我们还表明，给定一个尺寸$ n $的Wordle实例，这是一种获奖策略，在最坏情况下（如果有）可以在时间$ n^{o（g）} $中找到$ g $猜测。
In this paper, we give a formal definition of the popular word-guessing game Wordle. We show that, in general, determining if a given Wordle instance admits a winning strategy is NP-complete. We also show that given a Wordle instance of size $N$, a winning strategy that uses $g$ guesses in the worst case (if any) can be found in time $N^{O(g)}$.
