Browse all game versions and their sources · Interactive map

← Games Complexity Atlas

Variants and open questions

Additional exact variants and source-dated open questions. Published theorems are distinguished from explicitly explained algorithmic consequences. Not finding a theorem is not treated as proof that a question is open.

80 notes · 30 game families · Reviewed 2026-10-08 · Version 10.0.2

Results concern the specific task and growing input described below. An open question is dated to its cited source. A rule change is not a reduction.

Akari / Light Up

Only the clue 4

P

Force bulbs around each 4, reject conflicts, then greedily light dark cells.

Task
Decide whether the puzzle can be completed.
Scale & input
Growing grid. Walls are unnumbered or labeled 4.
Move rules
Ordinary Akari lighting and bulb-count rules.
Goal
Light every white cell without bulbs seeing each other.
Repetition
Static completion, no play-history restriction.
Players & information
One solver. All clues and constraints are known.
Randomness
None.
Connection
restriction: akari

Primary undergraduate thesis. Forced-bulb conflicts must be checked.

Result in cited thesis

§3.1.2, Algorithms 2–3.

Open this variant in the map →

Only 1s, only 2s, or only 3s

NP-complete

Each of these three fixed clue sets still encodes circuits.

Task
Decide whether the puzzle can be completed.
Scale & input
Growing grid. Choose one allowed number: 1, 2, or 3. Unnumbered walls also allowed.
Move rules
Ordinary Akari lighting and bulb-count rules.
Goal
Light every white cell and meet each clue.
Repetition
Static completion, no play-history restriction.
Players & information
One solver. All clues and constraints are known.
Randomness
None.
Connection
restriction: akari

Primary undergraduate thesis with mechanically checked gadgets.

Result in cited thesis

§3.1, NP membership; §§3.1.3–3.1.5, circuit constructions.

Open this variant in the map →

Backgammon

Known rolls, strategic opponent

PSPACE-hard

The opponent now chooses variable assignments in the reduction.

Task
Can you force a win against an opponent whose policy is not disclosed?
Scale & rules
Same scalable checker/point model and known roll schedule. Both players choose strategically.
Result scope
Theorem 2 is a hardness result. It does not prove PSPACE membership.
Connection
rule change: Replace the prescribed opponent by an adversarial player (Backgammon: Known rolls & opponent)

Published result

Definition 4, Theorem 2.

Open this variant in the map →

Adaptive rolls and strategic opponent

EXPTIME-hard

The proof uses roll choices that adapt to play to simulate a revisitable formula game.

Task
What is the hardness of the paper’s unknown-strategy, unknown-roll winner model?
Scale & rules
Same generalized board. Opponent and future rolls are unknown, with adaptively chosen rolls in the reduction.
Randomness
No expected-score or specified probability threshold is analyzed.
Connection
rule change: Allow an adversarial strategy and adaptive future rolls (Backgammon: Known rolls & opponent)

The theorem concerns adaptive rolls, not fair-dice win probabilities. It proves EXPTIME-hardness without a matching upper bound.

Published result

Definition 6, Theorem 3, especially p.10 on adaptive dice.

Open this variant in the map →

Matching upper bounds

Open in the 2021 source

The author explicitly leaves membership questions open.

Task
Which upper bounds match the three backgammon hardness models?
Scope
KSKR, USKR and USUR exactly as defined in the paper. Future-policy and roll encodings must be specified.
Caution
An unbounded game length alone does not rule out EXPTIME algorithms on finitely represented game graphs.
Connection
task change: Ask for membership, not only hardness (Backgammon: Known rolls & opponent)

This records the question in the cited 2021 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2021 source

Conclusion, p.12.

Open this variant in the map →

Battleships solitaire

Bloxorz

Remove switches and bridges

P

Only polynomially many block positions and orientations remain.

Task
Decide whether the rolling block can reach the goal.
Scale & input
Explicit finite board with a 1×1×2 block, start and goal.
Move rules
Roll and tilt, always fully supported. Static tiles only.
Goal
Reach goal upright.
Repetition
Revisits allowed.
Players & information
One player. Complete board known.
Randomness
None.
Connection
restriction: bloxorz-switches

Published result

§1.2 and Table 2.

Open this variant in the map →

Replace the long block with a cube

P

A unit cube can expand its reachable area systematically.

Task
Decide whether the cube can reach the goal using switches and bridges.
Scale & input
Same explicit switch/bridge board, with a 1×1×1 cube.
Move rules
Step to an adjacent supported square, toggling switches.
Goal
Reach goal.
Repetition
Revisits and repeated toggles allowed.
Players & information
One player. Full state known.
Randomness
None.
Connection
rule change: bloxorz-switches

Published result

Theorem 8.

Open this variant in the map →

Fragile one-use tiles instead of switches

NP-complete

A tile that disappears after use can enforce Boolean choices.

Task
Decide whether the 1×1×2 block can reach the goal.
Scale & input
Explicit board. Normal and single-use tiles, no switches or bridges.
Move rules
Roll/tilt long block. Fragile tiles disappear after traversal.
Goal
Reach goal upright.
Repetition
Fragile tiles cannot be reused.
Players & information
One player. Full board known.
Randomness
None.
Connection
rule change: bloxorz-switches

Single-use tiles are a theoretical variant, not a feature of the original Bloxorz.

Published result

§5, Theorem 7.

Open this variant in the map →

Checkers

Force your opponent to capture everything

NP-complete

Losing immediately is computationally hard even though the horizon is only two turns.

Task
Can you make a move forcing the opponent to capture all your remaining pieces next turn?
Model & rules
Arbitrary position on a growing n×n board. American checkers captures are compulsory and must continue while possible. Kings jump in both directions. Two players, full information, no randomness. Only the next two turns are relevant.
Connection
task change: Ask for an immediate forced loss (Checkers: Every turn must capture)

Published result

§2; Theorems 3.2–3.3

  • Losing at Checkers is HardJeffrey Bosboom; Spencer Congero; Erik D. Demaine; Martin L. Demaine; Jayson Lynch (2018).Published book chapter · The Mathematics of Various Entertaining Subjects, vol. 3 (2019), 103–118; cited 2018 manuscriptRead full text
Open this variant in the map →

Cooperate for just two turns

NP-complete

Replacing forced capture with a cooperative choice remains NP-complete.

Task
Can your move let the opponent capture all your pieces on their next turn?
Model & rules
Arbitrary position on a growing n×n board. American checkers captures are compulsory and must continue while possible. Kings jump in both directions. Two players, full information, no randomness. Only the next two turns are relevant.
Connection
task change: The opponent helps instead of resisting (Force your opponent to capture everything)

Published result

§5, first paragraph

  • Losing at Checkers is HardJeffrey Bosboom; Spencer Congero; Erik D. Demaine; Martin L. Demaine; Jayson Lynch (2018).Published book chapter · The Mathematics of Various Entertaining Subjects, vol. 3 (2019), 103–118; cited 2018 manuscriptRead full text
Open this variant in the map →

Chess

Cooperate to reach checkmate

PSPACE-complete

Even cooperative chess can require solving a PSPACE-complete reachability problem.

