Quoridor is PSPACE-Hard
For game theorists and complexity theorists, this resolves the complexity of Quoridor, showing it is as hard as other classic combinatorial games.
The paper proves that determining the winner of a Quoridor position on an n×n board is PSPACE-complete, establishing the game's computational complexity.
Quoridor is an award-winning abstract strategy game designed by Mirko Marchesi and published in 1997. Similar games include Maze Attack, Blockade (also known as Cul-de-sac), and Pinko Pallino. In line with chess, checkers, Go, and other classic combinatorial games, Quoridor is a turn-based, deterministic, perfect-information game played on a square grid. We show that it is PSPACE-complete to determine whether a given player has a winning strategy in a given Quoridor position on a board with size $n \times n$. We prove this by reduction from Gpos(POS CNF), a Boolean formula game originally defined in 1978 by T. Schaefer.