Live Roundups Editor's Desk Insights Executive Ops Weather About 🔍
Home › Science › Quoridor is PSPACE-Complete
Science

Quoridor is PSPACE-Complete

arXiv CS Monday 01 June 2026, 04:00 UTC By Marius Drop, Benjamin G. Rin, Finn van der Velde 1 min read
Key Points

Announce Type: replace Abstract: 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.

arXiv:2605.22747v2 Announce Type: replace Abstract: 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.
Quoridor (ORG) Mirko Marchesi (PERSON) Cul-de-sac (PERSON) Pinko Pallino (ORG) Boolean (ORG) T. Schaefer (PERSON)
Originally published by arXiv CS Read original →

Related Stories

Link between poverty and access to nature | Letter

Prof Kathy Willis responds to research showing that the poorest areas in the country face the deepest cuts to green spacesThe new research covered in your report (England’s poorest areas face deepest cuts to green space under planning law changes, report finds, 4 June) highlights the stark inequalities that exist across England when it comes to accessing nature-rich places and unlocking the many health, wellbeing and economic benefits that they can provide. In short, the research has found...

The Guardian UK 30m ago

The Last Evolution, by John W Campbell Jr. (1932)

The Project Gutenberg EBook of The Last Evolution, by John Wood Campbell This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. You may copy it, give it away or re-use it under the terms of the Project Gutenberg License included with this eBook or online at www.gutenberg.org

Hacker News 34m ago

Genetically modified worms can now produce and deliver drugs inside a living body, scientists say

Genetically modified worms can now produce and deliver drugs inside a living body, scientists say In a proof-of-concept lab experiment, scientists demonstrated that intestinal parasites could make and release therapeutic agents inside a living host. Scientists genetically tweaked a tiny, worm-like parasite to produce a life-saving antitoxin from inside a living host. In a first-of-its-kind study, researchers modified the hookworm Ancylostoma ceylanicum so that it produces antibodies that...

Live Science 1h ago

Indonesia Landslides Devastated Endangered Orangutans, Study Finds

More than 5 percent of the species is estimated to have been lost when a climate-fueled storm unleashed torrents of water, mud and debris.

NYT Science 1h ago