Task
Can any legal sequence checkmate Black?
Scale & input
Explicit growing n×n position, arbitrary number of pieces, exactly one king per color.
Move rules
Standard piece moves and alternating turns, with kings never left in check.
Players & information
Two cooperating players, full information.
Randomness
None.
Repetition
Unbounded reachability problem. No polynomial move limit or automatic tournament draw counter is part of the paper’s state definition.
Connection
task change: Replace forced mate with possible mate (Chess: Force checkmate)

This is the paper’s unbounded-sequence model. Its state does not include tournament move-count or repetition counters. Automatic-draw variants require a separate classification.

Published result

§1.1, Lemma 1.1; Theorem 2.1

Open this variant in the map →

Could this position have arisen?

PSPACE-complete

Testing reachability itself is hard, before asking which earlier move was forced.

Task
Is the input position reachable from a natural generalized starting setup?
Scale & input
Explicit growing n×n position, arbitrary number of pieces, exactly one king per color.
Move rules
Standard piece moves and alternating turns, with kings never left in check.
Players & information
Two cooperating players, full information.
Randomness
None.
Repetition
Unbounded reachability problem. No polynomial move limit or automatic tournament draw counter is part of the paper’s state definition.
Start condition
First two and last two ranks filled, pawns on the inner ranks, one king and sufficiently many other non-pawn types on each outer rank, middle empty.
Connection
task change: Replace checkmate with a specified position (Cooperate to reach checkmate)

The starting family is defined in the paper, not a unique standard 8×8 opening. The unbounded sequence model does not impose tournament draw counters.

Published result

§1.1 Problem 1, Lemma 1.1; §3

Open this variant in the map →

Chomp

Find the first winning bite

Open in the 2020 source

This search question is explicitly open even though deciding who wins is immediate.

Task
Can a winning first move be found in polynomial time in unary dimensions?
Input & rules
A full m×n rectangle with m,n written in unary, at least two cells. Same poison and bite rules.
Scope
The authors place the search in polynomial space and explain why the sparse input is an obstacle to usual hardness proofs.
Connection
task change: Find a move rather than name the winner (Chomp: Winner on a full rectangle?)

This records the question in the cited 2020 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2020 source

§3, “Hardness for Specific Games”, p.21:11.

Open this variant in the map →

Start from a partially eaten bar

Open in the 2013 source

Hardness of unrestricted poset games does not settle their two-dimensional Chomp restriction.

Task
What is the winner-decision complexity for arbitrary Chomp positions?
Input & rules
Explicit remaining cells of a downward-closed chocolate shape with the poison retained, not a succinct exponentially large bar. Same bite rule.
Upper bound
In PSPACE by finite board storage and at most one move per cell.
Connection
rule change: Allow a partially eaten starting position (Chomp: Winner on a full rectangle?)

This records the question in the cited 2013 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2013 source

Introduction, p.2.

Open this variant in the map →

Domineering / Cram

Winner complexity on general grid boards

Open in the 2024 source

The authors explicitly identify general-board winner complexity as open.

Task
Is deciding the Domineering winner efficiently solvable, or can hardness be proved?
Rules
Explicit remaining grid cells. Vertical versus horizontal placement, normal play.
Known upper bound
In PSPACE by at most N/2 moves.
Connection
task change: Close the upper/lower-bound gap (Domineering: Winner from a position?)

This records the question in the cited 2024 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2024 source

§1.2, “Cram and Domineering”.

Open this variant in the map →

Cram: either player may use either orientation

Open in the 2024 source

The general-board problem is explicitly open. The simple parity strategies for some empty rectangles do not settle it.

Task
What is the complexity of deciding the Cram winner on a general grid board?
Rules
Explicit remaining grid cells. Both players may place a horizontal or vertical domino. No overlap, last move wins.
Bound
At most N/2 moves, hence polynomial-space search.
Connection
rule change: Allow both orientations for both players (Domineering: Winner from a position?)

This records the question in the cited 2024 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2024 source

Introduction and §1.2.

Open this variant in the map →

Cram on an arbitrary graph: Arc Kayles

PSPACE-complete

A September 2026 proof settles the unrestricted graph game.

Task
Who wins when domino placements are graph edges?
Scale & rules
Explicit finite undirected graph. A move selects an edge and removes its two endpoints. The last move wins.
Players & information
Two players, perfect information, no randomness, at most |V|/2 moves.
Connection
rule change: Remove orientation ownership and replace the grid by a graph (Domineering: Winner from a position?)

This does not prove PSPACE-hardness of grid Cram.

Result in cited preprint

Bonnet, Theorem 1 and §3; Hanaka et al. identify Cram as the grid-graph restriction.

Open this variant in the map →

Dots & Boxes

Nimstring: change how the winner is chosen

PSPACE-complete

The proof permits parallel strings and nonplanar graphs. This is broader than an ordinary square board.

Task
Who wins when the first player unable to cut a string loses?
Model & rules
Explicit multigraph with grounded strings allowed. Two players cut one string. Freeing a coin forces another cut. Full information, no randomness. Strings disappear permanently.
Connection
rule change: Use normal play on arbitrary multigraphs (Dots & Boxes: More boxes than your opponent?)

Published result

Definition 2.2; Corollary 4.2.1

Open this variant in the map →

Normal play on the square-grid board

Open in the 2021 source

The multigraph hardness construction does not settle this restriction.

Task
Determine the winner under Nimstring scoring-free rules on grid instances.
Model & rules
Growing ordinary Dots & Boxes grid viewed as its strings-and-coins dual. Keep extra turns for completed boxes, but the first player unable to move loses. Two players, full information, no chance, no reused edge.
Connection
restriction: Require ordinary grid instances (Nimstring: change how the winner is chosen)

Open in the cited 2021 source. Later status is not established by this record.

Open in the 2021 source

§5, Open Problems

Open this variant in the map →

Geography

Compute the nimber, not just the winner

P search at degree 3; PSPACE-hard and polynomial-space computable at degree 4

Degree three permits efficient nimber computation. Degree four already gives PSPACE-hardness, while recursive computation still needs only polynomial space.

Task
Compute an undirected Geography position's Grundy value.
Model & rules
Explicit graph and token. Alternate to unvisited neighbors. The player with no legal move loses. Perfect information, no randomness.
Why this bound holds

At each recursion level store the remaining graph, token and a polynomial-size seen-nimber bitset. The nimber is at most the number of available moves, hence at most |V|. There are at most |V| levels because a vertex is removed each turn. This computes a function in polynomial space; it does not classify a decision language as PSPACE-complete.

Atlas-derived consequence
The derivation is stated in this record, rather than quoted as a theorem from the cited work.

Burke, Ferland and Teng, Theorem 1.1. Polynomial-space computation follows from depth-first mex evaluation: at most |V| moves and at most |V| options per position.

Open this variant in the map →

Play two boards together

PSPACE-complete

Each board alone is easy. Their combined game is hard.

Task
Determine the winner of two undirected Geography positions combined.
Model & rules
Two explicit graphs and tokens. Each turn moves on exactly one board to an unvisited neighbor. A player unable to move on either board loses. Perfect information, no randomness.

Published result

Theorem 4.3.

Open this variant in the map →

One shared pass changes the winner problem

PSPACE-complete

Adding one shared pass makes winner determination PSPACE-complete.

Task
Determine the winner with one pass available to either player.
Model & rules
Explicit undirected graph and token. Move to an unvisited neighbor or consume the shared pass. Passing is allowed even when stuck. A player with no remaining action loses. Perfect information, no randomness.

Published result

Section 4, Theorem 4.3.

