The symmetric functions catalog

#NP-complete puzzle games

David Eppstein’s list of hard games gives a useful overview.

For a survey, see [KPS08].

Dota Underlords is NP-complete [PS20].

• Minesweeper

• LaserTank

• Bust-a-Move (Puzzle Bobble), see [DL16].

• Sokoban

• Tetris

Bibliography

1. [DL16]Erik D. Demaine and Stefan Langerman. Bust-a-move/puzzle bobble is NP-complete. Discrete and computational geometry and graphs, 9943:94–104, 2016.
   .bib

   Copy Download

   @incollection{DemaineLangerman2016,
     author = {Erik D. Demaine and Stefan Langerman},
     title = {Bust-a-Move/Puzzle Bobble Is {NP}-complete},
     booktitle = {Discrete and Computational Geometry and Graphs},
     series = {Lecture Notes in Computer Science},
     volume = {9943},
     pages = {94--104},
     year = {2016},
     doi = {10.1007/978-3-319-48532-4_9}
   }
   

2. [KPS08]Graham Kendall, Andrew Parkes and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, 31(1):13–34, 2008.
   .bib

   Copy Download

   @article{KendallParkesSpoerer2008,
     author = {Graham Kendall and Andrew Parkes and Kristian Spoerer},
     title = {A survey of {NP}-complete puzzles},
     journal = {ICGA Journal},
     volume = {31},
     number = {1},
     pages = {13--34},
     year = {2008},
     doi = {10.3233/ICG-2008-31103}
   }
   

3. [PS20]Alexander A. Ponomarenko and Dmitry V. Sirotkin. Dota underlords game is NP-complete. arXiv:2007.05020, 2020.
   .bib

   Copy Download

   @article{PonomarenkoSirotkin2020x,
     author = {Alexander A. Ponomarenko and Dmitry V. Sirotkin},
     title = {Dota Underlords game is {NP}-complete},
     journal = {arXiv e-prints},
     year = {2020},
     eprint = {2007.05020},
     url = {https://arxiv.org/abs/2007.05020}
   }