pith. sign in

arxiv: 2605.22747 · v2 · pith:4YVJ7BYDnew · submitted 2026-05-21 · 💻 cs.CC

Quoridor is PSPACE-Complete

Marius Drop , Benjamin G. Rin , Finn van der Velde This is my paper

Pith reviewed 2026-05-22 02:56 UTC · model grok-4.3

classification 💻 cs.CC
keywords QuoridorPSPACE-completenesswinning strategyreductioncombinatorial gameboard game complexityGpos(POS CNF)
0
0 comments X

The pith

It is PSPACE-complete to decide whether a given player has a winning strategy in a Quoridor position on an n by n board.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that Quoridor belongs to the set of games where determining the winner from an arbitrary position is computationally intractable in the worst case. It establishes this by constructing a polynomial-time reduction from the PSPACE-complete game Gpos(POS CNF), in which players set variables to satisfy a positive CNF formula. A reader cares because the result implies that no efficient algorithm exists for solving Quoridor positions perfectly when the board grows, mirroring the hardness of generalized chess and similar games. The proof works for arbitrary square board sizes rather than a fixed size.

Core claim

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 × n. We prove this by reduction from Gpos(POS CNF), a Boolean formula game originally defined in 1978 by T. Schaefer.

What carries the argument

A polynomial-time reduction from Gpos(POS CNF) positions to Quoridor positions that preserves which player has a winning strategy.

If this is right

  • There is no polynomial-time algorithm for deciding Quoridor winners on n by n boards unless P equals PSPACE.
  • Quoridor joins the list of PSPACE-complete games that include generalized chess and other n by n board games.
  • Solving the game exactly remains hard even when the board is restricted to square grids of arbitrary size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Exact solvers or AI agents for Quoridor will need to rely on heuristics or search methods that scale exponentially in the worst case for large boards.
  • The result suggests similar hardness proofs may apply to other wall-placement games that share Quoridor's movement and blocking mechanics.
  • Restricted versions of Quoridor, such as those with fixed small n, might still admit practical algorithms even if the general case is hard.

Load-bearing premise

The mapping from Gpos(POS CNF) instances to Quoridor boards must be computable in polynomial time and must send winning strategies in one game to winning strategies in the other.

What would settle it

A concrete Quoridor position obtained from the reduction in which the player who wins the original formula game loses when both play optimally would show the reduction fails.

Figures

Figures reproduced from arXiv: 2605.22747 by Benjamin G. Rin, Finn van der Velde, Marius Drop.

