2026-07-22T06:26:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14465 2024-03-06T10:54:05Z ddc:004 open_access

Dots & Boxes Is PSPACE-Complete Buchin, Kevin Hagedoorn, Mart Kostitsyna, Irina van Mulken, Max Dots & Boxes PSPACE-complete combinatorial game 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Mart Hagedoorn and Irina Kostitsyna and Max van Mulken 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.25 urn:nbn:de:0030-drops-144657 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.25 eng https://creativecommons.org/licenses/by/4.0/legalcode