CS Paper Radar

Puzznic is PSPACE-Complete

Jake Anderson, Lars Magnus Hvattum, András Z. Salamon

cs.CC cs.CG ·submitted 2026-10-16 15:41 UTC · v1
theory

Abstract

We prove that deciding solvability of Puzznic, a falling-block puzzle game originally developed by Taito, is PSPACE-complete. To show hardness we construct a self-closing door gadget using Puzznic's game mechanics. For membership, we show that the configuration space is exponentially bounded and apply Savitch's theorem. We also improve an existing NP-completeness proof for a simpler version of the game known as Cubic, showing that this game is NP-complete even when restricted to only two kinds of blocks.

Comment
15 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

cs.CC cs.GTmath.CO ·2026-11-12 ·Ethan Dickey, Ethan Mader
similarity 0.63
Abstract · 55 pages, 6 figures, 5 tables

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

0.24

The Two-Level Poset Game is PSPACE-Complete

cs.CC cs.DMcs.GTmath.CO ·2026-10-14 ·Kengo Hashimoto
similarity 0.62
Abstract

Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

0.25

The Complexity of Undirected Partizan Edge Geography

cs.DS math.CO ·2026-09-16 ·Yuto Okada
similarity 0.56
Abstract · 9 pages, 6 figures

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

0.53

Planar PArcK is PSPACE-complete

cs.CC cs.DMmath.CO ·2026-11-15 ·Craig Tennenhouse, Kanae Yoshiwatari
similarity 0.55
Abstract · 9 pages

Partizan Arc Kayles, or PArcK, is a partizan combinatorial game on edge colored graphs, and is a generalization of the game Domineering. Previously, PArcK was shown to be PSPACE-complete on bipartite graphs. In this paper we show that PArcK is PSPACE-complete even when restricted to planar graphs of degree at most three by a reduction from Generalized Hex.

0.24

Antichains for Concurrent Parameterized Games

cs.LO ·2026-10-08 ·Nathalie Bertrand, Patricia Bouyer, Gaëtan Staquet
published similarity 0.54
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898. A full version of this paper, containing all proofs, appears at arXiv:2505.13460

Concurrent parameterized games involve a fixed yet arbitrary number of players. They are described by finite arenas in which the edges are labeled with languages that describe the possible move combinations leading from one vertex to another (n players yield a word of length n). Previous work showed that, when edge labels are regular languages, one can decide whether a distinguished player, called Eve, has a strategy to ensure a reachability objective, against any strategy profile of her arbitrarily many opponents. This decision problem is known to be PSPACE-complete. A basic ingredient in the PSPACE-membership proof is the reduction to the exponential-size knowledge game, a 2-player game that reflects the knowledge Eve has on the number of opponents. In this paper, we provide a symbolic approach, based on antichains, to compute Eve's winning region in the knowledge game. In words, it gives the minimal knowledge Eve needs at every vertex to win the concurrent parameterized reachability game. More precisely, we propose two fixed-point algorithms that compute, as an antichain, the maximal elements of the winning region for Eve in the knowledge game. We implemented these two algorithms in C++, as well as the one initially proposed, and report on their relative performances on various benchmarks.

0.46

Hull Games of Induced Path Convexities in Graphs

cs.DM math.CO ·2026-09-21 ·Eurinardo Costa, Leon Almeida, Rudini Sampaio
theory similarity 0.53
Abstract

