@inproceedings{3309c2a3bd0349f1b603e6ce0b09d2ed,
title = "Dots \& Boxes Is PSPACE-Complete",
abstract = "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.",
keywords = "Combinatorial game, Dots \& boxes, Pspace-complete",
author = "Kevin Buchin and Mart Hagedoorn and Irina Kostitsyna and \{van Mulken\}, Max",
year = "2021",
month = aug,
day = "18",
doi = "10.4230/LIPIcs.MFCS.2021.25",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "25:1--25:18",
editor = "Filippo Bonchi and Puglisi, \{Simon J.\}",
booktitle = "46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021",
note = "46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 ; Conference date: 23-08-2021 Through 27-08-2021",
}