Dots & Boxes Is PSPACE-Complete

Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken

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

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.

Original languageEnglish
Title of host publication46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
EditorsFilippo Bonchi, Simon J. Puglisi
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages25:1-25:18
Number of pages18
ISBN (Electronic)978-3-95977-201-3
DOIs
Publication statusPublished - 18 Aug 2021
Event46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 - Tallinn, Estonia
Duration: 23 Aug 202127 Aug 2021

Publication series

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

Conference

Conference46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
Country/TerritoryEstonia
CityTallinn
Period23/08/2127/08/21

Keywords

  • Combinatorial game
  • Dots & boxes
  • Pspace-complete

Fingerprint

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

Cite this