Open this variant in the map →

Two shared passes restore polynomial time

P

Pass parity matters: one pass is PSPACE-complete, two passes give the original polynomial-time winner test.

Task
Determine the winner with exactly two shared passes available.
Model & rules
Explicit undirected graph and token. Move to an unvisited neighbor or consume one of two shared passes, including when stuck. Two players, full information, no randomness. Every action removes a vertex or pass. The player with no legal action loses.
Connection
rule change: Increase the shared pass allowance from 1 to 2 (One shared pass changes the winner problem)

Published result

Theorem 4.3, even total pass count.

Open this variant in the map →

Hanabi

One color only

P

A near-linear algorithm chooses which copies to save.

Task
Can the known deck be completed with one color?
Scale & rules
Same solitaire model, one color, arbitrary finite hand capacity and duplicates.
Connection
restriction: Restrict the deck to one color (Hanabi: Known-deck solitaire)

Published result

§3, Theorem 4.

Open this variant in the map →

No duplicate cards

P

A greedy linear-time test suffices.

Task
Can the deck be completed if each card appears once?
Scale & rules
Same full-information solitaire model. Multiplicity is exactly one or less, colors and values may scale.
Connection
restriction: Remove duplicate copies (Hanabi: Known-deck solitaire)

Published result

§2, Lemma 1.

Open this variant in the map →

Hex

Find the winning first move

Open in the 2020 source

Knowing that the first player wins does not identify the move. The paper leaves polynomial-time search open for Hex itself.

Task
Given the empty board's dimensions in unary, output a winning first move.
Model & rules
Empty growing square Hex board, normal alternating placement and connection goals, no swap rule. Two players, perfect information, no randomness. Cells are never reused.

Its PSPACE-hardness theorem covers broader game classes, not this empty-Hex search problem. Open status is dated to the cited paper.

Open in the 2020 source

Section 3, Hardness for Specific Games.

Open this variant in the map →

Require a win within k turns

FPT in k

For ordinary planar Hex, the dependence on board size can be polynomial with the expensive part confined to k.

Task
Can the player force a connection within k total plies?
Model & rules
Growing explicit Hex board and input bound k on total alternating moves. Existing stones allowed, usual connection goals. Full information, no randomness. Each turn fills one cell.
Connection
task change: Bound the winning horizon (Hex: From a given position)

FPT is not a claim of polynomial time when k varies freely. The proof’s dependence on k is not practical.

Published result

§5, Theorem 5, Corollaries 2–3

Open this variant in the map →

Can optimal play have a small circuit?

Open in the 2020 source

The authors ask whether small strategies must exist even when finding them is hard.

Task
Does empty-board Hex necessarily admit a polynomial-size optimal-strategy circuit?
Scope
A scalable empty symmetric Hex board. A circuit takes a reached position and outputs the strategy’s next move.
Distinction
This is strategy representation size, not the problem of finding one opening move.
Connection
task change: Ask for a compact whole-game strategy (Hex: From an empty board)

This records the question in the cited 2020 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2020 source

§3, “Other Notions of Constructiveness”, p.21:11.

Open this variant in the map →

Jigsaw & packing

Every mate is locally identifiable

P (algorithmic consequence)

Testing piece pairs gives a polynomial-time assembly method under this strong promise.

Task
Can the puzzle be assembled when local fit identifies true neighbors?
Scale & rules
Explicit finite pieces. Every locally compatible pair is guaranteed to be adjacent in the final solution.
Scope
This is stronger than merely promising one global solution.
Connection
restriction: Promise that local compatibility identifies the true neighbor (Jigsaw: Fit every piece?)

Atlas-derived consequence
The derivation is stated in this record, rather than quoted as a theorem from the cited work.

Introduction, p.4, paragraph beginning “The shape-matching community”.

Open this variant in the map →

Lemmings

One lemming, unlimited skills, no traps or water

Open in the 2015 source

The paper asks whether removing deadly zones makes unlimited-skill rescue easier. Its PSPACE-hard construction uses such zones, and does not settle this restriction.

Task
Decide whether the single lemming can reach an exit.
Scale & input
Explicit scalable pixel landscape, one lemming, unlimited time and all skill types available without a usage bound.
Move rules
Original modeled skills and terrain rules. Remove deadly-zone objects, including traps and water. Long falls can still kill.
Goal
Save the one lemming.
Repetition
Revisits and terrain changes allowed.
Players & information
One solver, complete information.
Randomness
None.

Open in the cited 2015 source; later status is not established by this record. NP-hardness with limited skills does not classify levels where all skills are unlimited.

Open in the 2015 source

§6, especially Table 3's one-lemming, no-hazards, unlimited-skills column

Open this variant in the map →

Lights Out

Toggle neighbors but not the pressed light

P

The matrix changes from A+I to A. Gaussian elimination still decides reachability.

Task
Decide whether the target pattern is reachable.
Scale & input
Explicit arbitrary simple undirected graph and initial/target patterns.
Move rules
Press toggles neighbors only.
Goal
Reach target.
Repetition
Repeated presses allowed, parity suffices.
Players & information
One player. Complete input known.
Randomness
None.
Connection
rule change: lights-reach

Published result

§4.3.

Open this variant in the map →

Neighbors only, with a press budget

NP-complete

A short-solution requirement changes the neighbors-only graph problem from P to NP-complete.

Task
Can the target be reached with at most w pressed vertices?
Scale & input
Explicit arbitrary simple undirected graph, initial/target bit patterns and integer w.
Move rules
Press toggles neighbors only.
Goal
Reach target with at most w presses.
Repetition
Repeated presses may be canceled in pairs.
Players & information
One player. Complete input known.
Randomness
None.
Connection
task change: lights-neighbors-only (Toggle neighbors but not the pressed light)

The hardness is for arbitrary graphs, not specifically ordinary rectangular self-toggling boards.

Published result

§5, Lemmas 19–20 and Theorem 21.

Open this variant in the map →

Magic: The Gathering

Allow strategic choices before the forced endgame

Non-arithmetic lower bound

The 2020 preprint proves a stronger lower bound for strategic play.

Task
Does a player have a winning strategy?
Scale & rules
The paper’s Magic rules and unbounded tokens/counters. Binary numeric choices, full information, no randomness.
Task
Its mate-in-n target means reaching a forced winning endgame within n strategic moves, not resolving the full game within n turns.
Connection
rule change: Allow players to choose numbers before the simulation starts (Magic: The Gathering: Forced endgame outcome)

Result in cited preprint

Theorems 2–3, §§2–3.

Open this variant in the map →

Can every legal move be executed algorithmically?

Open in the 2021 source

The authors conjecture that the transition function is computable.

Task
Given a state and a legal move, is the next state computable?
Scope
All cards under the paper’s rules. Numerical choices must use binary notation. The input move is promised legal.
Connection
task change: Ask about one transition instead of the eventual outcome (Magic: The Gathering: Forced endgame outcome)

This records the question in the cited 2021 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2021 source

§2, Conjecture 1.

Open this variant in the map →

Is an arbitrary proposed move legal?

Open in the 2021 source

The authors conjecture that general move legality is undecidable.

Task
Is legality decidable for every proposed Magic move?
Scope
The paper’s rules/card pool and binary number convention. This is broader than the separately studied blocking step.
Connection
task change: Check legality instead of the eventual winner (Magic: The Gathering: Forced endgame outcome)

