LIPIcs.FUN.2022.19.pdf
- Filesize: 0.72 MB
- 8 pages
Document
Wordle Is NP-Hard
Authors
Bernardo Subercaseaux 
-
Part of:
Volume:
11th International Conference on Fun with Algorithms (FUN 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-05-23
File
Document Identifiers
Author Details
Acknowledgements
We thank anonymous reviewers for helpful suggestions, Mark Polyakov for pointing out a minor bug in a previous proof of Theorem 1, and Wassim Bouaziz for pointing out some imprecisions in a previous version of this paper. The second author thanks Jérémy Barbay for his insightful conversation, and his awesome friends: Saranya Vijayakumar for proofreading the English in an earlier draft of this paper, and Bailey Miller for providing him a place (and tea) to work on this article.
Cite As Get BibTex
Daniel Lokshtanov and Bernardo Subercaseaux. Wordle Is NP-Hard. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 19:1-19:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.19
Abstract
Wordle is a single-player word-guessing game where the goal is to discover a secret word w that has been chosen from a dictionary D. In order to discover w, the player can make at most 𝓁 guesses, which must also be words from D, all words in D having the same length k. After each guess, the player is notified of the positions in which their guess matches the secret word, as well as letters in the guess that appear in the secret word in a different position. We study the game of Wordle from a complexity perspective, proving NP-hardness of its natural formalization: to decide given a dictionary D and an integer 𝓁 if the player can guarantee to discover the secret word within 𝓁 guesses. Moreover, we prove that hardness holds even over instances where words have length k = 5, and that even in this case it is NP-hard to approximate the minimum number of guesses required to guarantee discovering the secret word. We also present results regarding its parameterized complexity and offer some related open problems.
Subject Classification
ACM Subject Classification
- Theory of computation → Problems, reductions and completeness
Keywords
- wordle
- np-hardness
- complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jérémy Barbay and Bernardo Subercaseaux. The computational complexity of evil hangman. In 10th International Conference on Fun with Algorithms (FUN 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
- M. Chlebík and J. Chlebíková. Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation, 206(11):1264-1275, November 2008. URL: https://doi.org/10.1016/j.ic.2008.07.003.
- Miroslav Chlebík and Janka Chlebíková. Approximation hardness of edge dominating set problems. Journal of Combinatorial Optimization, 11(3):279-290, May 2006. URL: https://doi.org/10.1007/s10878-006-7908-0.
- New York Times Company. Wordle is joining the new york times games. https://www.nytco.com/press/wordle-new-york-times-games/, 2022. Accessed: 2022-02-17.
- David Eppstein. Computational complexity of games and puzzles. https://www.ics.uci.edu/~eppstein/cgt/hard.html, 1997. Accessed: 2022-02-17.
- Sam Ganzfried. Computing strong game-theoretic strategies in jotto. In Lecture Notes in Computer Science, pages 282-294. Springer Berlin Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-31866-5_24.
- Michael T. Goodrich. On the algorithmic complexity of the mastermind game with black-peg results. Information Processing Letters, 109(13):675-678, June 2009. URL: https://doi.org/10.1016/j.ipl.2009.02.021.
-
Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. A. K. Peters, Ltd., USA, 2009.
- Nicole Holliday and Ben Zimmer. Wordle’s creator thinks he knows why the game has gone so viral. https://slate.com/culture/2022/01/wordle-game-creator-wardle-twitter-scores-strategy-stats.html, 2022. Accessed: 2022-02-17.
- Meeta Malhotra. Wordle’s viral success is based on design. https://thehardcopy.co/wordles-viral-success-is-based-on-design/, 2022. Accessed: 2022-02-17.
- Erin Sebo. Codecracking, community and competition: why the word puzzle wordle has become a new online obsession. https://theconversation.com/codecracking-community-and-competition-why-the-word-puzzle-wordle-has-become-a-new-online-obsession-174878, 2022. Accessed: 2022-02-17.
- Jeff Stuckman and Guo-Qiang Zhang. Mastermind is np-complete, 2005. URL: http://arxiv.org/abs/cs/0512049.
- Daniel Victor. Wordle is a love story. https://www.nytimes.com/2022/01/03/technology/wordle-word-game-creator.html, 2022. Accessed: 2022-02-17.
-
Giovanni Viglietta. Hardness of mastermind. In Evangelos Kranakis, Danny Krizanc, and Flaminia Luccio, editors, Fun with Algorithms, pages 368-378, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.