@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 Mulken, {Max van}",
note = "DBLP 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.",
year = "2021",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.MFCS.2021.25",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "25:1--25:18",
editor = "Filippo Bonchi and Puglisi, {Simon J.}",
booktitle = "46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021",
}