This records the question in the cited 2021 source, not a lower bound or a claim that every variant of this game is unresolved.

Open in the 2021 source

§2, Conjecture 2.

Open this variant in the map →

How far beyond halting-hard?

Open in the 2020 source

The lower bound is proved. The matching upper bound is Conjecture 3.

Task
Is winning-strategy existence Turing-equivalent to arithmetic truth?
Scope
Biderman’s strategic Magic model, full information and binary numeric choices, with the card pool/rules frozen as in the paper.
Connection
task change: Classify strategic play more precisely (Magic: The Gathering: Forced endgame outcome)

New card text could alter the conjecture. This is a dated research question, not an established upper bound.

Open in the 2020 source

§5, Conjecture 3.

Open this variant in the map →

Mancala

Awari: a fixed board is a draw

Fixed board solved

The cited ruleset was strongly solved: perfect play draws. This does not classify growing-board Awari or other Oware rules.

Task
Determine optimal play on the fixed Awari board.
Scale & rules
Two rows of six pits, four stones each. Sow from an own pit counterclockwise, skipping the starting pit on a lap. A last stone making an enemy pit hold two or three captures it and consecutive preceding enemy pits with two or three.
Ending & repetition
Choose a move leaving the opponent a stone whenever possible. Otherwise a grand slam captures every opposing stone, and the mover also collects all remaining stones because the opponent cannot move. Repetition ends play and divides uncollected stones equally, allowing half-stones. The companion rules note specifies threefold repetition.
Players & goal
Two players, known counts, no randomness. Capture more than 24 of the 48 stones to win.
Connection
rule change: Change capture, feeding and repetition rules (Kalah: Fixed 6×4 opening)

Traditional Oware capture and ending conventions differ.

Published result

Romein–Bal §1 and Appendix; Donkers companion note, rules 4–8. The solution does not use the rule that cancels grand-slam captures.

  • Awari Is SolvedJohn W. Romein, Henri E. Bal (2002).Published journal article · ICGA Journal 25(3) (2002)Open manuscript not recorded. The stored link is the journal issue contents; a direct open manuscript is not recorded.
  • Comments on the Awari SolutionJeroen Donkers (2002).Published journal article · ICGA Journal 25(3) (2002)Open manuscript not recorded. The stored link is the journal issue contents; a direct open manuscript is not recorded.
Open this variant in the map →

Tchoukaillon: solitaire sweep solvability

P (algorithmic consequence)

A winning play must always use the nearest harvestable bin. This gives a polynomial-time solvability test.

Task
Given a bin vector, can every stone reach the store?
Scale & rules
Input is an explicit vector of k nonnegative binary counts. Bin i is i steps from the store. Only a bin containing exactly i stones can be sown, depositing one in each earlier bin and finally the store.
Players & goal
One player, full information, no randomness. Empty all bins.
Repetition
Each move permanently stores one stone, so no repeated state.
Connection
rule change: Replace adversarial play with an all-sowings-end-in-store solitaire task (Kalah: Fixed 6×4 opening)

P follows from the cited characterization: reject any count above its bin index, then simulate at most k(k+1)/2 forced moves. This is not a winner result for two-player Kalah.

Atlas-derived consequence
The derivation is stated in this record, rather than quoted as a theorem from the cited work.

§1.1 and Theorem 2.1.

Open this variant in the map →

Dakon: win before the opponent moves

Fixed openings solved

The paper finds winning openings for Dakon-n at n=2 and 4 through 18, but none at n=3. These finite searches do not establish a complexity class.

Task
Can the initial player capture enough stones during the first turn to prevent another round?
Scale & rules
Dakon-n has n pits per side, initially n stones per pit, and stores. Sow counterclockwise through your store, skipping the opponent's. If the last stone lands in a nonempty pit, pick that pit up and keep sowing. Ending in your store grants another choice. Ending in an empty own pit captures it and the opposite pit.
Ending & information
Two players, known counts, deterministic. Rounds refill pits with n stones each and skip unfillable pits. A player unable to fill one pit loses. This record concerns only the terminating first-turn construction, not general repetition behavior.
Connection
rule change: Add relay sowing and round-based refill rules (Kalah: Fixed 6×4 opening)

Result in cited source

Rules pp. 79–80; winning openings pp. 81, 83–84.

Open this variant in the map →

Captureless Kalah: still in PSPACE for unary counts

In PSPACE (upper bound)

Removing capture does not break the polynomial play-length bound. Ordinary sowing still permanently adds stones to stores, and all other sowings move stones closer to their own store.

Task
Can the designated player force a larger final store count after removing the opposite-pit capture rule?
Scale & input
Explicitly list m pits per side, two stores, whose turn it is and unary stone counts. Arbitrary initial positions are allowed.
Rule change
Use the Kalah rules in the linked unary winner record but disable the last-stone/opposite-pit capture. Keep sowing into your own store, skipping the opponent's store, bonus choices for a last stone in your store, and final collection when one side empties.
Players & goal
Two players, fully visible counts, no randomness. Finish with strictly more stored stones than the opponent. A tie is not a win.
Repetition
No repetition rule is needed: the same rank R=(S−C)(mS+1)+Φ strictly decreases.
Connection
rule change: Disable the opposite-pit capture (Kalah: Scalable board, unary counts)

The polynomial-space result establishes membership only, not PSPACE-hardness or completeness.

Why this bound holds

The unary Kalah proof never relies on a capture taking place. Moves that deposit stones in stores decrease S−C. Every other move stays within the mover's own row and decreases Φ. Therefore the identical polynomial rank and minimax-space bound apply.

Atlas-derived consequence
The derivation is stated in this record, rather than quoted as a theorem from the cited work.

Public rules are in §2.1. This is an explicitly defined captureless modification and a derived upper bound, not an attributed published result.

  • Solving KalahGeoffrey Irving, Jeroen Donkers, Jos Uiterwijk (2000).Published journal article · ICGA Journal 23(3) (2000), 139–147Read full text
Open this variant in the map →

Kalah with binary counts: an EXPTIME upper bound

In EXPTIME (upper bound)

Binary notation can describe exponentially many stones. A finite-state search gives an EXPTIME upper bound. This weaker bound does not show that binary Kalah is harder or rule out PSPACE.

Task
Decide the same winner problem when each pit count is written in binary.
Scale & input
The m-pit rows are explicitly listed. All pit and store counts are nonnegative binary integers, with their total S. The player to move and designated player are specified.
Move rules
Identical to the unary Kalah winner record, including captures, bonus choices, no source-pit skip and final collection. Only the encoding changes.
Players & goal
Two players, fully visible counts, deterministic play. The designated player must finish with a strictly larger store.
Repetition
The same decreasing rank guarantees termination, but its mS(S+1)+S bound is not polynomial in binary input length.
Connection
encoding change: Write stone counts in binary (Kalah: Scalable board, unary counts)

A polynomial-size position by itself does not imply a polynomial-space winner algorithm. No EXPTIME-hardness, separation from unary Kalah, or optimality of this upper bound is claimed.

Why this bound holds

For input length L, m≤L and log(S+1)=O(L). At most 2(S+1)^(2m+2)=2^poly(L) states specify all counts and the player to move. There are at most m successors per state. A complete sowing can be computed without iterating over individual stones: divide its count by the 2m+1 visited positions, add the quotient to each, and distribute the remainder along the sowing order, then apply the last-stone rule. Arithmetic is polynomial in L. The decreasing rank makes the graph acyclic, so backward induction over its exponential number of states takes exponential time.

