2026-08-17T19:57:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15975 2024-03-06T10:56:59Z ddc:004 open_access

Chess Is Hard Even for a Single Player Aravind, N.R. Misra, Neeldhara Mittal, Harshil chess strategy board games NP-complete We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 × 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik N.R. Aravind and Neeldhara Misra and Harshil Mittal 2022 Is Part Of LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2022.5 urn:nbn:de:0030-drops-159753 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.5 eng https://creativecommons.org/licenses/by/4.0/legalcode