In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024, Araújo et al. obtained the first PSPACE-hardness proofs on some of these geodesic games and generalized them to any graph convexity. In this paper, we investigate convexity games on several known induced path convexities: the monophonic $\mathrm{m}$-convexity and the $\ell_k$-convexities, based on induced paths and on induced paths of size at most $k$. We prove that the hull games $\mathrm{CHG}_{\mathrm{m}}$, $\mathrm{CHG}_{\ell_k}$ and their misère variants are PSPACE-complete for every $k\ge2$ even in graphs with diameter at most 3. We also use the Sprague-Grundy Theory to obtain a polynomial time algorithm to decide the winner of the games $\mathrm{CHG}_{\mathrm{m}}$ and $\mathrm{CHG}_{\ell_k}$ for any $k\ge2$ in disjoint unions of paths and cycles. For $k\ge3$ odd, we prove that Alice (1st player) wins $\mathrm{CHG}_{\ell_k}$ in the path $P_n$ if and only if $n$ is odd and she wins in the cycle $C_n$ if and only if $n=3$ or $n=α\cdot (k+1)-1$ with $α\ge2$. For $k\ge2$ even, the only periodic nimber sequences of $\mathrm{CHG}_{\ell_k}$ obtained through extensive computational testing occurred for $k=2^h-4$ with $h\ge3$, e.g, $k\in\{4,12,28,60,\ldots\}$. In this case ($k=2^h-4$ with $h\ge3$), we prove that the nimber sequences of $\mathrm{CHG}_{\ell_k}$ in $P_n$ and in $C_n$ are periodic and Alice loses (resp. wins) in $P_n$ (resp. $C_n$) with $n>k$ only when $n=3k+4$ (resp. $n\in\{2k+1,5k+3\}$). Finally, we show that, for $k=2$, the game $\mathrm{CHG}_{\ell_2}$ in paths $P_n$ is closely related to the classical game \emph{Couples-are-Forever} of J. H. Conway: it is still an open problem if the nimber sequence is periodic or not and Alice loses only for 12 values of $n$ up to $150$ million.

0.12

PSPACE-completeness of the Hunters and Rabbit game

cs.CC cs.DM ·2026-10-13 ·Walid Ben-Ameur, Alessandro Maddaloni
theory similarity 0.52
Abstract

In the Hunters and Rabbit game, hunters shoot at a set of vertices at each round, while an invisible rabbit must move along an edge. We prove that deciding whether a given number of hunters can guarantee capture is PSPACE-complete, even on simple bipartite graphs. The reduction uses intersection nonemptiness for inverse finite automata: one common word must put all automata in accepting states simultaneously. A clique acting as a safe haven and two families of guards force every winning strategy to simulate common transitions. Existing transformations remove the restriction on the rabbit's initial positions and yield PSPACE-completeness for the directed game with one hunter, even on oriented graphs with positive minimum outdegree. Adjusting the guard sizes also proves PSPACE-completeness of the firefighting game, in which the rabbit may remain at its current vertex.

0.18

A Linear-Time Algorithm for the Unbiased Claw Game on Graphs with Maximum Degree 4

cs.DM ·2026-10-15 ·Julian Christoph Brinkmann
theory similarity 0.52
Abstract

We study the unbiased Maker-Breaker $K_{1,3}$-game, the unbiased claw game, played on the edge set of a general graph $G$. In this game, Maker and Breaker alternatingly claim edges of $G$, and Maker wins if his claimed edges contain a claw once no more edges are available. Graphs with maximum degree at least 5 are Maker's win. A graph $G$ is claw-connected if the hypergraph modeling the unbiased claw game played on $G$ is connected. We characterize Maker's win in the unbiased claw game on every claw-connected graph whose maximum degree is different from 3. Our main structural result is a complete characterization of Maker's win for claw-connected graphs with exactly one vertex of degree 4. The analysis is based on the fact that vertices of degree 4 act as forcing structures. Our characterization results in a linear-time algorithm for the unbiased claw game on claw-connected graphs with maximum degree different from 3. We also obtain a linear-time decomposition algorithm reducing the game on general graphs to a collection of pairwise edge-disjoint claw-connected subgraphs of maximum degree exactly 3, thereby isolating the only remaining case. This decomposition yields an $\mathcal{O}(|V(G)|^3)$-time algorithm for the unbiased claw game on general graphs, improving on the $\mathcal{O}(|V(G)|^7)$-time algorithm implied by the work of Galliot, Gravier and Sivignon (arXiv 2026). For a lower bound on the decision complexity, we prove that any agent deciding the game in the adjacency-array model makes at least $Ω(|V(G)|)$ queries in the worst case, indicating the optimality of our linear-time algorithm.

0.13