Atlas-derived consequence
The derivation is stated in this record, rather than quoted as a theorem from the cited work.

§2.1 supplies the rules. The upper bound is derived here by enumerating the finite game graph, with at most 2(S+1)^(2m+2) positions and a polynomial-time move calculation using quotient and remainder.

  • Solving KalahGeoffrey Irving, Jeroen Donkers, Jos Uiterwijk (2000).Published journal article · ICGA Journal 23(3) (2000), 139–147Read full text
Open this variant in the map →

Mastermind

Count all compatible codes

#P-complete

Counting remains hard with just two colors.

Task
Count secret codes consistent with the supplied ratings.
Scale & input
Growing code length and explicit query list. Two colors suffice.
Move rules
Usual black and white feedback, repeated colors allowed.
Goal
Count compatible ordered codes.
Repetition
Static completion, no play-history restriction.
Players & information
Offline list known, hidden code not given.
Randomness
None.
Connection
task change: mastermind-consistency

Published result

Theorem 1 and Lemma 5.

Open this variant in the map →

Only exact-position feedback

NP-complete

Removing misplaced-color feedback leaves two-color consistency hard.

Task
Decide whether supplied guesses and exact-position counts have a compatible code.
Scale & input
Growing length and query list. Two colors suffice.
Move rules
Feedback counts matching positions only.
Goal
A compatible ordered code exists.
Repetition
Static completion, no play-history restriction.
Players & information
Offline queries and ratings known.
Randomness
None.
Connection
rule change: mastermind-consistency

Published result

Lemma 4 and Corollary 1.

Open this variant in the map →

Ignore order and fix the color count

P

A fixed palette gives only polynomially many color-count vectors to check.

Task
Count compatible unordered codes.
Scale & input
Growing code length, constant number of colors, explicit query list.
Move rules
Feedback counts color matches ignoring position, including exact-position matches.
Goal
Count compatible color multisets.
Repetition
Static completion, no play-history restriction.
Players & information
Offline queries and ratings known.
Randomness
None.
Connection
rule change: mastermind-consistency

The paper’s white-only score is total color overlap, not ordinary white feedback alone.

Published result

§2 definition of MSP-White; Lemma 1.

Open this variant in the map →

Minesweeper

Every safe cell must show 2

In NP; exact complexity open in 2018 source

This is stronger than displaying only 2s among the visible clues. Unrevealed safe cells must also become 2s. The thesis leaves this case unclassified.

Task
Decide consistency when every nonmine cell in the completed board must have exactly two adjacent mines.
Scale & input
Explicit finite rectangular partial board, with eight-neighbor clues.
Move rules
Complete unknown cells with mines or safe cells, respecting the visible entries and the all-2 rule.
Goal
Existence of a legal completion.
Repetition
Not a move-sequence task.
Players & information
One solver sees the entire partial instance.
Randomness
None.
Connection
rule change: Require all safe cells, revealed or hidden, to have clue 2 (Minesweeper: Can the clues all be true?)

Dated question. The 2024 Minesweeper-variants paper concerns other rules and does not supply a resolution for this completed-board restriction.

Open in the 2018 source

Definition 5; Table 3.1, row {2}, final column; §4.1

Open this variant in the map →

Nim

Neighboring Nim: heaps of at most 1

P

Heaps are 0/1. For direct equivalence with undirected vertex Geography, the previous-move vertex starts empty. Winner determination is polynomial-time.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Input: explicit undirected graph, current vertex, heap at each vertex. Move to the same or an adjacent vertex and decrease that heap. Graph size scales.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Every move strictly decreases one heap. No pass is permitted and no full state repeats.
Randomness
None.
Connection
equivalence: undirected-vertex-geography

Published result

Definitions 2.1–2.2; discussion immediately after Definition 2.2

Open this variant in the map →

Neighboring Nim: heaps of at most 2

PSPACE-complete

Heaps are 0/1/2. PSPACE-complete by directed Geography reduction. Each arc becomes a seven-vertex internal gadget with one heap of 2, all others 1.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Input: explicit undirected graph, current vertex, heap at each vertex. Move to the same or an adjacent vertex and decrease that heap. Graph size scales.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Every move strictly decreases one heap. No pass is permitted and no full state repeats.
Randomness
None.
Connection
rule change: Allow heaps of size 2 (Neighboring Nim: heaps of at most 1)

Published result

Theorem 3.1 and Corollary 3.5

Open this variant in the map →

Neighboring Nim: large binary heaps

PSPACE-hard; in EXPTIME

Arbitrary binary heaps preserve PSPACE-hardness. An exponential-time upper bound follows by evaluating all positions. Whether this can be improved to polynomial space is Open Problem 6.1 in the 2017 source.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Input: explicit undirected graph, current vertex, heap at each vertex. Move to the same or an adjacent vertex and decrease that heap. Graph size scales.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Every move strictly decreases one heap. No pass is permitted and no full state repeats.
Randomness
None.
Connection
restriction: Bound every heap by 2 (Neighboring Nim: heaps of at most 2)

PSPACE membership was open in the 2017 source; later status is not established by this record. The EXPTIME upper bound is derived from its rules, not claimed as a named theorem in that paper.

Open in the 2017 source · derived upper bound
The PSPACE-hardness is from the source. The EXPTIME upper bound is a finite-state consequence derived in the atlas.

Section 3.2 and Open Problem 6.1. Derived EXPTIME upper bound: there are at most |V| times the product of (heap size + 1) states. Each state has polynomially many bits, move enumeration is exponential at most, and every move decreases the total counters.

Open this variant in the map →

Three-pile Nim with one shared pass

Open characterization

Exactly three heaps and one shared pass, unavailable after all heaps empty. A May 2026 primary source still identifies the general losing-position formula as open. This does not establish PSPACE-hardness.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Input: binary heap sizes and whether a shared pass is unused. Make a normal Nim move or an allowed pass. A pass is consumed globally.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Every move decreases a heap or uses the single pass. No repeated state.
Randomness
None.
Connection
rule change: Add one nonterminal pass (Nim: Take the last counter)

This is an open characterization question in the May 2026 cited source. It is not itself a complexity lower bound.

Open in the 2026 source

2025 Definition 19 defines the rules. The 2026 preprint's abstract explicitly reaffirms the three-pile characterization question.

Open this variant in the map →

Nim with a pass only while a pile has at least 2

P

Changing pass availability restores a polynomial-time XOR test. XOR all heaps with a bit that is 1 exactly when a pass is unused and some heap is at least 2. Otherwise that bit is 0.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Input: binary heap sizes and whether a shared pass is unused. Make a normal Nim move or an allowed pass. A pass is consumed globally.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Every move decreases a heap or uses the single pass. No repeated state.
Randomness
None.
Connection
rule change: Pass threshold changes from 1 to 2 (Three-pile Nim with one shared pass)

Published result

Corollary 2 with every threshold m_i=2

Open this variant in the map →

Demi-quantum Boolean Nim

PSPACE-complete

