License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.19
URN: urn:nbn:de:0030-drops-159893
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15989/
Go to the corresponding LIPIcs Volume Portal

Lokshtanov, Daniel ; Subercaseaux, Bernardo

Wordle Is NP-Hard

pdf-format:
LIPIcs-FUN-2022-19.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{lokshtanov_et_al:LIPIcs.FUN.2022.19,
  author =	{Lokshtanov, Daniel and Subercaseaux, Bernardo},
  title =	{{Wordle Is NP-Hard}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{19:1--19:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15989},
  URN =		{urn:nbn:de:0030-drops-159893},
  doi =		{10.4230/LIPIcs.FUN.2022.19},
  annote =	{Keywords: wordle, np-hardness, complexity}
}

Keywords: wordle, np-hardness, complexity
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI