LIPIcs.FUN.2021.18.pdf
- Filesize: 1.14 MB
- 7 pages
Document
Hyperbolic Minesweeper Is in P
Author
Eryk Kopczyński 
-
Part of:
Volume:
10th International Conference on Fun with Algorithms (FUN 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-09-16
File
Document Identifiers
Author Details
Cite As Get BibTex
Eryk Kopczyński. Hyperbolic Minesweeper Is in P. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 18:1-18:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FUN.2021.18
Abstract
We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.
Subject Classification
ACM Subject Classification
- Theory of computation → Representations of games and their complexity
- Theory of computation → Parameterized complexity and exact algorithms
Keywords
- Minesweeper
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Sergio Bermudo, José M. Rodríguez, José M. Sigarreta, and Jean-Marie Vilaire. Gromov hyperbolic graphs. Discrete Mathematics, 313(15):1575-1585, 2013. URL: https://doi.org/10.1016/j.disc.2013.04.009.
- James W. Cannon, William J. Floyd, Richard Kenyon, Walter, and R. Parry. Hyperbolic geometry. In In Flavors of geometry, pages 59-115. University Press, 1997. Available online at URL: http://www.msri.org/communications/books/Book31/files/cannon.pdf.
-
Alexander Grigoriev. Tree-width and large grid minors in planar graphs. Discrete Mathematics & Theoretical Computer Science, 13:13-20, January 2011.
- Maxim Gumin. WaveFunctionCollapse, 2017. URL: https://github.com/mxgmn/WaveFunctionCollapse.
- Isaac Karth and Adam M. Smith. WaveFunctionCollapse is Constraint Solving in the Wild. In Proceedings of the 12th International Conference on the Foundations of Digital Games, FDG ’17, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3102071.3110566.
- Richard Kaye. Minesweeper is np-complete. The Mathematical Intelligencer, 22(2):9-15, March 2000. URL: https://doi.org/10.1007/BF03025367.
- Eryk Kopczyński, Dorota Celińska, and Marek Čtrnáct. Hyperrogue: Playing with hyperbolic geometry. In #1David Swart and Carlo H. Séquin and Kristóf Fenyvesi, editor, Proceedings of Bridges 2017#1: Mathematics, Art, Music, Architecture, Education, Culture, pages 9-16, Phoenix, Arizona, 2017. Tessellations Publishing. #1Available online at http://archive.bridgesmathart.org/2017/bridges2017-9.pdf.
- John Lamping, Ramana Rao, and Peter Pirolli. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI '95, pages 401-408, New York, NY, USA, 1995. ACM Press/Addison-Wesley Publishing Co. URL: https://doi.org/10.1145/223904.223956.
- Maurice Margenstern. Pentagrid and heptagrid: the fibonacci technique and group theory. Journal of Automata, Languages and Combinatorics, 19(1-4):201-212, 2014. URL: https://doi.org/10.25596/jalc-2014-201.
- Tamara Munzner. Exploring large graphs in 3d hyperbolic space. IEEE Computer Graphics and Applications, 18(4):18-23, 1998. URL: https://doi.org/10.1109/38.689657.
-
Fragkiskos Papadopoulos, Maksim Kitsak, M. Angeles Serrano, Marian Boguñá, and Dmitri Krioukov. Popularity versus Similarity in Growing Networks. Nature, 489:537-540, September 2012.
- N. Robertson, P. Seymour, and R. Thomas. Quickly excluding a planar graph. Journal of Combinatorial Theory, Series B, 62(2):323-348, 1994. URL: https://doi.org/10.1006/jctb.1994.1073.
- Zeno Rogue. HyperRogue: Experiments with Geometry, 2020. URL: http://www.roguetemple.com/z/hyper/geoms.php.
- Sci-Tech Binary Ltd. Co. Warped mines, 2019. URL: https://apps.apple.com/br/app/hypersweeper/id1450066199.