Cardinal Grid Slime Trail is PSPACE-Complete
2026-08-05 • Computational Complexity
Computational ComplexityDiscrete Mathematics
AI summaryⓘ
The authors studied a game called Slime Trail where two players move a token on a grid trying to reach a goal while deleting the places they move from. Previous work showed that deciding the winner is a hard problem (PSPACE-complete) on any flat map, but it was unknown if this was true on a simple square grid like in actual gameplay. The authors proved that it is still hard on a square grid where the token moves up, down, left, or right. They also showed their method works when allowing moves in eight directions by rotating the grid.
Slime TrailPSPACE-completecombinatorial gamegrid graphQBF reductionplanar graphfour-directional movementeight-directional movementcomputational complexitygame theory
Authors
Anne Pham, Matthew Ferland
Abstract
Slime Trail is a two-player combinatorial game in which the players alternately move a shared token to an adjacent vertex, permanently removing each vertex the token leaves, while attempting to reach a goal node. Ferland and Burke (2017) proved that Slime Trail is PSPACE-complete on arbitrary planar graphs and asked whether the same holds for the grid version actually used in play. We resolve this open problem by proving that Cardinal Grid Slime Trail, that is, Slime Trail on a square grid with four-directional movement, is PSPACE-complete. We adapt their QBF reduction to the grid setting, designing grid-compatible gadgets that respect the degree-4 bound and the parity constraints of the integer lattice. We further show the construction extends, under a 45-degree rotation, to the eight-directional variant.