Dots & Boxes Is PSPACE-Complete

DOI10.4230/LIPICS.MFCS.2021.25MaRDI QIDQ6168439zbMATH OpenOpenAlexFDO

Authors Kevin Buchin, Irina Kostitsyna

Publication date 8 August 2023

Full work available at URL https://arxiv.org/abs/2105.02837

zbMATH Keywords

combinatorial gamedots \& boxesPSPACE-complete

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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.

This page was built for publication: Dots & Boxes Is PSPACE-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168439)