DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.3

Hive Is PSPACE-Hard

Authors: Daniël I. Andel and Benjamin G. Rin

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

Hive is an abstract strategy game played on a table with hexagonal pieces. First published in 2001, it was and continues to be highly popular among both casual and competitive players. In this paper, we show that for a suitably generalized version of the game, the computational problem of determining whether a given player in an arbitrary position has a winning strategy is PSPACE-hard. We do this by reduction from Formula Game, which is first reduced to an intermediate problem we call Formula Game Geography, after which the latter is reduced to our decision problem.

Cite as

Daniël I. Andel and Benjamin G. Rin. Hive Is PSPACE-Hard. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andel_et_al:LIPIcs.FUN.2026.3,
  author =	{Andel, Dani\"{e}l I. and Rin, Benjamin G.},
  title =	{{Hive Is PSPACE-Hard}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.3},
  URN =		{urn:nbn:de:0030-drops-257221},
  doi =		{10.4230/LIPIcs.FUN.2026.3},
  annote =	{Keywords: Computational complexity, Combinatorial games, Hive, PSPACE-hardness, Formula Game, Generalized Geography}
}

Document

DOI: 10.4230/LIPIcs.FUN.2024.11

Hamiltonian Paths and Cycles in NP-Complete Puzzles

Authors: Marnix Deurloo, Mitchell Donkers, Mieke Maarse, Benjamin G. Rin, and Karen Schutte

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

Abstract

We show that several pen-and-paper puzzles are NP-complete by giving polynomial-time reductions from the Hamiltonian path and Hamiltonian cycle problems on grid graphs with maximum degree 3. The puzzles include Dotchi Loop, Chains, Linesweeper, Arukone{}₃ (also called Numberlink₃), and Araf. In addition, we show that this type of proof can still be used to prove the NP-completeness of Dotchi Loop even when the available puzzle instances are heavily restricted. Together, these results suggest that this approach holds promise in general for finding NP-completeness proofs of many pen-and-paper puzzles.

Cite as

Marnix Deurloo, Mitchell Donkers, Mieke Maarse, Benjamin G. Rin, and Karen Schutte. Hamiltonian Paths and Cycles in NP-Complete Puzzles. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deurloo_et_al:LIPIcs.FUN.2024.11,
  author =	{Deurloo, Marnix and Donkers, Mitchell and Maarse, Mieke and Rin, Benjamin G. and Schutte, Karen},
  title =	{{Hamiltonian Paths and Cycles in NP-Complete Puzzles}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{11:1--11:25},
  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.11},
  URN =		{urn:nbn:de:0030-drops-199199},
  doi =		{10.4230/LIPIcs.FUN.2024.11},
  annote =	{Keywords: Hamiltonicity, NP-completeness, complexity theory, pen-and-paper puzzles}
}

Document

DOI: 10.4230/LIPIcs.FUN.2024.27

Arimaa Is PSPACE-Hard

Authors: Benjamin G. Rin and Atze Schipper

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

Abstract

Arimaa is a strategy board game developed in 2003 by Omar Syed, designed to be hard for AI to win because of its large branching factor. In this paper, its theoretical complexity is considered. We prove that Arimaa (suitably generalized to an n × n board) is PSPACE-hard. This result is found by reducing a known PSPACE-hard variant of Generalized Geography to a variant of Arimaa that we call Arimaa^′, which in turn is then reduced to (n × n) Arimaa. Since the game is easily seen to be solvable in exponential time, it follows that its complexity lies somewhere between being PSPACE-complete and EXPTIME-complete.

Cite as

Benjamin G. Rin and Atze Schipper. Arimaa Is PSPACE-Hard. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rin_et_al:LIPIcs.FUN.2024.27,
  author =	{Rin, Benjamin G. and Schipper, Atze},
  title =	{{Arimaa Is PSPACE-Hard}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{27:1--27:24},
  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.27},
  URN =		{urn:nbn:de:0030-drops-199359},
  doi =		{10.4230/LIPIcs.FUN.2024.27},
  annote =	{Keywords: Arimaa, complexity theory, PSPACE-hardness, board games, Generalized Geography}
}

Search Results

Documents authored by Rin, Benjamin G.

Hive Is PSPACE-Hard

Abstract

Cite as

Hamiltonian Paths and Cycles in NP-Complete Puzzles

Abstract

Cite as

Arimaa Is PSPACE-Hard

Abstract

Cite as

Thanks for your feedback!

Could not send message