Man, these New York Times games are hard! A computational perspective
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912585550397440 |
|---|---|
| author | Alberti, Alessandro Giovanni Chierichetti, Flavio Giacchini, Mirko Muscillo, Daniele Panconesi, Alessandro Tani, Erasmo |
| author_facet | Alberti, Alessandro Giovanni Chierichetti, Flavio Giacchini, Mirko Muscillo, Daniele Panconesi, Alessandro Tani, Erasmo |
| contents | The New York Times (NYT) games have found widespread popularity in recent years and reportedly account for an increasing fraction of the newspaper's readership. In this paper, we bring the computational lens to the study of New York Times games and consider four of them not previously studied: Letter Boxed, Pips, Strands and Tiles. We show that these games can be just as hard as they are fun. In particular, we characterize the hardness of several variants of computational problems related to these popular puzzle games. For Letter Boxed, we show that deciding whether an instance is solvable is in general NP-Complete, while in some parameter settings it can be done in polynomial time. Similarly, for Pips we prove that deciding whether a puzzle has a solution is NP-Complete even in some restricted classes of instances. We then show that one natural computational problem arising from Strands is NP-Complete in most parameter settings. Finally, we demonstrate that deciding whether a Tiles puzzle is solvable with a single, uninterrupted combo requires polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10846 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Man, these New York Times games are hard! A computational perspective Alberti, Alessandro Giovanni Chierichetti, Flavio Giacchini, Mirko Muscillo, Daniele Panconesi, Alessandro Tani, Erasmo Computational Complexity The New York Times (NYT) games have found widespread popularity in recent years and reportedly account for an increasing fraction of the newspaper's readership. In this paper, we bring the computational lens to the study of New York Times games and consider four of them not previously studied: Letter Boxed, Pips, Strands and Tiles. We show that these games can be just as hard as they are fun. In particular, we characterize the hardness of several variants of computational problems related to these popular puzzle games. For Letter Boxed, we show that deciding whether an instance is solvable is in general NP-Complete, while in some parameter settings it can be done in polynomial time. Similarly, for Pips we prove that deciding whether a puzzle has a solution is NP-Complete even in some restricted classes of instances. We then show that one natural computational problem arising from Strands is NP-Complete in most parameter settings. Finally, we demonstrate that deciding whether a Tiles puzzle is solvable with a single, uninterrupted combo requires polynomial time. |
| title | Man, these New York Times games are hard! A computational perspective |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2509.10846 |