Exactly 20 years ago at MFCS, Demaine posed the open problem whether the game of Dots & Boxes is PSPACE-complete. Dots & Boxes has been studied extensively, with for instance a chapter in Berlekamp et al. Winning Ways for Your Mathematical Plays, a whole book on the game The Dots and Boxes Game: Sophisticated Child's Play by Berlekamp, and numerous articles in the Games of No Chance series. While known to be NP-hard, the question of its complexity remained open. We resolve this question, proving that the game is PSPACE-complete by a reduction from a game played on propositional formulas.
|Title of host publication||46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021|
|Editors||Filippo Bonchi, Simon J. Puglisi|
|Number of pages||18|
|Publication status||Published - 1 Aug 2021|
|Name||Leibniz International Proceedings in Informatics, LIPIcs|
Bibliographical noteDBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
- Combinatorial game
- Dots & boxes