Explicit 0/1 matrix: rows are configurations, columns are heaps. Only single ordinary moves are permitted, with illegal rows discarded. PSPACE-complete and polynomially isomorphic to Avoid True: each row maps to a clause on its zero columns.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Explicit scalable 0/1 matrix. Rows are alternative positions on named heaps. Choose one heap, remove its stick from each legal row, discard illegal rows. No superposed moves.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Each move removes one counter in every surviving row and discards rows where that move is illegal. No pass is allowed.
Randomness
None. Alternative configurations are deterministic, not random measurements.
Connection
equivalence: Avoid True

Published result

Theorems 3–4

Open this variant in the map →

Quantum Boolean Nim from a superposition

Σ₂^P-hard; in PSPACE

Explicit polynomial-width list of 0/1 heap configurations. Proved Σ₂^P-hard, and in PSPACE by Theorem 7.1. Completeness is unresolved in the source. The rule change allows superposed moves.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Input configurations share named heaps. Flavor D, width 2: select one ordinary move or two alternative moves, each legal somewhere. Retain every legal successor branch. This is deterministic, not probabilistic quantum mechanics.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Every surviving branch removes one counter per turn. No pass is allowed.
Randomness
None. Superposed moves are deterministic branching rules.
Connection
rule change: Allow superpositions of moves (Demi-quantum Boolean Nim)

Result in cited preprint

FUN Theorems 6–8; full version Theorem 7.1 and §8.1

Open this variant in the map →

Quantum Nim: heaps of at most 2, ordinary start

In PSPACE; exact complexity open in 2020 source

Single ordinary starting configuration, scalable heaps of size 0/1/2. In PSPACE. Open Question 8.3 asks whether it is polynomial-time solvable or PSPACE-complete, without asserting either.

Task
Decide whether the next player wins under optimal play.
Scale & input rules
Input configurations share named heaps. Flavor D, width 2: select one ordinary move or two alternative moves, each legal somewhere. Retain every legal successor branch. This is deterministic, not probabilistic quantum mechanics.
Players & information
Two alternating players, complete information.
Goal
The player with no legal move loses.
Repetition
Every surviving branch strictly loses counters each turn. No pass is allowed.
Randomness
None. Superposed moves are deterministic branching rules.
Connection
rule change: Different starting-position promise, not a reduction (Quantum Boolean Nim from a superposition)

Open question in the cited 2020 source. Later status is not established by this record.

Open in the 2020 source

Theorem 7.1; §8.1, Open Question 8.3

Open this variant in the map →

Quantum Boolean Nim from an ordinary position

P

An ordinary starting position is easy by parity. A supplied superposition of such positions has a proved hardness lower bound.

Task
Determine the winner from one ordinary 0/1-heap position.
Scale & rules
Scalable list of heaps, each 0 or 1. Flavor D, width 2: choose one ordinary move or two alternatives, each legal somewhere. Retain legal successor branches.
Players & goal
Two alternating players, perfect information. The player with no legal move loses.
Repetition & randomness
Each branch removes a stick per turn. No repeated positions or randomness. These are deterministic quantum-inspired rules.
Connection
restriction: Start with one ordinary position instead of a supplied superposition (Quantum Boolean Nim from a superposition)

Result in cited preprint

Section 8.1, paragraph preceding Open Question 8.3.

Open this variant in the map →

Long global Nim: explicit move set

In PSPACE (derived upper bound)

A subtraction size can be used only once across all piles. With S explicitly listed, at most |S| moves remain. Depth-first game-tree evaluation uses polynomial space, for binary or unary integers.

Task
Determine whether the player to move can win from supplied piles and available subtraction sizes.
Scale & input
An explicit list of nonnegative pile sizes and a finite explicit set S of positive integers. Pile count and |S| scale. Values may be binary or unary.
Move rules
Choose s in S and one pile containing at least s counters. Subtract s from that pile and delete s from S globally.
Goal
Normal play: the player with no legal move loses.
Repetition
No move size is reused. Every turn reduces |S| by one.
Players & information
Two alternating players, with all piles and S visible.
Randomness
None.
Connection
rule change: Supply allowed move sizes and forbid their reuse globally (Nim: Take the last counter)

This record establishes PSPACE membership only, without a matching lower bound or polynomial-time algorithm. The bound does not cover a succinct interval S={1,...,M} when M is binary and the interval is not expanded.

Why this bound holds

Each move deletes one member of the explicitly listed set S, so a play has at most |S| turns. Pile sizes only decrease and never require more bits than the input. A state contains the piles, a used-size bitmask and the player to move. A depth-first minimax stack of at most |S| such states uses polynomial space. This argument applies with unary or binary numbers, but not to an unexpanded binary-sized interval of allowed moves.

Atlas-derived upper bound
The paper supplies the game rules. The explicit-move-set PSPACE argument is given by the atlas, not attributed as a theorem to the paper.

Definition 22 supplies the rules. Upper-bound derivation: depth is at most |S|. A state stores the piles and a used-size bitmask, each polynomial in input length. A depth-first minimax stack is therefore polynomial space.

Open this variant in the map →

Quantum Unary Nim: ordinary start

In PSPACE; classification open in 2020 source

Theorem 7.1 gives PSPACE membership. Open Question 8.3 asks whether this problem has a polynomial-time algorithm or is PSPACE-complete. Ordinary unary Nim still has the XOR solution.

Task
Determine the winner from one ordinary position with unary-encoded heaps under the specified quantum-inspired rules.
Scale & input
A scalable explicit list of heaps, with every heap size written in unary. The initial position is one ordinary configuration, not a supplied superposition.
Move rules
Flavor D, width 2: choose one ordinary Nim move or two alternative Nim moves, each legal in some current branch. Retain all legal successor branches.
Goal
Normal play: the player with no legal move loses.
Repetition
Every surviving branch decreases its counter total. The maximum play length is at most the initial unary counter total.
Players & information
Two alternating players. The initial position and all choices are public.
Randomness
None. The branching rules are deterministic and do not model random measurements.
Connection
restriction: Restrict each unary heap to 0, 1 or 2 (Quantum Nim: heaps of at most 2, ordinary start)

The cited 2020 source poses P versus PSPACE-complete as an open question, not a proved dichotomy. Later status is not established by this record.

Open in the 2020 source

Theorem 7.1 and Section 8.1, Open Question 8.3. The membership theorem handles exponentially many possible branches without storing all of them at once.

Open this variant in the map →

Portal

Lasers, relays and moving platforms

PSPACE-complete

Laser-controlled platforms implement reusable memory latches.

Task
Decide whether the player can reach the exit.
Scale & input
Growing discretized 3D level, polynomially described finite state.
Move rules
Portals redirect lasers. Relays control moving platforms.
Goal
Reach the exit.
Repetition
Backtracking and repeated latch changes allowed.
Players & information
One player. Entire level known.
Randomness
None.
Connection
rule change: portal-cubes

Published result

§9, Theorem 14.

Open this variant in the map →

High-energy pellets and their catchers

NP-hard; in PSPACE (finite-precision model)

Activating every catcher within the constructed timing constraint encodes a grid Hamiltonian cycle.

Task
Decide whether the player can reach the exit.
Scale & input
Explicit growing level with pellet launchers, catchers, portals and catcher-controlled doors. Positions, velocities and timer states have polynomial-bit finite-precision encodings. Velocities are polynomially bounded, as assumed by the paper's PSPACE argument.
Move rules
Redirect pellets through portals. Pellets reflect and can kill the player. A launcher replaces its pellet only after the prior pellet is destroyed, so the number of active pellets remains bounded by the input.
Goal
Reach exit.
Repetition
Revisits allowed, timing can prevent a successful detour.
Players & information
One player. Entire level known.
Randomness
None.
Connection
rule change: portal-cubes