Figure 1
Figure 1. Figure 1: Jumping to the open square behind an oppo￾nent’s pawn [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 4
Figure 4. Figure 4: White’s options when moving at a railroaded T￾junction from the stem. Turning 90◦ is possible. x [PITH_FULL_IMAGE:figures/full_fig_p004_4.png] view at source ↗
Figure 7
Figure 7. Figure 7: An unblockable T-junction. White can travel freely from any entrance to any other, regardless of the Black pawn’s location. 3 Proof We first sketch the proof and then provide the details. 3.1 Proof outline We will reduce Gpos(POS CNF) to Quoridor as follows. Given positive CNF formula A with c ∈ N clauses and v ∈ N variables , we construct a game position as depicted in [PITH_FULL_IMAGE:figures/full_fig_p… view at source ↗
Figure 8
Figure 8. Figure 8: The reduction position at a high level (some details omitted). Image is not drawn to scale. The outer edge represents the edge of the Quoridor board. Labeled items are as follows. 1. White starting location. 2. Black starting location. 3. Clause entrance chamber. 4. Chamber access corridor. 5. Winding road to increase corridor to a specified length L. 6. Side path for White to force entry into variable gad… view at source ↗
Figure 9
Figure 9. Figure 9: No new wall in the 2 × 2 area with the pawn. The pawn has three squares to move to [PITH_FULL_IMAGE:figures/full_fig_p007_9.png] view at source ↗
Figure 12
Figure 12. Figure 12: Example of an elongator. Size and shape can vary as needed. 3.2.1 Position construction and terminology The maze is the area within the large rectangle with corners labeled 7a and 7b in [PITH_FULL_IMAGE:figures/full_fig_p008_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: (a) The structure labeled 13 in the initial position. (b) The structure labeled 13 with walls placed so that the second and last black victory corridor are closed off. A black pawn is placed to show moving options. The emergency exit, labeled 11, is an additional corridor out of the maze. This ensures that White always has an open path to victory once White is in the maze, as required under the rules. How… view at source ↗
Figure 14
Figure 14. Figure 14: Simplified image of a clause entrance chamber. The actual gadget has unblockable T-junctions in place of the junctions marked (*), with the rest of the gadget appropriately scaled up in size to make space. Black can close the chamber by placing vertical walls in the open spaces (indicated by small white gaps) to block off the horizontal corridors. The dotted lines denote a continuation of the pattern depi… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that determining whether the first or second player has a winning strategy in a given Quoridor position on an n×n board is PSPACE-complete. The proof is by polynomial-time reduction from Gpos(POS CNF), the positional game on positive CNF formulas shown PSPACE-complete by Schaefer in 1978; the construction encodes formula variables and clauses via pawn paths and wall placements so that winning strategies correspond exactly.

Significance. If the reduction is correct, the result adds a popular modern board game to the list of PSPACE-complete generalized games (alongside chess, Go, etc.). The direct reduction from an independently established 1978 problem is a strength, as it introduces no free parameters, invented entities, or circular steps.

major comments (2)
  1. [Reduction section] Reduction section: the manuscript must explicitly verify that every wall placement encoding a literal choice in Gpos(POS CNF) blocks exactly the paths corresponding to unsatisfied clauses and does not create spurious pawn routes that would allow a player to win in Quoridor without satisfying the formula (or vice versa). Without this bidirectional strategy-preservation argument, the equivalence of winning strategies is not established.
  2. [Reduction section] Reduction section: the construction must be shown to be polynomial-time; the manuscript should state the size of the resulting n×n board and number of walls as a function of the input formula size, confirming that n remains polynomial.
minor comments (2)
  1. [Abstract] The abstract states the high-level approach but supplies no outline of how walls encode literals or how pawn movement simulates clause checking; a short paragraph sketching the key gadgets would improve readability.
  2. [Notation and rules] Notation for board positions and moves should be introduced once and used consistently; currently some wall-placement rules are described informally.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful review and positive evaluation of the significance of our result. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation of the reduction.

read point-by-point responses

  1. Referee: [Reduction section] Reduction section: the manuscript must explicitly verify that every wall placement encoding a literal choice in Gpos(POS CNF) blocks exactly the paths corresponding to unsatisfied clauses and does not create spurious pawn routes that would allow a player to win in Quoridor without satisfying the formula (or vice versa). Without this bidirectional strategy-preservation argument, the equivalence of winning strategies is not established.

    Authors: We agree that an explicit bidirectional strategy-preservation argument is necessary to rigorously establish the equivalence. In the revised manuscript we will add a dedicated paragraph (or short subsection) in the Reduction section that performs a case analysis: for each possible literal choice encoded by a wall placement, we show (i) that a satisfying assignment for the formula corresponds to a winning Quoridor strategy for the appropriate player, and (ii) conversely, that any winning Quoridor strategy induces a satisfying assignment, with no spurious pawn paths or blocking configurations that would break the correspondence. This will be done by examining the possible pawn routes around the clause gadgets and confirming that wall placements affect exactly the intended paths. revision: yes

  2. Referee: [Reduction section] Reduction section: the construction must be shown to be polynomial-time; the manuscript should state the size of the resulting n×n board and number of walls as a function of the input formula size, confirming that n remains polynomial.

    Authors: We will make the polynomial bound explicit. In the revised version we will state that, given a POS-CNF formula with v variables and c clauses, the constructed Quoridor instance uses an n×n board where n = O(v + c) and a polynomial number of walls (at most O(v + c) walls are placed in the initial position). Because both the board size and the wall count are linear in the size of the input formula, the reduction is clearly polynomial-time computable. We will include this statement together with a brief justification of the linear dependence in the Reduction section. revision: yes

Circularity Check

0 steps flagged

Direct reduction from independent 1978 PSPACE-complete problem

full rationale

The paper proves PSPACE-completeness of Quoridor by exhibiting a polynomial-time reduction from Gpos(POS CNF), a problem whose PSPACE-completeness was established externally by Schaefer in 1978. No author overlap exists with the cited source. The derivation consists of a strategy-preserving mapping between game positions; this is a standard, externally verifiable construction that does not rely on self-definition, fitted parameters, or load-bearing self-citations. The central claim therefore remains independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definition of PSPACE-completeness and the correctness of a reduction from a previously proven hard problem; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (1)
  • standard math Gpos(POS CNF) is PSPACE-complete as originally shown by Schaefer in 1978
    The reduction begins from this established result.

pith-pipeline@v0.9.0 · 5645 in / 1083 out tokens · 29461 ms · 2026-05-22T02:56:52.665301+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.