Paper by Erik D. Demaine
- Erik D. Demaine, Fermi Ma, and Erik Waingarten, “Playing Dominoes is Hard, Except by Yourself”, in Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), Lipari Island, Italy, July 1–3, 2014, pages 137–146.
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
- The paper is available in PDF (2203k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated April 22, 2019 by