NP-hardness is a published theorem. The PSPACE upper bound applies to the specified finite-precision engine with polynomially bounded velocities and polynomial-bit state. It is not a claim about exact real-valued physics or NP-completeness.

Why this bound holds

The fixed level, player, doors and bounded number of active pellets have a polynomial-size state under the stated precision and velocity assumptions. A launcher creates a new pellet only when its previous pellet has disappeared. Thus the state graph has at most exponentially many vertices, and a successor can be computed in polynomial space. Nondeterministically search for an exit-reaching path while storing only the current state and a polynomial-bit step counter permitting exponentially many steps, then use NPSPACE=PSPACE. This is the argument given for the broader engine in the proof of Theorem 12, applied to the pellet-only mechanics.

Published hardness · atlas-derived upper bound
The source proves NP-hardness. The stated finite-state model gives the PSPACE upper bound.

Section 7, Theorem 9 proves NP-hardness. The finite-precision PSPACE upper bound is derived from Theorem 12's state-space argument, whose proof explicitly discusses pellets and their launchers, although its displayed mechanics list omits them.

Open this variant in the map →

Only the portal gun

Open in the 2018 source

The authors explicitly leave the portals-only mechanics set unresolved.

Task
Reach an exit using only portal placement and ordinary movement.
Scale & input
Scalable polygonal level with fixed-point coordinates and discrete time.
Move rules
One portal pair, ordinary movement, no other puzzle devices.
Goal
Reach the target.
Repetition
Allowed.
Players & information
One player, complete information.
Randomness
None.

Open in the cited 2018 source. Later status is not established by this record.

Open in the 2018 source

§10.1; model in §2

Open this variant in the map →

Only movable cubes

Open in the 2018 source

Cubes alone are an explicit open mechanics set. The proved cube result also uses buttons and doors.

Task
Reach an exit using movable cubes and ordinary movement.
Scale & input
Scalable polygonal level, discrete fixed-point model.
Move rules
Carry cubes and use them as platforms. No other puzzle devices.
Goal
Reach the target.
Repetition
Allowed.
Players & information
One player, complete information.
Randomness
None.
Connection
restriction: Remove buttons and doors (Portal: Cubes, floor buttons and doors)

Open in the cited 2018 source. Later status is not established by this record.

Open in the 2018 source

§10.1; model in §2

Open this variant in the map →

Rubik's Cube

Long thin cuboid: shortest solution

P search

Fixing two dimensions permits optimal solving in polynomial time.

Task
Find a shortest solving sequence.
Scale & input
c1×c2×n cuboid. c1 and c2 are constants, n grows. Reachable configuration.
Move rules
Legal slice turns preserving the cuboid, under the paper’s move model.
Goal
Minimize number of turns to solve.
Repetition
Reversible turns, revisits allowed.
Players & information
One player. All sticker colors known.
Randomness
None.
Connection
restriction: rubik-opt

Published result

§6, Theorem 6.

Open this variant in the map →

Turn several layers together

Open in the 2018 source

The shortest-solution theorem covers one slice at a time. The authors ask what happens when one move rotates a contiguous bundle of layers touching a face.

