This repo contains the reproduction code for my work on solving small Quoridor variants.

It is not a polished Quoridor engine. It is a solver built around one idea: for small boards, you can enumerate every possible wall configuration up front, then turn the annoying "you may not block all paths to goal" rule into a table lookup.

Odd-height boards are not always 2nd player wins.

They are 2nd player wins with few walls, but often become 1st player wins once there are enough walls. For example, 5x5 is a 2nd player win at <=4 walls per player, but a 1st player win at >4 walls.

There are also weird geometries:

• 8x3 with 3 walls per player is a forced draw from the starting position.
• 7x3 never transitions into a 1st player win at any wall count tested.
• 3x5 is a 2nd player win at all tested wall counts except 3.
• 4x7 flips from 2nd player, to 1st player, back to 2nd player, then back to 1st player.

Even-height boards tested here are all 1st player wins.

Full results table. 1 means 1st player win, 2 means 2nd player win, D means draw, ? means not yet solved.

W x H  0 1 2 3 4 5 6 7 8 9 10

2 x 3  2 1 1 1 1 1 1 1 1 1 1
3 x 3  2 2 2 2 2 2 2 2 2 2 2
4 x 3  2 2 2 1 1 1 1 1 1 1 1
5 x 3  2 2 2 1 1 1 1 1 1 1 1
6 x 3  2 2 2 2 1 1 1 1 1 1 1
7 x 3  2 2 2 2 2 2 2 2 2 2 2
8 x 3  2 2 2 D 2 2 2 2 2 2 2
9 x 3  2 2 2 2 2 2 2 1 1 1 1

2 x 5  2 2 2 2 2 2 2 2 2 2 2
3 x 5  2 2 2 1 2 2 2 2 2 2 2
4 x 5  2 2 2 2 1 1 1 1 1 1 1
5 x 5  2 2 2 2 2 1 1 1 1 1 1

2 x 7  2 2 1 1 1 1 1 1 1 1 1
3 x 7  2 2 2 2 2 1 1 1 1 1 1
4 x 7  2 2 1 2 1 1 1 ? ? ? ?

2 x 9  2 2 2 2 2 2 2 2 2 2 2
3 x 9  2 2 2 2 2 1 1 1 1 ? ?

Quoridor is annoying to search because most moves are wall moves, and each wall move naively requires pathfinding to check legality.

This solver avoids that cost by precomputing all wall states for the board:

• enumerate all non-overlapping wall configurations up to the maximum number of placed walls;
• for each wall configuration, flood-fill from each goal row;
• store the set of squares that can still reach each player's goal;
• check wall legality by looking up the next wall configuration and testing whether both pawns are still inside their goal-reachability masks.

Search is then an iterative-deepening proof search. For a target player, it asks: can this player force a win within this depth?

If no finite win is proved by the cutoff, the solver falls back to exact retrograde analysis of the reachable game graph. That is needed for loopy cases like the 8x3, 3-wall draw.

Solve one board:

cargo run --release --bin solve_custom -- 5 5 5

The three arguments are width height walls-per-player.

Output is one parseable key=value line:

width=5 height=5 walls=5 winner=Player1 method=proof depth=25 fallback_depth=256 nodes=857072712

Run the frontier driver:

python3 pareto_frontier.py

This expands outward from solved cases, prioritizes the next cases by parent solve time so cheap frontiers get explored first, records each attempt in a TSV log, and resumes from that log if interrupted.

Run tests:

cargo test

The tests compare the optimized solver against a deliberately dumb reference implementation on small boards.

• src/lib.rs: the optimized solver.
• src/bin/solve_custom.rs: thin CLI wrapper around the library.
• tests/tests.rs: slow, obvious-reference Quoridor engine plus alpha-beta negamax tests.
• pareto_frontier.py: resumable script for exploring the board-size/wall-count frontier.
• Cargo.toml, Cargo.lock: Rust package metadata.

The full 9x9 game is still out of reach for this approach. The number of wall configurations grows too quickly.

This code is meant to reproduce the small-board results and make the core idea inspectable.