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 each piece performs at most as many captures as its budget allows. The time complexity of finding a winning sequence of captures has already been pinpointed for several combinations 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 only rooks with budget exactly 2, or only knights with budget exactly 11.

Bilò, D., Di Donato, L., Guala', L., Leucci, S. (2025). Uniform-budget solo chess with only rooks or only knights is hard. THEORETICAL COMPUTER SCIENCE, 1056 [10.1016/j.tcs.2025.115544].

Uniform-budget solo chess with only rooks or only knights is hard

Guala', Luciano;
2025-01-01

Abstract

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 each piece performs at most as many captures as its budget allows. The time complexity of finding a winning sequence of captures has already been pinpointed for several combinations 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 only rooks with budget exactly 2, or only knights with budget exactly 11.
2025
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INFO-01/A - Informatica
English
Board games
NP-completeness
Puzzle games
Solo chess
Bilò, D., Di Donato, L., Guala', L., Leucci, S. (2025). Uniform-budget solo chess with only rooks or only knights is hard. THEORETICAL COMPUTER SCIENCE, 1056 [10.1016/j.tcs.2025.115544].
Bilò, D; Di Donato, L; Guala', L; Leucci, S
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
TCS2026.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 2.79 MB
Formato Adobe PDF
2.79 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/458006
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact