Abstract
Dominoes is a popular and well-known game possibly dating back three millennia. Players are given a set of domino tiles, each with two labeled square faces, and take turns connecting them into a growing chain of dominoes by matching identical faces. We show that single-player dominoes is in P, while multiplayer dominoes is hard: when players cooperate, the game is NP-complete, and when players compete, the game is PSPACE-complete. In addition, we show that these hardness results easily extend to games involving team play.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Stormdark, I.P., Media: Domino history (2010), http://www.domino-play.com/History.htm
Demaine, E.D., Demaine, M.L., Harvey, N.J., Uehara, R., Uno, T., Uno, Y.: Uno is hard, even for a single player. Theoretical Computer Science 521, 51–61 (2014)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)
Bóna, M.: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific (2011)
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company (1997)
Lichtenstein, D., Sipser, M.: Go is polynomial-space hard. J. ACM 27(2), 393–401 (1980)
Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. AK Peters, Limited (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Demaine, E.D., Ma, F., Waingarten, E. (2014). Playing Dominoes Is Hard, Except by Yourself. In: Ferro, A., Luccio, F., Widmayer, P. (eds) Fun with Algorithms. FUN 2014. Lecture Notes in Computer Science, vol 8496. Springer, Cham. https://doi.org/10.1007/978-3-319-07890-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-07890-8_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07889-2
Online ISBN: 978-3-319-07890-8
eBook Packages: Computer ScienceComputer Science (R0)