Paper by Erik D. Demaine

Reference:

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.

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.

Availability:

The paper is available in PDF (2203k).

See information on file formats.

[Google Scholar search]