Paper by Erik D. Demaine
- Jeffrey Bosboom, Spencer Congero, Erik D. Demaine, Martin L. Demaine, and Jayson Lynch, “Losing at Checkers is Hard”, in The Mathematics of Various Entertaining Subjects (MOVES 2017), volume 3, to appear, Princeton University Press.
We prove computational intractability of variants of checkers:
(1) deciding whether there is a move that forces the other player to win in one move is NP-complete;
(2) checkers where players must always be able to jump on their turn is PSPACE-complete; and
(3) cooperative versions of (1) and (2) are NP-complete.
We also give cooperative checkers puzzles whose solutions are the letters of the alphabet.
- This paper is also available as arXiv:1806.05657.
- The paper is available in PDF (510k).
- See information on file formats.
- [Google Scholar search]
- Related webpages:
- Checkers Font
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 15, 2019 by