Aravind, N. R.N. R.AravindMisra, NeeldharaNeeldharaMisraMittal, HarshilHarshilMittal2025-08-312025-08-312024-11-0110.1016/j.tcs.2024.1147262-s2.0-85201098981https://d8.irins.org/handle/IITG2025/28674We 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.falseCombinatorial games | NP-completeness | Solo ChessArticle1 November 20240114726arJournal0WOS:001296907300001