2026-07-23T16:09:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19912 2024-05-29T09:43:29Z ddc:004 open_access

Uniform-Budget Solo Chess with Only Rooks or Only Knights Is Hard Bilò, Davide Di Donato, Luca Gualà, Luciano Leucci, Stefano solo chess puzzle games board games NP-completeness We study the Solo-Chess problem which has been introduced in [Aravind et al., FUN 2022]. This is a single-player variant of chess in which the player must clear all but one piece from the board via a sequence captures while ensuring that the number of captures performed by each piece does not exceed the piece’s budget. The time complexity of finding a winning sequence of captures has already been pinpointed for several combination of piece types and initial budgets. We contribute to a better understanding of the computational landscape of Solo-Chess by closing two problems left open in [Aravind et al., FUN 2022]. Namely, we show that Solo-Chess is hard even when all pieces are restricted to be only rooks with budget exactly 2, or only knights with budget exactly 11. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Luca Di Donato and Luciano Gualà and Stefano Leucci 2024 Is Part Of LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2024.4 urn:nbn:de:0030-drops-199121 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.4 eng https://creativecommons.org/licenses/by/4.0/legalcode