2026-07-22T00:02:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25746 2026-06-23T12:45:43Z ddc:004 open_access

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings Are Hard Kühn, Kolja Yi, Wendy Solo chess puzzle games board games NP-completeness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kolja Kühn and Wendy Yi 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.27 urn:nbn:de:0030-drops-257464 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.27 eng https://creativecommons.org/licenses/by/4.0/legalcode