DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.4

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

Authors: Davide Bilò, Luca Di Donato, Luciano Gualà, and Stefano Leucci

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

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 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.

Cite as

Davide Bilò, Luca Di Donato, Luciano Gualà, and Stefano Leucci. Uniform-Budget Solo Chess with Only Rooks or Only Knights Is Hard. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2024.4,
  author =	{Bil\`{o}, Davide and Di Donato, Luca and Gual\`{a}, Luciano and Leucci, Stefano},
  title =	{{Uniform-Budget Solo Chess with Only Rooks or Only Knights Is Hard}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.4},
  URN =		{urn:nbn:de:0030-drops-199121},
  doi =		{10.4230/LIPIcs.FUN.2024.4},
  annote =	{Keywords: solo chess, puzzle games, board games, NP-completeness}
}

Search Results

Documents authored by Di Donato, Luca

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

Abstract

Cite as

Thanks for your feedback!

Could not send message