Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Saving the Queen is hard: Hive is EXPTIME-complete
Francesco Carboni, Daniele Muscillo
Hive is a boardless two-player strategy game in which the pieces form the playing surface. We prove that deciding whether White can force a win in single-Queen -Hive, the genera…
cs.CC2026
One Hex reduction to rule them all: Quoridor, Maze Attack, Pinko Pallino and Blockade are PSPACE-complete
Francesco Carboni, Daniele Muscillo
Quoridor is a popular award-winning board game whose computational complexity, listed among the open problems of the Demaine-Hearn survey, remained open for nearly two decades. It…
cs.CC2025
Man, these New York Times games are hard! A computational perspective
Alessandro Giovanni Alberti, Flavio Chierichetti, Mirko Giacchini +3
The New York Times (NYT) games have found widespread popularity in recent years and reportedly account for an increasing fraction of the newspaper's readership. In this paper, we b…