Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
For researchers in computational complexity and combinatorial game theory, this work resolves the open classification of 2-Solo Chess for all standard chess piece types.
The paper completes the complexity classification of 2-Solo Chess by proving that the problem is NP-complete for instances restricted to knights or kings, extending previous results that showed polynomial-time solvability for pawns and NP-completeness for rooks, bishops, or queens.
We extend the study of the 2-Solo Chess problem which was first introduced by Aravind, Misra, and Mittal in 2022. 2-Solo Chess is a single-player variant of chess in which the player must clear the board via captures such that only one piece remains, with each piece capturing at most twice. It is known that the problem is solvable in polynomial time for instances containing only pawns, while it becomes NP-complete for instances restricted to rooks, bishops, or queens. In this work, we complete the complexity classification by proving that 2-Solo Chess is NP-complete if the instance contains only knights or only kings.