Task
Decide whether a scalable n × n × n cube can be solved within k wide turns.
Scale & input
Growing cube, explicit sticker configuration and move budget k.
Move rules
WTM permits quarter or half turns of a face-adjacent bundle. WQTM counts only quarter turns.
Goal
Make faces monochromatic within k moves.
Repetition
Repeated states allowed, subject to the budget.
Players & information
One solver, complete information.
Randomness
None.
Connection
rule change: Count a wide turn as one move (Rubik's Cube: Can it be solved within k turns?)

Open in the cited 2018 source. Later status is not established by this record.

Open in the 2018 source

§6 Future work

Open this variant in the map →

Rush Hour

Single-cell cars and fixed obstacles

PSPACE-complete

Even single-cell cars can encode long dependencies.

Task
Can the designated car reach the left boundary?
Model & rules
Growing explicit n × n board, one empty cell. Each unit car moves only horizontally or only vertically. Some cells are fixed obstacles. One player, full information, no randomness. Revisiting positions is allowed.

Published result

Definitions 2.1–2.2, Lemma 2.5 and section 4.

Open this variant in the map →

Single-cell cars without fixed obstacles

Open in the 2020 source

Removing fixed obstacles was left unresolved by the unit-car hardness paper.

Task
Can the designated unit car reach the left boundary?
Model & rules
Growing explicit square grid. Every car is movable but retains its horizontal or vertical direction. No fixed obstacles. One player, full information, no randomness, repeated positions allowed.
Connection
rule change: Permit fixed obstacles (Single-cell cars and fixed obstacles)

This is a dated open question, not an assertion that no later solution exists.

Open in the 2020 source

Section 5, Open Problems.

Open this variant in the map →

Scrabble

Keep the total number of tiles fixed

P

A constant total tile count leaves only polynomially many configurations as the board grows.

Task
Determine the winner in the derandomized model.
Model & rules
Growing explicit board, constant total tiles including the position and bag, known bag order and racks. Two players, equal letter scores, no random draws, tiles never removed.
Connection
restriction: Bound total tile count (Scrabble: Known bag order)

The constant is the total number of tiles in the instance, not merely the tiles left in a small bag beside an arbitrarily populated board.

Published result

§2, paragraph on unbounded generalization

Open this variant in the map →

Sokoban

Just get the player to an exit

PSPACE-complete

Replacing crate-storage goals with one player destination still leaves a PSPACE-complete problem.

Task
Push-1F: can the player reach a designated cell?
Model & rules
Growing explicit rectangular grid with unit crates and fixed walls. Orthogonal steps may push one crate by one cell into empty space. No pulling or gravity. One player, full information, no randomness. Positions may repeat.
Connection
rule change: Remove internal fixed walls (Reach an exit without fixed walls)

A related rule-and-goal variant called Push-1F, not the ordinary Sokoban storage task.

Published result

Sections 1 and 6.

Open this variant in the map →

Reach an exit without fixed walls

PSPACE-complete

The no-fixed-wall reachability question was settled by a 2025 proof, revised in 2026.

Task
Push-1: can the player reach the specified destination?
Model & rules
Growing explicit rectangular grid, unit movable crates, start and destination. Orthogonal moves push at most one crate one cell. No pulling, gravity or internal fixed walls. Repeated positions allowed. One player, complete information, no randomness.

Clusters of movable crates can still be immobile. Older sources that list this task as open are outdated.

Published result

Sections 1 and 6 of arXiv v2.

Open this variant in the map →

Sliding blocks with a unique route to the exit

Hardness conjectured in the 2025 source

The paper proves hardness for a storage-goal uniqueness promise, then conjectures analogous hardness when the objective is reaching an exit. Ordinary walks between pushes do not distinguish solutions.

Task
Decide solvability of PushPush pathfinding with at most one successful ordered sequence of pushes.
Scale & input
Explicit scalable bounded square grid, block positions, player start and exit.
Move rules
Push one adjacent block until it hits another block or the boundary. No momentum transfer.
Goal
Move the player to the exit, rather than cover storage sites.
Repetition
At most one successful push sequence is promised.
Players & information
One solver, complete information.
Randomness
None in gameplay. The proposed hardness comparison permits randomized reductions.
Connection
rule change: Blocks slide to obstacles; require a unique push sequence to an exit (Sokoban: Crates onto targets?)

The cited 2025 source conjectures no polynomial algorithm unless NP = RP. This is not a proved PSPACE-hardness result for the promised version. Later status is not established by this record.

Open in the 2025 source

§4 Concluding Remarks

Open this variant in the map →

Tetris

Only two columns

P

Two columns admit a polynomial-time algorithm.

Task
Decide whether the known piece sequence can survive, optionally clearing the board.
Model & rules
Explicit initial board of variable height, fixed width two, explicit tetromino sequence. One informed player, no randomness. Pieces fall, rotate and lock. Full rows disappear. Section 2 uses partial lock-out and specified rotation restrictions.
Connection
restriction: Restrict the width from eight columns to two (Eight columns still suffice)

Published result

Sections 2–3, Theorem 3.2. The theorem also permits larger polyominoes.

Open this variant in the map →

Eight columns still suffice

NP-complete

A fixed width of eight preserves NP-completeness.

Task
Decide survival or complete board clearing for the supplied sequence.
Model & rules
Height, initial occupied cells and finite tetromino sequence are input. One informed player, no randomness. Section 2 rotation and partial lock-out rules apply. This is not a fixed 10 × 20 board.

Published result

Sections 2 and 4, Theorem 4.1.

Open this variant in the map →

Only one tetromino shape

NP-complete (explicit sequence)

A 2026 result gives hardness for each single shape I, T, S, Z, J and L.

Task
Decide clearing or survival for the supplied finite run of one piece type.
Scale & input
Explicit growing board, initially filled cells and prescribed number of identical pieces.
Move rules
Super Rotation System (SRS), including wall kicks.
Goal
Clear the board, or place all pieces without losing.
Repetition
Pieces consumed in order.
Players & information
One player. Entire input known.
Randomness
None.
Encoding
The finite sequence is explicitly listed, equivalently a unary count of identical pieces. A compact binary count is a different input model.
Connection
rule change: Use SRS wall kicks and one piece shape, and change the goal from a row target to clearing the board or surviving the sequence (Tetris: Know every upcoming piece)

O (square) is excluded. The rotation model is essential. Source states NP-hardness.

Why this bound holds

For each of K explicitly given pieces, store its placement and a path through the polynomial-size orientation/position graph for the current fixed board. A simple path suffices. Verify legal SRS moves, locking and line clears. The total certificate is polynomial in K plus the explicit board size. The hardness construction uses polynomially many identical pieces.

Published hardness · atlas-derived membership
The source proves NP-hardness. Membership in NP uses the explicitly listed finite piece sequence (or unary count).

§1.1 and §§5–9. NP membership for this explicit-sequence model follows from polynomial-size legal-placement certificates.

Open this variant in the map →

I-pieces with three empty top rows

P

With room at the top, indefinite survival is guaranteed and eventual clearing is polynomial-time.

Task
Decide whether the board can eventually be completely cleared with enough I-pieces.
Scale & input
Growing board of height at least 7. Top three rows empty. Unlimited identical I-pieces.
Move rules
Translate and rotate straight tetrominoes under the paper’s model.
Goal
Eventually clear the board.
Repetition
Unlimited supply.
Players & information
One player. Initial board known.
Randomness
None.
Connection
task change: tetris-single-shape (Only one tetromino shape)

Both initial conditions and the supply/goal differ from finite-count hardness.

Published result

§3.1, Theorem 1 with k=4.

Open this variant in the map →

Dominoes that can rotate downward

P

The falling rotation rule allows a polynomial-time algorithm.

Task
Decide survival for a specified count, or eventual clearing with unlimited dominoes.
Scale & input
Growing board. Only 1×2 pieces. Explicit finite count for survival or unlimited supply for eventual clearing.
Move rules
Rotation keeps a lowest cell fixed and moves the other to an unoccupied cell no higher.
Goal
Survive the specified count, or eventually clear.
Repetition
Pieces may continue indefinitely for the latter task.
Players & information
One player. Initial board and supply known.
Randomness
None.
Connection
rule change: tetris-offline

Does not classify clearing with an arbitrarily short prescribed domino count.

Published result

§2.2; §3.2, Theorem 6 and Corollary 7.

Open this variant in the map →

The Legend of Zelda

Minecarts that cannot block walking paths

PSPACE-hardness open in the 2023 source

The proved construction uses parked minecarts as barriers. Question 1 asks whether that ingredient is necessary.

Task
Determine whether generalized Zelda minecart navigation remains PSPACE-hard without carts blocking walking routes.
Scale & input
Explicit scalable 2D rooms with tracks, carts, start and goal.
Move rules
Ride minecarts, switch T-junctions with levers, retain minecart-only doors. Exclude using parked carts to block walking paths.
Goal
Reach the target location.
Repetition
Revisits and repeated track switches allowed.
Players & information
One solver, complete information.
Randomness
None.

Hardness is open in the cited 2023 source; later status is not established by this record. The question itself supplies no lower bound for this restriction.

Open in the 2023 source

§5.5, Question 1 following Theorem 5.9

Open this variant in the map →

TwixT

Pencil-and-paper TwixT

PSPACE-complete

Allowing links of the same color to cross preserves the hardness construction. Pegs still fill the board permanently, giving a polynomial bound on the number of turns.

Task
Determine whether a player can force a connection.
Model & rules
Growing board and arbitrary peg/link position, two players with full information, no chance. Same-color links may cross. Opposite colors cannot cross. Peg count increases each turn.
Connection
rule change: Allow crossings between own links (TwixT: Connect opposite sides)
Why this bound holds

Every turn adds a peg to an empty cell. At most N turns remain on an explicit N-cell board. A state, including links, has polynomial size. Enumerating legal turns and a depth-first minimax search use polynomial space. The same-color-crossing rule preserves these facts, and the paper explicitly extends its Hex hardness reduction to twixtpp.

Published hardness · atlas-derived membership
The source proves PSPACE-hardness. The polynomial move horizon supplies the PSPACE upper bound.

Bonnet, Jamain and Saffidine, Section 3.1: hardness after Theorem 1 plus the preceding polynomial-game-length membership argument.

Open this variant in the map →

UNO

Keep the number of colors fixed

P

Fixing either colors or numbers makes solitaire UNO polynomial-time.

Task
Decide whether every card can be played.
Model & rules
Explicit growing card multiset, same matching rule, no action cards or draws. One player, all information known, no randomness. Each card is discarded once.
Connection
restriction: Bound colors or numbers (UNO: Order all the cards)

Published result

§3.3, Theorem 5

Open this variant in the map →

Two players cooperate

NP-complete

Cooperation is NP-complete in the scalable visible-hand model.

Task
Can both players cooperate to empty player 1’s hand first?
Model & rules
Two visible hands, unbounded card colors and numbers, no draw pile or action cards. Alternate discards. A stuck player skips rather than loses. No voluntary pass. Cards never return.
Connection
rule change: Cooperate, and skip if stuck (UNO: Two players, visible hands)

Published result

§§2.3, 3.1, Theorem 1

Open this variant in the map →

Primary sources