Dots & Boxes Is PSPACE-Complete

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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.

Original languageEnglish
Title of host publication46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
EditorsFilippo Bonchi, Simon J. Puglisi
Number of pages18
ISBN (Electronic)9783959772013
Publication statusPublished - 1 Aug 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969

Bibliographical note

DBLP License: DBLP's bibliographic metadata records provided through 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
  • Pspace-complete


Dive into the research topics of 'Dots & Boxes Is PSPACE-Complete'. Together they form a unique fingerprint.

Cite this