Paper by Erik D. Demaine

Reference:

Josh Brunner, Lily Chung, Michael Coulombe, Erik D. Demaine, Timothy Gomez, and Jayson Lynch, “Complexity of Solo Chess with Unlimited Moves”, in Revised Selected Papers from the Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2022), edited by Jin Akiyama, Hiro Ito, and Toshinori Sakai, Lecture Notes in Computer Science, volume 14364, Tokyo, Japan, September 9–11, 2022, pages 149–174.

Abstract:

We analyze Solo Chess puzzles, where the input is an n × n board containing some standard Chess pieces of the same color, and the goal is to make a sequence of capture moves to reduce down to a single piece. Prior work analyzes this puzzle for a single piece type when each piece is limited to make at most two capture moves (as in the Solo Chess puzzles on chess.com). By contrast, we study when each piece can make an unlimited number of capture moves. We show that any single piece type can be solved in polynomial time in a general model of piece types, while any two standard Chess piece types are NP-complete. We also analyze the restriction (as on chess.com) that one piece type is unique and must be the last surviving piece, showing that in this case some pairs of piece types become tractable while others remain hard.

Comments:

The paper is also available as arXiv:2302.01405 and from SpringerLink.

Length:

The paper is 26 pages.

Availability:

The paper is available in PDF (498k).

See information on file formats.

[Google Scholar search]

Related papers:

SoloChess_JCDCGGG2022 (Complexity of Solo Chess with Unlimited Moves)