Uniform-Budget Solo Chess with Only Rooks or Only Knights Is Hard

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.