Games & Complexity

Sliding tiles · Any solution?

P

If you only ask whether a solution exists, the scalable sliding-tile puzzle has a polynomial-time algorithm. The challenge changes when the route must be short.

Exact question: Decision: does any sequence reach the target arrangement?

Scale & input

An n×n board with n²−1 distinct unit tiles and one blank; both arrangements are input.

Move rules

Swap the blank with an orthogonally adjacent tile, one tile per move.

Goal

Reach the complete prescribed arrangement.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Sliding tiles · At most k slides?

NP-complete

The same tiles become an NP-complete decision problem when you must reach the target within a specified number of slides.

Exact question: Decision: reach the target in at most input k single-tile moves.

Scale & input

Same n×n, n²−1 distinct tiles and one blank; start, target and k are input. The nonnegative integer k may be binary encoded; polynomial puzzle diameter bounds a needed certificate.

Move rules

A single adjacent tile slides into the blank; this costs one move.

Goal

Reach target without exceeding k.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Finding a shortest sequence is an optimization problem and NP-hard; the label here is for its budget decision version.

Rectilinear Steiner tree · Short connecting tree?

NP-complete

Connect given points with horizontal and vertical segments, keeping the total length within a budget. This network-design problem supplies the hardness proof for short sliding-tile solutions.

Exact question: Decision: can integer-coordinate terminals be connected by a rectilinear tree of total length ≤ℓ?

Scale & input

Variable number of plane terminals and input length budget.

Move rules

Not sequential: choose horizontal/vertical segments and optional junctions.

Goal

A connected tree through every terminal within the budget.

Repetition

Not applicable

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Constraint logic · Reverse one edge?

PSPACE-complete

A small graph of weighted arrows can encode surprisingly complex sequences. Reversing one chosen arrow is the source problem for the Rush Hour construction.

Exact question: Decision: can a legal move sequence reverse a designated edge?

Scale & input

Growing planar AND/OR graph, initial legal orientation, designated edge; protected OR restriction is available.

Move rules

Reverse one edge while keeping incoming total weight at least 2 everywhere. AND incident weights 1,1,2; OR weights 2,2,2.

Goal

Reverse the designated edge.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Nondeterministic means a choice of moves, not random outcomes.

Constraint logic · Reach a full target?

PSPACE-complete

Here the target specifies every arrow, not just one. This version of constraint logic supplies the Sokoban construction.

Exact question: Decision: is prescribed legal orientation B reachable from orientation A?

Scale & input

Growing planar AND/OR graph; both complete edge orientations are input.

Move rules

Reverse one edge, always preserving incoming weight ≥2 at every vertex. AND incident weights are 1,1,2; OR incident weights are 2,2,2.

Goal

Match every edge in the target orientation.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Rush Hour · Can the car escape?

PSPACE-complete

Even with only straight cars of length two or three, deciding whether the exit car can escape is PSPACE-complete on growing boards.

Exact question: Decision: can a designated car reach its exit?

Scale & input

A growing grid with 1×2 and 1×3 cars.

Move rules

Cars translate only along their long axis; no turning or overlapping.

Goal

Bring the designated car to the specified border location.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Sokoban · Crates onto targets?

PSPACE-complete

Pushing crates is powerful enough to simulate a constraint graph. Hardness even survives removing fixed barrier pieces from the scalable puzzle.

Exact question: Decision: can every target square be occupied by a crate?

Scale & input

Growing finite grid with a walker, unit crates and an equal number of target cells. This record uses the no-fixed-barrier construction.

Move rules

Walker moves one orthogonal step, pushing at most one crate if the next cell is empty; pulling prohibited.

Goal

Crates occupy all targets.

Repetition

Repeated positions allowed; no repetition ban

Players & information

1 player; Complete: entire input is known

Randomness

None

No fixed barriers does not mean no obstacles: packed crates can be immovable. Reduction starts from NCL configuration-to-configuration, not directly the edge task.

Latin squares · Complete rows & columns

NP-complete

Fill the grid so every symbol appears once per row and column. Its completions can be embedded one-for-one in a larger Sudoku.

Exact question: Decision: can a partial Latin square be completed?

Scale & input

An n×n grid using n symbols, with arbitrary givens.

Move rules

Fill blank cells; no sequential move restriction.

Goal

Every row and column has every symbol once, preserving givens.

Repetition

Not applicable

Players & information

1 player; Complete: entire input is known

Randomness

None

Complexity is for the scalable family, not a fixed commercial board.

Sudoku · Does a completion exist?

NP-complete

Deciding whether a partial generalized Sudoku has any completion is NP-complete. A fixed 9×9 newspaper puzzle is not the scalable family in this theorem.

Exact question: Decision: is there a completed grid respecting all givens?

Scale & input

An n²×n² grid with n×n boxes and n² symbols; arbitrary partial instances without a uniqueness promise.

Move rules

Fill blank cells; no sequential move restriction.

Goal

Every row, column and box contains every symbol once.

Repetition

Not applicable

Players & information

1 player; Complete: entire input is known

Randomness

None

No uniqueness promise. The claim is about a growing n²×n² family, not just fixed 9×9 boards. Finding a grid, deciding existence and counting grids are different tasks.

Different questions

Find one completion

Search task, not labelled NP-complete here.

Given one completion, does another exist?

NP-complete decision problem (Yato–Seta, Theorems 3.4 and 4.8).

Count all completions

#P-complete, using the paper’s parsimonious reductions (p. 2 and Theorem 4.8).

Quantified Boolean formulas · Can you force true?

PSPACE-complete

Imagine two players choosing true or false values in a fixed order. One wants the final formula true, the other false. This is a starting point for game reductions.

Exact question: Is a fully quantified Boolean formula, in prenex form with a conjunctive-normal-form (CNF) matrix, true?

Scale & input

Explicit sequence of quantifiers followed by a CNF formula (an AND of clauses, each an OR of literals). The formula and number of variables grow.

Move rules

Existential and universal choices follow the quantifier order; the final assignment is evaluated.

Goal

The existential chooser wants true; the universal chooser wants false.

Repetition

Each variable is assigned once.

Players & information

Two choosers; all earlier choices visible

Randomness

None

This hub uses the quantified-CNF decision problem. The game analogy explains the quantifiers; there is no random assignment.

Geography · Arrows · no vertex reuse

PSPACE-complete

Move along arrows without returning to a visited vertex. Deciding who can force the last legal move is PSPACE-complete.

Exact question: Can the player to move force a win from the supplied graph and token position?

Scale & input

An explicitly given directed graph of arbitrary size and a starting vertex.

Move rules

Players alternate moving one shared token along an outgoing arrow to an unvisited vertex.

Goal

A player with no legal move loses.

Repetition

Vertices cannot be revisited; at most |V|−1 token moves.

Players & information

Two players; Perfect information

Randomness

None

The source counts placing the initial marker as a turn; specifying who moves next, or adding a forced prefix, translates conventions.

Geography, two-way paths · Two-way · no vertex reuse

P

Make the paths two-way and keep the ban on revisiting vertices. Maximum matching now gives a polynomial-time winner algorithm.

Exact question: Can the player to move force a win from the supplied graph and token position?

Scale & input

An explicitly given undirected graph of arbitrary size and a starting vertex.

Move rules

Move the shared token to a neighbor, deleting the vertex just left.

Goal

A player with no legal move loses.

Repetition

No vertex revisits.

Players & information

Two players; Perfect information

Randomness

None

The player to move wins exactly when every maximum matching covers the token's vertex. Compare maximum-matching sizes in G and G−v.

Geography, use each edge once · Two-way · no edge reuse

PSPACE-complete

Still use two-way paths, but use up each edge rather than each vertex. Vertices can be revisited, and winner determination is PSPACE-complete again.

Exact question: Can the player to move force a win from the supplied graph and token position?

Scale & input

An explicitly given undirected graph of arbitrary size and a starting vertex.

Move rules

Move the shared token along an unused edge, then delete that edge.

Goal

A player with no legal move loses.

Repetition

Edges cannot be reused; vertices may be revisited. At most |E| moves.

Players & information

Two players; Perfect information

Randomness

None

Hardness persists on planar graphs of maximum degree 3. Bipartite graphs admit a polynomial algorithm.

Hex · From a given position

PSPACE-complete

From a supplied partly filled board, deciding who can force a connection is PSPACE-complete as the board grows.

Exact question: Does the player to move have a winning strategy from the supplied partly filled board?

Scale & input

An n×n rhombus of hexagonal cells, with n part of the input; arbitrary supplied positions.

Move rules

Alternate placing a stone of your color on an empty cell. No swap/pie rule.

Goal

Connect your assigned opposite sides with your stones.

Repetition

Stones never move or disappear; no cell is played twice.

Players & information

Two players; Perfect information

Randomness

None

This classification does not concern only a fixed 11×11 commercial board, or only empty starting boards.

Hex, empty board · From an empty board

P

On every empty square Hex board without a swap rule, the first player has a winning strategy. This settles the winner question, not how to play the winning moves.

Exact question: On an empty n×n board without the swap rule, does the first player have a winning strategy?

Scale & input

Empty square rhombus boards of every size n≥1.

Move rules

The same placement and connection rules as Hex; no swap/pie rule.

Goal

Connect your assigned opposite sides with your stones.

Repetition

Stones remain fixed; a cell can be filled only once.

Players & information

Two players; Perfect information

Randomness

None

The decision answer is always yes. Strategy stealing establishes existence; this is not an efficient method for finding the winning moves.

Othello · Who can win?

PSPACE-complete

Flipping disks can simulate a route through a graph. A final region makes the simulated result decide the score.

Exact question: Decision: can Black force a win from this position?

Scale & input

Arbitrary position on a variable n×n board.

Move rules

Place a disk bracketing opposing disks; flip all bracketed lines. Pass only without a legal move.

Goal

More disks after both players pass.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

The result concerns arbitrary growing boards, not the usual opening on 8×8.

Go · Ko-free hardness construction

PSPACE-hard

Even constructions without ko battles encode a hard strategy problem.

Exact question: Can Black force a win from the supplied generalized Go position under the paper’s scoring and pass rules?

Scale & input

Variable n×n board; a supplied stone position.

Move rules

Place stones, capture surrounded groups, or pass.

Goal

Territory minus captured own stones; two passes end play.

Repetition

The hardness construction avoids ko; no claim about equivalence of repetition rules.

Players & information

Two players; all information visible.

Randomness

None.

This is the paper’s ko-free hardness construction, not a complete classification of every modern Go ruleset.

Dots & Boxes · More boxes than your opponent?

PSPACE-complete

The pencil-and-paper game can encode competing choices of variables in a logical formula.

Exact question: Decision: can the player to move force a higher final score?

Scale & input

Growing rectangular grid; existing lines, scores and turn supplied.

Move rules

Draw an unused unit edge. Completing a box scores a point and grants another turn.

Goal

Higher score when every edge is drawn.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Scores are part of the supplied position. This does not classify the empty-board opening alone.

Amazons · Last player able to move?

PSPACE-complete

A queen-like move followed by a blocking arrow can implement logical wires and gates.

Exact question: Decision: can the player to move force a win?

Scale & input

Arbitrary n×n position with a growing number of amazons.

Move rules

Move an amazon as a chess queen, then shoot a queen-moving arrow that permanently blocks its destination. No captures.

Goal

Opponent has no legal move.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

The proof uses many amazons. It is not a hardness proof for only four per side.

Hive · Generalized, multiple queens

PSPACE-hard; in EXPTIME

The requirement that pieces remain connected can lock other pieces in place and encode logical choices.

Exact question: In the multi-queen n-Hive generalization, can a specified player force a win?

Scale & input

n-Hive: growing equal piece sets, including multiple queens. All pieces already placed in the proof. The supplied position is a legal connected hive.

Move rules

Usual piece movements, One Hive and Freedom To Move rules. A player with no legal placement or movement must pass.

Goal

Surround any opposing queen. Simultaneous loss is a draw.

Repetition

No move cap or repetition prohibition is imposed.

Players & information

Two players; all information visible.

Randomness

None.

Publication status

Published in FUN 2026 proceedings on May 15, 2026.

The EXPTIME upper bound is a finite-state consequence derived here, not a theorem asserted by the source. The multi-queen generalization and no history-dependent repetition rule are essential. Ordinary commercial Hive is a fixed finite game.

Nim · Take the last counter

P

Compute the bitwise XOR of the heap sizes. A nonzero result means a winning move exists. This takes polynomial time for binary or unary input.

Exact question: Decision: does the player to move have a winning strategy?

Scale & input

A scalable explicit list of heap sizes, in binary or unary. A binary heap h uses O(log(h+1)) bits, but the input also includes every heap.

Move rules

Remove any positive number of counters from one heap.

Goal

Take the last counter.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

The XOR algorithm makes Nim easy. Compact binary notation alone does not imply efficient solvability, and changing to unary does not make ordinary Nim hard.

Nim · Avoid the last counter

P

The same XOR test works until every nonempty heap has size one. Then parity decides the outcome.

Exact question: Decision: does the player to move have a winning strategy?

Scale & input

A scalable explicit list of heap sizes, in binary or unary.

Move rules

Remove any positive number from one heap.

Goal

Make the opponent take the last counter.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

With only singleton heaps remaining, an even positive number of heaps is winning.

Chess · Force checkmate

EXPTIME-complete

Ordinary piece movements can encode repeatedly changing logical variables.

Exact question: Decision: can the designated player force a win?

Scale & input

Arbitrary n×n position; one king per side; numbers of other pieces grow with n.

Move rules

Standard movement and capture of the chess pieces used in the construction.

Goal

Force the opponent’s king into checkmate.

Repetition

Unbounded-play model: no polynomial draw clock; endless play is not a forced win.

Players & information

Two players; all information visible.

Randomness

None.

Not a theorem about fixed 8×8 chess, modern move-count draw rules, or reachability from the standard opening.

Checkers · Every turn must capture

PSPACE-complete

Requiring a capture every turn bounds the game’s length, but optimal play remains PSPACE-complete.

Exact question: Decision: can the first player force a win?

Scale & input

Supplied n×n position.

Move rules

Mandatory jumps; continue the capture sequence while possible. Kings jump in either direction.

Goal

Opponent cannot jump.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Noncapturing moves are forbidden, even when no capture exists.

Checkers · Work together

NP-complete

Cooperation changes the always-jumping game into a solution-existence puzzle.

Exact question: Decision: can cooperating players eliminate one color?

Scale & input

Supplied n×n position.

Move rules

Alternate mandatory capturing turns; continue available jumps.

Goal

Remove every piece of either color.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two sides cooperate; complete information.

Randomness

None.

This claim concerns the always-jumping variant.

Formula game · Choose which variable to claim

PSPACE-complete

Players choose previously unchosen variables in any order. One sets theirs true, the other false.

Exact question: Decision: can the True player force the formula to be true?

Scale & input

A positive CNF formula of arbitrary size.

Move rules

True moves first. Players alternate choosing one unassigned variable; True assigns true and False assigns false.

Goal

True player wants every clause true after all variables are assigned.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Unlike a quantified prefix, players choose the order of variables.

Geography · Sparse planar directed graph

PSPACE-complete

Hardness survives even when edges can be drawn without crossings and every vertex has at most three neighbors.

Exact question: Decision: can the next player force a win?

Scale & input

Directed planar bipartite graph, maximum total degree three; start vertex supplied.

Move rules

Move to an unvisited out-neighbor.

Goal

Opponent has no move.

Repetition

Impossible: play permanently consumes resources.

Players & information

Two players; all information visible.

Randomness

None.

Directions still matter. This is not undirected vertex Geography.

Quoridor · Reach the far side first

PSPACE-complete

Wall placement can encode a formula. Having a path available does not mean you can win the race.

Exact question: Decision: can White force a win from a supplied position?

Scale & input

n×n board, one pawn each; existing walls and remaining wall supplies are input. Wall supply grows with board area.

Move rules

Move the pawn, including a jump over an adjacent opposing pawn or a side-step when a straight jump is blocked, or place a length-two wall. Walls cannot cross or overlap. Each player must retain a path to a goal edge.

Goal

Reach the opposite edge first.

Repetition

No repetition ban or move cap. Endless play is not a forced win.

Players & information

Two opponents; complete information.

Randomness

None.

Publication status

2026 preprint. The linked manuscript supplies the stated result.

2026 preprint result for supplied positions, not a solution of the standard 9×9 opening.

Super Mario Bros. · Persistent level state

PSPACE-complete

A Spiny moving between two tunnels acts as a reusable door. Remembering its position lets a level encode a long computation.

Exact question: Can Mario reach the flagpole in the supplied level?

Scale & input

Arbitrary explicitly described level. Off-screen sprites persist, or the whole level fits a scalable screen. Timer may grow exponentially.

Move rules

Small Mario, blocks, jumps, Spinies and firebars. Backtracking allowed.

Goal

Reach the flagpole.

Repetition

No ban on revisiting positions.

Players & information

One player; complete level description.

Randomness

Deterministic modeled dynamics.

This is SMB-general, not the fixed NES cartridge or its ordinary screen/reset limits.

Super Mario Bros. · Bounded screen, off-screen reset

P

Forgetting distant objects can make the generalized game efficiently solvable.

Exact question: Can Mario finish the supplied level or level sequence in the reset model?

Scale & input

Explicitly encoded levels; constant screen size and constant number of on-screen sprites.

Move rules

The SMB-standard reset model of Section 2. Far-off-screen state is forgotten.

Goal

Reach the flagpole or finish the level sequence in the modeled game.

Repetition

Revisits allowed, with the specified resets.

Players & information

One player; complete level description.

Randomness

Deterministic modeled dynamics.

The encoding matters: arbitrary run-length compression is not covered by this P result.

Donkey Kong Country · Generalized stage reachability

PSPACE-complete

A movable tire and icy slope act as a switch that opens or closes a route.

Exact question: Can the player reach the designated goal from the supplied start?

Scale & input

Stage size and remembered state scale; not a fixed commercial stage.

Move rules

One Kong; rolling tires, ice, ropes, barrel cannons and Zingers.

Goal

Reach a designated goal from the start.

Repetition

Revisits allowed.

Players & information

One player; fully specified stage.

Randomness

Deterministic enemy patterns in the construction.

Idealized glitch-free rules; a fixed screen with resetting state is a different model.

The Legend of Zelda · A Link to the Past: hookshot puzzles

NP-hard; in PSPACE

Pushing a block can make it a future hookshot target. The final route checks whether earlier choices opened every required crossing.

Exact question: Can Link reach the target using the hookshot rules in this model?

Scale & input

Explicit arbitrary-size dungeon with polynomial-bit coordinates and object state. State needed by the construction persists.

Move rules

Hookshot, movable blocks, treasure chests and crossing paths.

Goal

Reach a specified target location.

Repetition

Revisits allowed.

Players & information

One player; complete dungeon description.

Randomness

No random element used by the reduction.

This mechanic-based model is NP-hard and in PSPACE. NP-completeness is not established by the original theorem. Persistent object state uses polynomially many bits.

The Legend of Zelda · A Link to the Past: doors and switches

PSPACE-complete

Switches make a reusable door network. Gates must remember their state when Link leaves the room.

Exact question: Can Link reach the target using the switch rules in this model?

Scale & input

Arbitrary-size dungeon. Floor-switch gate states explicitly persist across rooms.

Move rules

Floor switches, gates, crystal switches, pillars and one-way teleporter tiles.

Goal

Reach a specified target location.

Repetition

Revisits allowed.

Players & information

One player; full dungeon and engine state.

Randomness

Hard construction uses no random behavior. General upper bound uses polynomially encoded engine/seed state.

The cross-room memory assumption is explicit in the theorem, rather than assumed from every Zelda release.

Metroid · Generalized Morph Ball levels

NP-hard; in PSPACE

Samus can clear a route earlier by shooting enemies from a different corridor. Later, Morph Ball mode removes the option to shoot.

Exact question: Can the player reach the specified target location?

Scale & input

Explicit arbitrary-size map with polynomial-bit room and object state and enough persistent state for the gadgets.

Move rules

Original Metroid movement and shooting; Morph Ball and Zoomers.

Goal

Reach a specified target location.

Repetition

Revisits allowed.

Players & information

One player; full level and modeled engine state.

Randomness

Deterministic engine once its polynomial-bit pseudorandom state is supplied. The hardness construction succeeds independently of favorable health drops.

The upper bound is for the deterministic modeled engine, including a supplied polynomial-bit pseudorandom state. It is not an almost-sure-win or expected-score theorem for hidden genuine randomness.

Pokémon · Trainer-only route planning

NP-complete

Battles can be predetermined wins or losses and route planning is still hard. A trainer who steps forward changes which corridors are safe.

Exact question: Can the player reach the target through the supplied trainer layout?

Scale & input

Arbitrary-size overworld; fixed-size Pokémon teams and battle mechanics.

Move rules

Walls and enemy trainers only in the overworld. Trainers have sight lines, approach the player and become inert after defeat.

Goal

Reach a target location by a successful route.

Repetition

Travel may revisit squares. Each trainer battle changes that trainer permanently.

Players & information

One human player; trainer layouts and battle states given. Battle subgames have constant size in the model.

Randomness

Hardness uses battles with certain outcomes. No hidden team information or random encounter mechanic is used.

This is not competitive Pokémon battle complexity. Restricting the overworld to trainers is essential to the NP upper bound.

Lemmings · Save one lemming with two skills

PSPACE-complete

One lemming is enough. Building and bashing let the player close and reopen passages.

Exact question: Can the single lemming be guided alive into an exit?

Scale & input

Explicit pixel landscape with steel and deadly zones. Skill budgets and allowed time can be exponentially large or unlimited.

Move rules

Only Builder and Basher skills; at most one skill assignment per time step.

Goal

Get the single lemming into an exit alive.

Repetition

Repeated paths and repeated construction/destruction allowed.

Players & information

One player; complete level and deterministic lemming behavior.

Randomness

None.

Not a polynomial-move-budget claim. The linked author manuscript is an earlier version whose main PSPACE theorem agrees with the 2015 final paper.

Lemmings · Polynomial building and digging budgets

NP-complete

Polynomially many terrain-changing commands give a short certificate. Even with only Climber skills, choosing which lemmings to save encodes a satisfiability problem.

Exact question: Can at least the required number of lemmings be rescued?

Scale & input

Explicit landscape. Builder, Basher and Miner budgets polynomial in landscape size. Other skill budgets may be larger. The total number of lemmings is polynomial in the number of landscape cells.

Move rules

All eight classic skills permitted under the given budgets. Deadly zones/traps are permitted. Other unavailable skills have budget zero in the hardness construction.

Goal

Rescue at least a supplied number of lemmings.

Repetition

Revisits and long waits allowed.

Players & information

One player; full deterministic level.

Randomness

None.

This concerns saving at least a supplied threshold of lemmings. It does not claim hardness for rescuing every lemming or for one lemming under these bounded budgets.

Portal · Cubes, floor buttons and doors

PSPACE-complete

Portals are not needed: a cube placed on either of two floor buttons stores a bit that controls doors elsewhere.

Exact question: Can the player reach the exit in the cube-and-door model?

Scale & input

Arbitrary-size discretized 3D level; fixed-point positions/velocities and polynomially described state.

Move rules

Pick up cubes, press weighted buttons, pass connected doors. No Portal Gun or long-fall mechanic required.

Goal

Reach the level exit.

Repetition

Backtracking and repeated switch changes allowed.

Players & information

One player; complete level.

Randomness

None in the construction.

The result concerns the specified generalized finite-state model, not the finite set of shipped test chambers.

Portal · Timed buttons and doors

NP-hard; in PSPACE

The exit opens only while every timer is active. Reaching it becomes a race to visit every switch without wasting a detour.

Exact question: Can the player reach the exit while the required timed doors are open?

Scale & input

Explicit arbitrary-size level with configurable timer lengths. Polynomial-bit finite-precision state and polynomially bounded velocities, as in Theorem 12.

Move rules

Walk between timed buttons; buttons temporarily open connected doors. No Portal Gun needed.

Goal

Reach the exit before required doors close.

Repetition

Revisits allowed, but timers can make them fatal to a successful route.

Players & information

One player; full level and timer settings.

Randomness

None in the construction.

Configurable timers are required for hardness. PSPACE membership assumes the paper's finite-precision model, polynomially bounded velocities and polynomial-bit state. This does not assert NP-completeness.

Candy Crush / Bejeweled · Offline target-gem problem

NP-hard

A cascade can encode a logical choice. Which columns fall determines whether one chosen gem can ever be matched.

Exact question: Can a sequence of legal swaps pop the designated gem?

Scale & input

Arbitrary rectangular board; six gem types; all replacement gems known beforehand.

Move rules

Swap adjacent gems to form matches. Matching lines disappear simultaneously, gravity acts, and cascades resolve.

Goal

Pop one designated gem.

Repetition

No imposed move-count bound; later swaps may revisit locations.

Players & information

One player; entire board and replenishment information available.

Randomness

Offline prescribed replenishment, not random unknown future gems.

The formal theorem establishes NP-hardness. This is not an expected-score claim about the commercial random game.

Exactly-one SAT · Positive 1-in-3 SAT

Source problem

Choose true variables so that every listed group contains exactly one true variable.

Exact question: Can truth values be assigned so exactly one variable is true in every positive clause of at most three variables?

Scale & input

A list of positive clauses, each containing at most three variables.

Move rules

Assign each variable true or false.

Goal

Exactly one true variable per clause.

Repetition

Not applicable.

Players & information

One solver; full formula.

Randomness

None.

This record defines the source problem used by the match-three reduction. Its source coverage is limited to the reduction paper and Schaefer’s bibliographic record and abstract; it carries no separate complexity classification.

Minesweeper · Can the clues all be true?

NP-complete

Check whether any placement of mines fits the revealed numbers.

Exact question: Does any placement of mines satisfy every revealed number on the supplied board?

Scale & input

Variable rectangular grid; partial clues.

Move rules

Clues count eight neighboring cells.

Goal

Some consistent mine placement exists.

Repetition

Static assignment.

Players & information

One reasoner; clues visible, mines unknown.

Randomness

None.

Not the problem of choosing a safe click.

Minesweeper · Is any covered cell certainly safe?

coNP-complete

A safe deduction must hold for every mine placement compatible with the clues.

Exact question: Is there a covered cell that is safe in every mine placement consistent with the revealed clues?

Scale & input

Variable rectangular partial board. Consistency of the revealed clues is not promised.

Move rules

Same eight-neighbor clues.

Goal

Some covered cell is safe in every completion.

Repetition

One deduction, no repeated play.

Players & information

Hidden mines; visible clues.

Randomness

No probabilities assumed.

If clues are inconsistent, every covered cell satisfies the universal safety condition vacuously: there are no fitting mine placements. The formal decision problem therefore differs from restricting input to consistent live-game boards. Uses the repaired 2024 inference proof.

Nonograms · Can the picture fit every clue?

NP-complete

Row and column clues jointly constrain a hidden picture.

Exact question: Does a black-and-white grid exist with exactly the supplied runs in every row and column?

Scale & input

Variable m × n grid and run-length clues.

Move rules

Fill cells black or white.

Goal

Every ordered run-length list matches.

Repetition

Static assignment.

Players & information

One solver; all clues given.

Randomness

None.

No uniqueness promise.

Klondike solitaire · Can every card reach a foundation?

NP-complete

Even knowing the covered cards does not make every scalable deal easy.

Exact question: Can a sequence of legal moves put every card of the supplied generalized Klondike deal onto the foundations?

Scale & input

Growing ranks and build stacks; three suits suffice.

Move rules

Alternating-color descending builds, ascending same-suit foundations; whole-block moves.

Goal

Move all cards to foundations.

Repetition

Finite successful certificate.

Players & information

One player; covered identities known.

Randomness

Deal supplied.

Specific no-stock/talon model; no return from foundations or empty-stack move. Not a claim about a fixed 52-card deck.

Mahjong solitaire · Can all matching tiles be removed?

NP-complete

Hardness already occurs with isolated stacks only three tiles high.

Exact question: Can all tiles in the supplied, fully revealed Mahjong-solitaire layout be removed in matching free pairs?

Scale & input

Unbounded tiles; four of each matching type.

Move rules

Remove two matching tiles that are uncovered and each have a free left or right side.

Goal

Empty the layout.

Repetition

Tiles only disappear.

Players & information

One player; peeking reveals every identity.

Randomness

Layout supplied.

Solitaire, not multiplayer Mahjong.

Mahjong solitaire · Isolated stacks at most two high

Polynomial-time solvable

With exactly four tiles of each type, these layouts are always solvable.

Exact question: Can all tiles be removed when the layout consists of isolated stacks at most two high, with four copies per type?

Scale & input

Growing layouts of isolated stacks of height at most two, with exactly four copies of every tile type.

Move rules

Remove two matching tiles that are uncovered and each have a free left or right side.

Goal

Remove everything.

Repetition

Monotone removal.

Players & information

One player; all identities known.

Randomness

None.

Four copies per type is essential to the stated always-solvable result.

Akari / Light Up · Can the whole board be lit?

NP-complete

Bulb placements can encode an entire Boolean circuit.

Exact question: Can lamps illuminate every white cell without shining on one another, while meeting every numbered adjacency clue?

Scale & input

Variable rectangle with black walls and numbered clues.

Move rules

Bulbs shine along rows/columns until walls; bulbs cannot see one another.

Goal

Light every white cell and satisfy adjacent-bulb counts.

Repetition

Static placement.

Players & information

One solver; full puzzle visible.

Randomness

None.

Counts are orthogonal neighbors, not all illuminated cells.

Akari / Light Up · Remove all numbered clues

Polynomial-time solvable

Every unnumbered layout can be completed by adding a bulb to an unlit cell until none remain.

Exact question: Can lamps illuminate every white cell without shining on one another when there are no numbered clues?

Scale & input

Growing grid; unnumbered black walls only.

Move rules

Same lighting and nonvisibility rules.

Goal

Illuminate all white cells.

Repetition

At most one new bulb per step.

Players & information

All cells known.

Randomness

None needed.

A primary undergraduate thesis; the short greedy proof is explicit.

Kakuro · Can the crossing sums be filled?

NP-complete

Hardness persists with at most four cells in every run.

Exact question: Can the blank cells be filled with allowed digits so every horizontal and vertical run has its specified sum, without repeats in a run?

Scale & input

Variable grid; digits remain 1–9; each run has a sum.

Move rules

Digits cannot repeat within a horizontal or vertical run.

Goal

Satisfy all sums and distinctness constraints.

Repetition

Static assignment.

Players & information

One solver; all clues supplied.

Randomness

None.

Fixed digit alphabet, growing board. No uniqueness promise.

Rubik's Cube · Find any solution

Polynomial-time search

A scalable, legally scrambled cube can be solved efficiently if the solution need not be shortest.

Exact question: Find a sequence of legal turns that solves the supplied reachable, generalized Rubik’s Cube configuration.

Scale & input

n × n × n cube, n grows; legal scramble promised.

Move rules

Rotate individual slices.

Goal

Restore solved face colors.

Repetition

Turns may be undone; no repetition ban.

Players & information

One player; all stickers known.

Randomness

None.

This is a search guarantee on valid scrambles, not a decision about arbitrary sticker colorings.

Rubik's Cube · Can it be solved within k turns?

NP-complete

Requiring the shortest route makes a different computational problem.

Exact question: Can the supplied generalized Rubik’s Cube configuration be solved in at most the given number k of turns?

Scale & input

Variable n × n × n cube plus k.

Move rules

One slice per move; slice-turn or slice-quarter-turn metric.

Goal

Reach solved colors using at most k moves.

Repetition

Revisits allowed.

Players & information

One player; complete configuration known.

Randomness

None.

Not the fixed 3 × 3 × 3 cube, and not whole-cube rotations as free slice moves.

Tetris · Know every upcoming piece

NP-complete

Seeing the whole piece sequence still leaves hard packing choices.

Exact question: Can the known sequence of pieces be placed to clear at least k rows without losing?

Scale & input

Growing rectangular board, initial filled cells, explicit finite piece sequence, row target k.

Move rules

Translate/rotate falling tetrominoes; complete rows clear.

Goal

Clear at least k rows without losing.

Repetition

Finite supplied sequence; no repeating history rule.

Players & information

One player; all future pieces visible.

Randomness

None.

Uses the paper's rotation models, not an assertion about every modern implementation or a fixed 10 × 20 board.

2048 · No new tiles appear

NP-complete

Even without new random tiles, reaching 2048 can encode satisfiability.

Exact question: Can a tile of value 2048 be formed from the supplied grid when no new tiles ever appear?

Scale & input

Arbitrary m × n board with given power-of-two tiles; target 2048.

Move rules

Slide all tiles in a chosen direction; matching tiles merge once per move.

Goal

Create a tile of value 2048.

Repetition

Revisits allowed; polynomial certificates established between merges.

Players & information

One player; whole board visible.

Randomness

No spawned tiles.

This is the no-new-tiles variant, not the ordinary random-spawn game on 4 × 4.

Peg solitaire · Can one peg remain at the target?

NP-complete

Removing pegs can simulate a planar logic circuit.

Exact question: Can legal peg jumps leave exactly one peg at the specified target position?

Scale & input

n × n board, initial pegs and a target hole; n grows.

Move rules

Jump orthogonally over an adjacent peg into an empty hole; remove jumped peg.

Goal

Exactly one peg remains at the designated hole.

Repetition

Every move removes a peg.

Players & information

One player; full board known.

Randomness

None.

Arbitrary generalized configurations; not just the standard 33-hole opening.

Nurikabe · Can islands fit in one connected sea?

NP-complete

Island sizes and a connected black region jointly impose hard constraints.

Exact question: Can the supplied clues be completed to islands of the required sizes, separated by one connected sea with no 2×2 sea block?

Scale & input

Growing numbered rectangular grid.

Move rules

White components each contain one clue equal to their size; black cells connected, with no black 2 × 2 block.

Goal

Complete the black/white coloring.

Repetition

Static assignment.

Players & information

One solver; visible clues.

Randomness

None.

Evidence is limited to the publisher abstract. This record does not include a construction sketch.

Nurikabe · Only clues 1 and 2

NP-complete

Tiny islands do not make the general problem easy.

Exact question: Does the same island-and-sea puzzle have a solution when every numerical clue is 1 or 2?

Scale & input

Same grid, with all clues restricted to 1 or 2.

Move rules

Same island and sea conditions.

Goal

Complete the coloring.

Repetition

Static.

Players & information

Complete clues.

Randomness

None.

Evidence is limited to the publisher abstract; no full-text proof is linked.

Slitherlink · Can one loop satisfy the numbers?

NP-complete

A single loop can encode a tour that visits every graph vertex.

Exact question: Can a single loop be drawn along grid edges so each numbered cell has exactly that many loop edges on its boundary?

Scale & input

Variable rectangular dot lattice; cells may have clues 0–3.

Move rules

Choose edges between neighboring dots; no branching or crossing.

Goal

One loop, with each clue counting its incident boundary edges.

Repetition

Static edge selection.

Players & information

One solver; every clue known.

Randomness

None.

No uniqueness promise.

Circuit satisfiability · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Given a Boolean circuit, is there an input making its output true?

Scale & input

Given a Boolean circuit, is there an input making its output true?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

3SAT · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Is a conjunction of clauses of three literals satisfiable?

Scale & input

Is a conjunction of clauses of three literals satisfiable?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Planar 3SAT · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Is the supplied 3CNF formula with planar variable-clause incidence structure satisfiable?

Scale & input

Satisfiability of a 3CNF formula with planar variable-clause incidence structure.

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

3-Partition · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Can the supplied 3s positive integers be partitioned into s triples with the same specified sum T?

Scale & input

Partition 3s positive integers into s triples all summing to T, with T/4 < a_i < T/2; unary instances suffice.

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Constraint graph satisfiability · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Can the supplied planar weighted AND/OR graph be oriented with incoming weight at least two at every vertex?

Scale & input

A planar graph of AND vertices with incident edge weights 1, 1, 2 and OR vertices with weights 2, 2, 2. Each vertex requires incoming weight at least two.

Move rules

Assign an orientation to every edge. This is a static existence problem with no move sequence.

Goal

Find an orientation satisfying the minimum incoming weight at every vertex.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Acyclic bounded constraint logic · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Can the target edge be reversed legally when each edge may reverse at most once?

Scale & input

An initially acyclic, legally oriented constraint graph using the AND, OR, FANOUT and CHOICE vertex types specified in Sections 1.1–1.3 of the cited paper. Edges have weights 1 or 2 and minimum incoming weight is two.

Move rules

Reverse one edge while maintaining incoming weight at least two at every vertex. Each edge may reverse at most once.

Goal

Reverse the designated target edge.

Repetition

An edge cannot be reversed again. Thus a move sequence has at most the number of edges.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Grid Hamiltonian cycle · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Does the supplied finite induced subgraph of the square lattice have a cycle visiting every vertex exactly once?

Scale & input

Does a finite induced subgraph of the square lattice have a cycle visiting every vertex exactly once? The cited Rubik source excludes degree-one vertices; those are trivially no-instances.

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Planar circuit satisfiability · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Is the designated output of a planar Boolean circuit made true by some input assignment?

Scale & input

Is the designated output of a planar Boolean circuit made true by some input assignment?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Planar Hamiltonian cycle · Reduction source

Reduction source

This is the exact source problem used by the linked construction. It is included to make the proof relationship explicit.

Exact question: Does a planar graph of maximum degree three have a Hamiltonian cycle?

Scale & input

Does a planar graph of maximum degree three have a Hamiltonian cycle?

Move rules

As specified in the cited reduction-source definition.

Goal

Answer the stated source question.

Repetition

Not a game rule unless explicitly part of the source definition.

Players & information

Explicit, fully known input. This is a proof-source problem.

Randomness

None.

This record identifies a reduction’s source problem; it does not provide a separate complexity classification.

Mastermind · Do the guesses fit any code?

NP-complete

Consistency is hard even with only two colors.

Exact question: Does at least one secret code produce every supplied guess rating?

Scale & input

Code length and explicit guess list grow. Two colors already suffice.

Move rules

Feedback gives correct positions and correct colors in wrong positions. Repeated colors allowed.

Goal

Find whether a compatible code exists.

Repetition

Static completion, no play-history restriction.

Players & information

Offline consistency problem. Guesses and ratings known, code hidden.

Randomness

None.

Not optimal adaptive codebreaking. In a truthful live game, consistency is already promised.

Flow Free / Numberlink · Connect every pair and cover every cell

NP-complete

Allowing paths to zigzag freely does not remove the hardness.

Exact question: Can pairwise disjoint paths join the terminal pairs and cover every cell?

Scale & input

Explicit n×n grid. The number of distinct terminal pairs grows.

Move rules

Orthogonal simple paths, one per pair. Every cell belongs to exactly one path.

Goal

Join all matching terminals and cover the grid.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

No minimum-turn rule. The claim is not about a fixed app level.

Lights Out · Can the target light pattern be reached?

P

Press order does not matter. A linear system records whether each light is pressed an odd or even number of times.

Exact question: Can presses transform the supplied initial pattern into the supplied target pattern?

Scale & input

Explicit finite undirected graph, including scalable rectangular grids, with initial and target bit patterns.

Move rules

A press toggles its vertex and all neighbors.

Goal

Reach the target pattern.

Repetition

Repeated presses allowed. Two presses at one vertex cancel.

Players & information

One player. Graph and both patterns known.

Randomness

None.

This P result is unrestricted reachability, not minimum presses on every graph family.

Battleships solitaire · Can the fleet fit the clues?

NP-complete

Ships and water encode Boolean choices.

Exact question: Does any fleet placement satisfy all supplied clues and row/column totals?

Scale & input

Growing rectangular grid, partial ship/water clues, totals and fleet. Ship lengths and fleet size may grow.

Move rules

Ships are straight, width one, horizontal or vertical. Distinct ships may not touch, even diagonally.

Goal

Place the full fleet and meet every clue.

Repetition

Static completion, no play-history restriction.

Players & information

One solver. All clues and constraints are known.

Randomness

None.

Solitaire logic puzzle, not the two-player hidden-fleet guessing game. General fleet, not a fixed commercial fleet.

Bloxorz · Reach the goal with switches and bridges

PSPACE-complete

Changing a 1×1×2 rolling block into a unit cube makes this reachability problem polynomial-time.

Exact question: Can the block legally reach the goal standing upright?

Scale & input

Explicit list of board tiles, start/goal, bridge states and one-to-one switch-to-bridge links.

Move rules

Roll/tilt a 1×1×2 block. Entering a switch toggles its bridge. All occupied cells must be supported.

Goal

Reach the goal upright.

Repetition

Revisits and repeated switch activation allowed.

Players & information

One player. Complete board state known.

Randomness

None.

Scalable levels with switches and bridges only. No splitting portals or weak tiles required.

UNO · Order all the cards

NP-complete

Matching colors or numbers is enough for NP-completeness in the scalable solitaire model.

Exact question: Decision: is there a legal ordering of every card?

Scale & input

An explicit multiset of cards with color and number labels. Card count and both label sets may grow.

Move rules

Discard one card matching the previous color or number. The first card is unrestricted. No action cards, draw pile or voluntary passes.

Goal

Play all cards.

Repetition

Discarded cards cannot return.

Players & information

One player, all cards known.

Randomness

None.

The result concerns a growing explicit input family, not a fixed commercial set.

UNO · Two players, visible hands

P

The corrected two-player model reduces to undirected vertex Geography.

Exact question: Decision: can the first player avoid being the first unable to play?

Scale & input

An explicit multiset of cards with color and number labels. Card count and both label sets may grow.

Move rules

Discard one card matching the previous color or number. The first card is unrestricted. No action cards, draw pile or voluntary passes.

Goal

Determine the first player unable to play, under optimal opposition, in the paper’s uncooperative model.

Repetition

Discarded cards cannot return.

Players & information

Two alternating players, both hands visible.

Randomness

None.

Simplified model, not commercial hidden-hand UNO. The authors explicitly withdrew their 2010 PSPACE-completeness claim.

Scrabble · Known bag order

PSPACE-complete

The result survives constant alphabet, dictionary and rack size in a derandomized model.

Exact question: Decision: can the designated player force a higher final score?

Scale & input

Growing n×n board, tile bag and given position. Alphabet, dictionary and rack size can be fixed constants for the two-player theorem.

Move rules

Place connected dictionary words horizontally or vertically. All letters score 1, no premium squares. Refill from the known bag order. No exchanges or passes in this model.

Goal

Higher score when the bag empties or the next player cannot form a legal word.

Repetition

Placed tiles never move or disappear.

Players & information

Two alternating players. Both racks and the entire bag order are known.

Randomness

None. The bag order is input.

Not a theorem about the fixed English-language commercial game or hidden random tile draws.

Scrabble · Place all the tiles

NP-complete

Removing the opponent gives the NP-complete solitaire placement task.

Exact question: Decision: can one player place every tile?

Scale & input

Growing n×n board and explicit tile sequence, dictionary, alphabet and rack size. Lemma 1 permits these parameters to grow.

Move rules

Place connected dictionary words horizontally or vertically. All letters score 1, no premium squares. Refill from the known bag order. No exchanges or passes in this model.

Goal

Place every tile.

Repetition

Placed tiles never move or disappear.

Players & information

One player, full board and tile order known.

Randomness

None. The bag order is input.

The result concerns a growing explicit input family, not a fixed commercial set.

TwixT · Connect opposite sides

PSPACE-complete

Each Hex cell can be represented by a 9×9 TwixT gadget.

Exact question: Decision: can the designated player force a connection?

Scale & input

An arbitrary input position on a growing rectangular grid, including colored pegs and links.

Move rules

Add one peg on a legal empty hole, avoiding the opponent’s border rows or columns. Link same-color pegs a knight’s move apart without crossing links. A player may remove their own links to add others. Pegs stay fixed.

Goal

Connect the player’s two opposite sides.

Repetition

Each turn adds a peg. Game length is bounded by board area.

Players & information

Two players, full information. Input positions are after any opening swap choice.

Randomness

None.

The result concerns a growing explicit input family, not a fixed commercial set.

Havannah · Ring, bridge or fork

PSPACE-complete

Ring threats simulate a walk through a Geography graph.

Exact question: Decision: can the designated player force a winning shape?

Scale & input

A given position on a hexagonal board of growing side length.

Move rules

Add one stone of the player’s color to an empty cell. Stones never move or get captured.

Goal

Make a ring enclosing a cell, connect two corners, or connect three sides. Corners do not count as sides.

Repetition

Every turn fills a new cell.

Players & information

Two players, full information. The input is a played position, not a claim about empty-board strategy.

Randomness

None.

The result concerns a growing explicit input family, not a fixed commercial set.

Kalah(6,4), fixed opening, empty-opposite capture allowed · Fixed 6×4 opening

Fixed board solved

The first player wins by 10 stones under the cited rules. This is a finite-board solution, not an asymptotic hardness classification.

Exact question: What is the optimal score from the Kalah(6,4) opening?

Scale & input

Exactly six pits per player, initially four stones each, and two empty stores.

Move rules

Sow counterclockwise from an own nonempty pit. Include your store, skip the opponent's store, and do not skip the starting pit on later laps. Ending in your store gives another move. Ending in an empty own pit captures that stone and the opposite pit, even when the opposite pit is empty.

Goal

When either side empties, the other player collects remaining stones. Maximize final score difference.

Repetition

Positions cannot repeat under these rules.

Players & information

Two players with fully known pit counts.

Randomness

None.

This paper does not classify the scalable winner problem. The empty-opposite capture convention matters.

Generalized Kalah winner, explicit m-pit rows and unary stone counts · Scalable board, unary counts

In PSPACE

This scalable winner problem is in PSPACE when the stone counts are unary. Every play has polynomially many sowing choices. This is an upper bound, not a hardness or completeness claim.

Exact question: From an explicitly supplied position, can the designated player force a strictly larger final store count?

Scale & input

An explicit board with m pits per player and two stores, a player to move, and nonnegative stone counts encoded in unary. The initial position may be arbitrary. Let S be the total number of stones, including stores.

Move rules

Choose a nonempty own pit and sow counterclockwise. Include your store, skip the opponent's store, and do not skip the source pit on later laps. A final stone in your store gives another choice. A final stone in an empty own pit captures that stone and the opposite pit, including when the opposite pit is empty.

Goal

When either side empties, collect the remaining stones into the other player's store. The designated player wins exactly when their final store is larger. A tie is not a win.

Repetition

No extra repetition restriction is required. The decreasing rank proved below bounds every play by mS(S+1)+S sowings.

Players & information

Two players with fully visible counts and deterministic optimal play. Consecutive moves by one player are allowed when the sowing ends in their store.

Randomness

None.

The citation supplies the rules, not a published PSPACE theorem. This bound does not prove PSPACE-hardness. The unary length assumption matters to this particular proof.

Jigsaw — Fit every piece? · Fit every piece?

NP-complete

Ambiguous tab-and-pocket matches make scalable assembly NP-complete.

Exact question: Can all supplied pieces assemble into the target square?

Scale & input

An explicit finite collection of n nearly square pieces and a target square. Shapes are encoded by finitely described matching types.

Move rules

Face-up orthogonal placement of tab-and-pocket pieces, matching shapes only. Use each supplied piece once.

Goal

Fill the target exactly, without overlap or gaps.

Repetition

Static completion problem. No move-history restriction.

Players & information

One solver, all input is visible.

Randomness

None.

This concerns scalable, potentially ambiguous piece sets, not the difficulty of a particular commercial picture puzzle.

Edge matching — Match every edge? · Match every edge?

NP-complete

Exact edge matching is NP-complete and converts to jigsaw assembly.

Exact question: Can all colored-edge tiles fill the target square?

Scale & input

n explicitly listed unit-square tiles, with four colors per tile and a square target of area n.

Move rules

Place tiles on the square grid. Adjacent edge colors must agree. Every tile is used exactly once.

Goal

Fill the target with compatible edges.

Repetition

Static completion problem. No move-history restriction.

Players & information

One solver, all input is visible.

Randomness

None.

The reduction forces tile orientations. Difficulty does not rely on image recognition.

Polyomino packing — Pack every piece? · Pack every piece?

NP-complete

Even pieces fitting in O(log n) by O(log n) boxes can encode hard jigsaw puzzles.

Exact question: Can the supplied polyominoes exactly tile the square?

Scale & input

n finite grid-cell shapes and a square target whose area equals their total area.

Move rules

Orthogonal placements of all supplied pieces, without overlap.

Goal

Cover every target cell exactly once.

Repetition

Static completion problem. No move-history restriction.

Players & information

One solver, all input is visible.

Randomness

None.

A fixed catalog of shapes is a different restriction from the variable piece sets here.

Hanabi — Known-deck solitaire · Known-deck solitaire

NP-complete

Hardness survives a hand of two cards and at most two copies of each card.

Exact question: Can one player complete every color sequence?

Scale & input

Explicit ordered deck, scalable number of colors and values. Hand capacity h=2 and multiplicity at most 2 suffice.

Move rules

Scan the known deck. Play, discard or store each card. Play each color in increasing order without skipping numbers.

Goal

Play values 1 through n in every color.

Repetition

The finite deck is processed once. Discards are permanent.

Players & information

One player with full knowledge of every card and draw order.

Randomness

None. The order is input, not a fresh random draw.

This is the paper’s solitaire planning model, not an exact classification of normal hidden-hand multiplayer Hanabi.

Pandemic — Known-draw planning · Known-draw planning

NP-complete

Planning is NP-complete on scalable maps even with one player.

Exact question: Can the team find every cure before losing?

Scale & input

An explicit city graph, player positions, hands, infections, and all future player/infection draws, including reshuffles.

Move rules

Four actions per turn: movement/flights, build, share, cure, or treat. Seven-card hand limit. Cure uses five matching-color city cards at a lab. Draw two player cards per turn.

Goal

Find all cures before eight outbreaks or player-deck exhaustion.

Repetition

At most |V|/2+3 turns under the specified deck rules.

Players & information

Cooperative players, with all future card outcomes supplied.

Randomness

Draw and reshuffle outcomes are fixed input.

Does not classify optimal play with genuinely unknown future draws.

Backgammon — Known rolls & opponent · Known rolls & opponent

NP-hard

Even with those future choices disclosed, finding a winning play is NP-hard.

Exact question: Can you win against this prescribed opponent and roll sequence?

Scale & input

Explicit scalable line of points and polynomially many checkers. Six home points per side and two six-sided dice suffice. Input includes the prescribed future rolls and opponent policy.

Move rules

Move according to both dice, doubles four times. Two opposing checkers block a point. A hit checker must re-enter before others move.

Goal

Bear off every checker first.

Repetition

Captures permit arbitrarily long play. No fixed turn limit is assumed.

Players & information

Two players, with the opponent’s complete policy revealed in this task.

Randomness

Both players’ future rolls are supplied, using the paper’s compact descriptions.

Hardness only. This is neither a fixed 24-point board nor expected win probability under fair random dice.

Magic: The Gathering — Forced endgame outcome · Forced endgame outcome

Undecidable

A forced game encodes a Turing machine and wins exactly when the machine halts.

Exact question: Will the designated player win this forced endgame?

Scale & input

A finite described reachable game state, using the paper’s card pool and rules. Standard-sized decks suffice, while counters and generated tokens have no fixed cap.

Move rules

All remaining actions are forced. Tokens, triggered effects and counters simulate a tape and transition rules. Numeric choices use binary notation.

Goal

Reach the designated player’s winning effect.

Repetition

Nonhalting simulation yields an unavoidable infinite loop, treated as a draw by the cited rule.

Players & information

Two players, no remaining strategic choices and no relevant hidden information.

Randomness

No stochasticity is used in the construction.

This does not model finite physical memory or tournament clocks, and it freezes the paper’s rules/card text instead of asserting compatibility with every later rules update.

Domineering — Winner from a position? · Winner from a position?

In PSPACE

Polynomial-space search follows from the move bound. Exact complexity is open in the cited source.

Exact question: Can the player to move force a win?

Scale & input

A finite grid-cell board supplied explicitly, possibly with unavailable cells, plus the player to move.

Move rules

One player places vertical dominoes and the other horizontal dominoes. Occupied cells cannot be reused.

Goal

Make the last legal move.

Repetition

Every move consumes two empty cells, so play has at most N/2 moves.

Players & information

Two players, deterministic perfect information.

Randomness

None.

The 2026 graph-generalization results do not automatically settle domino placement on a grid.

Chomp — Winner on a full rectangle? · Winner on a full rectangle?

Polynomial time

Every rectangle with more than one square is a first-player win by strategy stealing.

Exact question: Who wins from a complete rectangular chocolate bar?

Scale & input

Positive dimensions m,n given in binary or unary, describing a full rectangle.

Move rules

Choose a remaining square and remove it and every square up and to its right. The lower-left square is poisoned.

Goal

Make the opponent take the poison.

Repetition

Each move removes at least one square.

Players & information

Two players, perfect information.

Randomness

None.

This decides the winner. The proof does not provide an efficient winning first move. The 1×1 board is losing.

Ask for a short solution

Task change

Sliding tiles: Any solution? — Sliding tiles: At most k slides?

Reachability is polynomial-time solvable. Requiring at most k single-tile slides is NP-complete. The move rules and board family stay the same.

1. Any solution: decide whether the target arrangement can be reached at all. Parity characterizes reachability, and a solution can be constructed in polynomial time.
2. Short solution: decide whether there is a route using at most k slides. A fast reachability check does not answer this budget question.
3. This dashed connection compares computational tasks. It is not a displayed hardness reduction.

A short network becomes a short solution

Proved polynomial-time reduction

Steiner tree: Short connecting tree? → Sliding tiles: At most k slides?

Scale terminal coordinates; cycle three target tiles at each terminal; a short blank tour corresponds to a short connecting tree.

1. Start from integer-coordinate terminals and a tree-length bound ℓ. The proof uses the strongly NP-hard restriction, so the explicit output board has polynomial size.
2. Scale the terminal locations by c = 18|P|. At each non-root terminal, cycle three nearby target tiles while keeping the blank anchored at the root.
3. A walk of the blank can make the local rotations. The reduction uses k = (2ℓ + 1)c. Its two directions relate a short solution to a short connecting rectilinear tree.

One edge or the entire orientation

Task change

Constraint logic: Reverse one edge? — Constraint logic: Reach a full target?

Both are complete for PSPACE, but they are separate reachability tasks. Their use in a reduction must be specified.

1. The first question asks whether one designated arrow can be reversed. The second asks whether the whole graph can reach a prescribed orientation.
2. Both are PSPACE-complete, but their instance formats and targets differ. The displayed puzzle reductions name the version they actually use.

Cars simulate constraints

Proved polynomial-time reduction

Constraint logic: Reverse one edge? → Rush Hour: Can the car escape?

AND and protected-OR arrangements of cars simulate legal edge reversals. The target edge releases an exit car.

1. Start from planar AND/OR edge-reversal reachability, with the protected-OR restriction used by the gadgets.
2. Replace graph constraints with car arrangements. An AND gadget can release its output only after both inputs retract. An OR gadget permits either of its allowed inputs.
3. Connecting the gadgets makes the designated edge reversal correspond to reaching the target car’s border position. See the complete car layouts in Figure 14.

Crates encode edge orientations

Proved polynomial-time reduction

Constraint logic: Reach a full target? → Sokoban: Crates onto targets?

Crate gadgets simulate graph constraints; targets encode the final orientation. Irrecoverable pushes lead away from any solution.

1. Start from constraint-logic configuration-to-configuration reachability. The goal describes every target arrow.
2. Crate arrangements encode constraint ports, and target squares encode the final orientation. Packed crates provide barriers even though no separate fixed barrier pieces are supplied.
3. The proof rules out cheating pushes by showing that they make the target impossible to reach. The sketch does not assert that all crate pushes are reversible.

A scaffold preserves completions

Proved polynomial-time reduction

Latin squares: Complete rows & columns → Sudoku: Does a completion exist?

A fixed Sudoku scaffold leaves selected cells free. Their high base-n digits encode the Latin square; low digits are forced. Completions correspond one-to-one.

1. Begin with a partial Latin square of order n. Build an n²×n² Sudoku with n×n boxes.
2. A fixed scaffold leaves selected cells free in the top band. The encoded symbols correspond to the Latin symbols.
3. Each Latin completion gives exactly one Sudoku completion and vice versa. This is a parsimonious reduction, not merely a resemblance between grids.

Choices become paths

Proved polynomial-time reduction

Quantified logic: Can you force true? → Geography: Arrows · no vertex reuse

A polynomial construction turns formula truth into optimal-play winner determination.

1. Variable diamonds encode truth choices. After those choices, the universal player selects a clause and the existential player selects a literal. Links back to visited vertices test whether that literal satisfies the clause.

Allow travel both ways

Rule change

Geography: Arrows · no vertex reuse — Geography: Two-way · no vertex reuse

Keeping the no-vertex-revisit rule while allowing undirected movement changes a PSPACE-complete problem to a polynomial-time one.

1. This compares two rulesets. Removing arrowheads is not claimed to preserve a position's winner or to be a reduction.

Use up edges, not vertices

Rule change

Geography: Two-way · no vertex reuse — Geography: Two-way · no edge reuse

Allowing vertex revisits while deleting used edges changes the winner problem from polynomial-time solvable to PSPACE-complete.

1. After traversing a→b, the vertex version removes a and its incident edges. The edge version removes only ab. These are different games, not a winner-preserving transformation.

Logic becomes a connection game

Proved polynomial-time reduction

Quantified logic: Can you force true? → Hex: From a given position

Quantified formula truth reduces in polynomial time to winning from a supplied Hex position.

1. The proof first builds a planar graph-Hex instance. Its links and degree-three unplayed vertices are represented on a partly filled Hex board. Preset stones restrict the remaining connection choices.

Require an empty starting board

Restriction of inputs, moves or resources

Hex: From an empty board — Hex: From a given position

Empty n×n boards always have a first-player win. Arbitrary supplied positions have a PSPACE-complete winner problem.

1. The allowed input positions change; the placement and winning rules do not. The easy yes/no answer on empty boards does not produce the winning moves.

Logical choices become reversible moves

Proved polynomial-time reduction

Quantified logic: Can you force true? → Constraint logic: Reverse one edge?

Quantified CNF truth reduces to reversing one designated edge in a planar protected-OR constraint graph. This connects game proofs to sliding-puzzle proofs.

1. Start from the quantified-CNF restriction of the formula problem. Quantifier gadgets provide literal signals to a circuit for the formula.
2. Existential gadgets can choose a successful assignment. Universal gadgets use a latch to require success under both assignments; the designated output edge can reverse exactly when the formula is true.
3. Crossover gadgets make the graph planar, then OR replacement gives protected-OR vertices. Protection is a global invariant: two specified incident edges cannot both point inward. It is not an extra move rule.

Keep directions, remove crossings

Restriction of inputs, moves or resources

Geography: Sparse planar directed graph — Geography: Arrows · no vertex reuse

A restriction of directed vertex Geography that is still PSPACE-complete.

1. Only planar, bipartite, degree-three graphs are allowed.
2. The token still cannot revisit a vertex.

Choices become a route

Proved polynomial-time reduction

Quantified logic: Can you force true? → Geography: Sparse planar directed graph

Variable choices and clause checks become graph paths. Crossover gadgets make the graph planar.

1. Encode truth choices by alternative paths.
2. A clause-check path tests the earlier choices.
3. Replace crossings without changing the winner.

Paths become an escape route

Proved polynomial-time reduction

Geography: Sparse planar directed graph → Go: Ko-free hardness construction

A large white group must navigate pipes and junctions to reach safety.

1. Represent arcs by narrow corridors.
2. Junctions let the appropriate player choose.
3. Saving the group or capturing it decides the score.

A graph hidden in disk flips

Proved polynomial-time reduction

Geography: Sparse planar directed graph → Othello: Who can win?

The Othello construction accepts bipartite degree-three Geography, including this planar restriction.

1. Encode each vertex with disk-flipping gadgets.
2. Connect exits to entries along rows of disks.
3. Deviating from the simulation concedes a decisive scoring region.

Variable choices become box chains

Proved polynomial-time reduction

Formula game: Choose which variable to claim → Dots & Boxes: More boxes than your opponent?

Choices in the formula game determine signals and the final box score.

1. Claim a variable gadget.
2. Propagate the value through wires and OR gadgets.
3. Clause gadgets and the initial score make formula truth decide victory.

A true formula opens territory

Proved polynomial-time reduction

Formula game: Choose which variable to claim → Amazons: Last player able to move?

Amazons acting as wires and gates open a large region only when the formula becomes true.

1. The first player reaching a variable enables or blocks its signal.
2. Wire and gate gadgets evaluate the clauses.
3. Opening the final room provides enough moves to win.

Quantified choices become a hive

Proved polynomial-time reduction

Quantified logic: Can you force true? → Hive: Generalized, multiple queens

The paper composes Formula Game → Formula Game Geography → n-Hive.

1. A route chooses variable values, then checks a clause.
2. Connected hexagonal pieces implement the route.
3. Surrounding a queen records the outcome.

Make the last move lose

Rule / task change

Nim: Take the last counter — Nim: Avoid the last counter

Changing the winner changes the strategy near the end; both variants remain polynomial-time solvable.

1. Keep every legal move.
2. Reverse who wins on the last counter.
3. Switch from XOR to parity when only singleton heaps remain.

Turn opponents into partners

Rule / task change

Checkers: Every turn must capture — Checkers: Work together

Keep the capture-only moves, but ask whether a successful joint sequence exists.

1. Competitive: a strategy must defeat every opposing choice.
2. Cooperative: both sides choose a successful sequence.

Walls become truth values

Proved polynomial-time reduction

Formula game: Choose which variable to claim → Quoridor: Reach the far side first

A vertical or horizontal wall in a small gate records which player claimed a variable.

1. Each variable has a gate accepting one of two wall orientations.
2. The opponent chooses a clause; White chooses one of its variables.
3. An open gate yields an escape route fast enough to win the race.

Quantifiers become reusable doors

Proved polynomial-time reduction

Quantified logic: Can you force true? → Super Mario Bros.: Persistent level state

The quantified-formula framework is implemented by Spinies that block one passage or another.

1. Represent each door state by the tunnel containing a Spiny.
2. Hit the supporting brick to move it between tunnels.
3. Wire door and crossover gadgets into the quantified-formula construction.

What the level remembers matters

Rule / task change

Super Mario Bros.: Bounded screen, off-screen reset — Super Mario Bros.: Persistent level state

Bounded-screen reset gives P for explicit levels. Persistent off-screen state supports PSPACE-completeness. This compares two engine models, not a reduction.

1. Reset model forgets state sufficiently far off-screen.
2. Persistent model remembers every monster position.
3. The difference permits many independent door states.

Tires store door states

Proved polynomial-time reduction

Quantified logic: Can you force true? → Donkey Kong Country: Generalized stage reachability

The quantified-formula construction uses tires, slopes and Zingers to implement doors.

1. A tire low on the slope blocks safe traversal.
2. Push it up to open the route.
3. A different path rolls it down again to close the route.

Truth choices prepare hookshot targets

Proved polynomial-time reduction

3SAT: Reduction source → The Legend of Zelda: A Link to the Past: hookshot puzzles

Choosing a route pushes blocks into place. A final check path crosses each clause only if a suitable block was moved.

1. A branch chooses a variable value.
2. Selected literal corridors push blocks for their clauses.
3. The check path needs one reachable hookshot target per clause.

Switches implement reusable logic

Proved polynomial-time reduction

Quantified logic: Can you force true? → The Legend of Zelda: A Link to the Past: doors and switches

Persistent gates and teleporters implement the quantified-formula door framework.

1. Initialize complementary gate states.
2. An open or close traversal toggles the relevant floor switches.
3. A check corridor is passable exactly in the open state.

From prepared crossings to reusable switches

Rule / task change

The Legend of Zelda: A Link to the Past: hookshot puzzles — The Legend of Zelda: A Link to the Past: doors and switches

These results use different dungeon mechanics: permanent block preparation versus repeatedly switchable gates.

1. Inspect the hookshot-only construction.
2. Add the persistent door-state model for the second result.
3. The labels are known bounds for their stated models, not a proved strict complexity separation.

Clear the monsters before the final pass

Proved polynomial-time reduction

3SAT: Reduction source → Metroid: Generalized Morph Ball levels

Literal routes let Samus clear a clause obstacle from below before attempting it in Morph Ball mode.

1. Choose one route for each truth value.
2. Use that route to shoot the corresponding clause enemies.
3. Check all clauses along a route where Morph Ball cannot shoot.

Trainer sight lines simulate clauses

Proved polynomial-time reduction

3SAT: Reduction source → Pokémon: Trainer-only route planning

Defeating a weak trainer freezes its position. Unwanted encounters with strong trainers then enforce the logical choices.

1. Use trainers that are certain wins or certain losses.
2. Earlier literal visits disable selected weak guards.
3. Later passage is safe exactly when the clause was enabled.

A staircase becomes a door

Proved polynomial-time reduction

Quantified logic: Can you force true? → Lemmings: Save one lemming with two skills

Build to close a passage and bash to reopen it, implementing the quantified-formula door framework.

1. Steel and deadly zones constrain the possible paths.
2. A Builder action creates a blocking stair segment.
3. A Basher action removes it so the traverse path is safe.

Bound the available commands

Rule / task change

Lemmings: Save one lemming with two skills — Lemmings: Polynomial building and digging budgets

Unlimited or exponential Builder/Basher budgets support the PSPACE construction. Polynomial Builder/Basher/Miner budgets yield membership in NP in the broader skill model.

1. Terrain changes become polynomially bounded.
2. Long waits are encoded by timestamps.
3. Verify the resulting plan without simulating every waiting frame.

A cube on a button is a memory bit

Proved polynomial-time reduction

Constraint logic: Reverse one edge? → Portal: Cubes, floor buttons and doors

Rooms containing one cube and two floor buttons realize NCL-controlled switches.

1. Each switch room has two possible cube positions.
2. The two buttons control complementary sets of doors.
3. The room exit requires a button to remain pressed, enforcing a valid switch state.

Timers and stored switch states

Rule / task change

Portal: Timed buttons and doors — Portal: Cubes, floor buttons and doors

Timed-door reachability is NP-hard. Reusable cube/button switches yield a PSPACE-complete model. These are different allowed-mechanic sets.

1. Timers constrain the length of a successful tour.
2. Cube positions persist until the player changes them.
3. The second construction can revisit and update many switches.

Falling columns check exactly one

Proved polynomial-time reduction

Exactly-one SAT: Positive 1-in-3 SAT → Candy Crush / Bejeweled: Offline target-gem problem

The player activates or skips one choice wire per variable. Column offsets align a final cascade only when each clause has exactly one true variable.

1. Rows implement variable choices.
2. Clause columns drop by offsets determined by those choices.
3. Exactly-one choices align the final goal wire with the designated gem.

Possible versus guaranteed

Rule / task change

Minesweeper: Can the clues all be true? — Minesweeper: Is any covered cell certainly safe?

Same clues, different quantifier: does some placement work, or is some cell safe in all placements?

Orientations become black squares

Proved polynomial-time reduction

Constraint graph satisfiability: Reduction source → Nonograms: Can the picture fit every clue?

AND/OR constraints become clue gadgets joined by grid wires.

1. Embed the planar graph.
2. Replace vertices with clue gadgets.
3. Legal orientations correspond to completions.

Cards become keys and locks

Proved polynomial-time reduction

Acyclic bounded constraint logic: Reduction source → Klondike solitaire: Can every card reach a foundation?

Exposing key cards permits lock cards to move, simulating edge reversals.

A third layer changes the problem

Restriction of inputs, moves or resources

Mahjong solitaire: Isolated stacks at most two high — Mahjong solitaire: Can all matching tiles be removed?

Two-high isolated stacks are always solvable; three-high stacks already encode 3SAT.

Matching choices encode truth assignments

Proved polynomial-time reduction

3SAT: Reduction source → Mahjong solitaire: Can all matching tiles be removed?

Tile groups enforce variable choices and clause satisfaction.

Numbers create the difficulty

Restriction of inputs, moves or resources

Akari / Light Up: Remove all numbered clues — Akari / Light Up: Can the whole board be lit?

Unnumbered walls retain lighting constraints, but permit a greedy solution.

A light puzzle can carry logic

Proved polynomial-time reduction

Circuit satisfiability: Reduction source → Akari / Light Up: Can the whole board be lit?

Two bulb placements represent a Boolean signal; wires, NOT and OR gadgets preserve it.

1. Choose input bulb patterns.
2. Propagate them through lighting gadgets.
3. Force the output pattern to true.

Crossing sums become circuit wires

Proved polynomial-time reduction

Planar 3SAT: Reduction source → Kakuro: Can the crossing sums be filled?

Alternating 1s and 2s carry bits through arithmetic gadgets.

1. Select the two-state input patterns.
2. Join wire and gate interfaces.
3. Require every clause gadget to admit a filling.

Solving versus solving optimally

Rule / task change

Rubik's Cube: Find any solution — Rubik's Cube: Can it be solved within k turns?

An efficient way to solve a scrambled cube need not find the fewest turns.

A shortest tour becomes a shortest scramble

Proved polynomial-time reduction

Grid Hamiltonian cycle: Reduction source → Rubik's Cube: Can it be solved within k turns?

The construction encodes graph paths as cube transformations whose moves cancel in the right order.

1. Encode grid Hamiltonicity as promised bitstrings.
2. Turn bitstrings into slice transformations.
3. A short solution exists exactly when the source has its required tour.

Equal-sum triples become equal-height stacks

Proved polynomial-time reduction

3-Partition: Reduction source → Tetris: Know every upcoming piece

Each integer becomes a piece sequence that must fit one bucket. Clearing succeeds when buckets balance.

1. Make one bucket for each triple.
2. Encode numbers as indivisible piece sequences.
3. Balanced buckets unlock the final clearing sequence.

Left or right chooses a truth value

Proved polynomial-time reduction

3SAT: Reduction source → 2048: No new tiles appear

Controlled merges activate clause gadgets; the final target merge requires all clauses.

1. Choose left/right for each variable.
2. Use those shifts to activate its clauses.
3. Merge the target only after every clause is satisfied.

A peg can carry a Boolean signal

Proved polynomial-time reduction

Planar circuit satisfiability: Reduction source → Peg solitaire: Can one peg remain at the target?

Jump patterns realize circuit gates; cleanup leaves the target peg only for a satisfying input.

Hard even with tiny islands

Restriction of inputs, moves or resources

Nurikabe: Only clues 1 and 2 — Nurikabe: Can islands fit in one connected sea?

Restrict every numbered island to size one or two.

A graph tour becomes the puzzle loop

Proved polynomial-time reduction

Planar Hamiltonian cycle: Reduction source → Slitherlink: Can one loop satisfy the numbers?

Embed a degree-at-most-three planar graph, then replace vertices and connections with loop gadgets.

1. Lay the graph on a grid.
2. Force required vertex visits with clue gadgets.
3. The single puzzle loop corresponds to a Hamiltonian cycle.

Truth values become code positions

Proved polynomial-time reduction

3SAT: Reduction source → Mastermind: Do the guesses fit any code?

The construction preserves the number of solutions.

1. Two positions encode each variable and its negation.
2. Feedback forces exactly one of those positions to represent true.
3. Clause queries and auxiliary positions enforce satisfaction with a unique completion.

Variable routes block false clause choices

Proved polynomial-time reduction

3SAT: Reduction source → Flow Free / Numberlink: Connect every pair and cover every cell

A path chooses a truth value and blocks incompatible literal routes.

1. Each variable selects one of two routes.
2. Each clause needs an unblocked route for one of its literals.
3. Paired terminals and crossover gadgets fill every remaining cell without permitting crossings.

Fleet placements encode assignments

Proved polynomial-time reduction

3SAT: Reduction source → Battleships solitaire: Can the fleet fit the clues?

The reduction preserves the number of solutions.

1. A ship placement selects a truth value.
2. Column totals make each variable choice consistent across occurrences.
3. Clause regions can be completed exactly when at least one literal is true.

Switches simulate constraint-logic edges

Proved polynomial-time reduction

Constraint logic: Reverse one edge? → Bloxorz: Reach the goal with switches and bridges

The AND/OR constraints control which simulated edge may reverse.

1. Bridge states store the orientation of each source edge.
2. Traversing an edge gadget changes its orientation.
3. Vertex gadgets allow this only while the source inflow constraint remains satisfied.

Turn matching cards into a walk

Proved polynomial-time reduction

UNO: Two players, visible hands → Geography: Two-way · no vertex reuse

Create a vertex for each card and connect matching cards held by opposite players.

1. Cards become graph vertices.
2. Opposite-hand cards share an edge exactly when their color or number matches. For the unrestricted first discard, add a start vertex joined to player 1’s cards.
3. Discarding cards follows an undirected walk without revisiting a vertex. Use the polynomial-time Geography winner algorithm.

One hand or competing hands?

Player and task change

UNO: Order all the cards — UNO: Two players, visible hands

The task and turn rules change. This is not a hardness reduction.

1. Solitaire asks whether every card can be ordered.
2. The two-player version alternates between visible hands and asks who gets stuck.

Words encode truth choices

Proved polynomial-time reduction

Quantified logic: Can you force true? → Scrabble: Known bag order

Alternating word choices assign variables. Later plays check the clauses.

1. Horizontal routes encode alternating truth choices.
2. Vertical routes test the clauses against those choices.
3. The prescribed tile order and dictionary enforce the simulation.

A tile sequence checks a formula

Proved polynomial-time reduction

3SAT: Reduction source → Scrabble: Place all the tiles

One player chooses the truth values and must finish every clause test.

1. Variable gadgets select a consistent assignment.
2. Each clause requires a word placed at a satisfied literal.
3. All tiles can be placed exactly when the formula is satisfiable.

Remove the opponent

Player and task change

Scrabble: Known bag order — Scrabble: Place all the tiles

Compare score competition with placing every tile alone.

1. Known tile order in both models.
2. The winning condition changes from score competition to placing all tiles.

Replace a Hex cell with pegs

Proved polynomial-time reduction

Hex: From a given position → TwixT: Connect opposite sides

A 9×9 cell gadget preserves each player’s connection options.

1. Use the empty, white and black cell gadgets from Figure 4.
2. Tile the gadgets in the adjacency pattern of the input Hex board.
3. Dominating moves inside each gadget preserve the winning player.

Follow a chain of ring threats

Proved polynomial-time reduction

Geography: Sparse planar directed graph → Havannah: Ring, bridge or fork

Wires and vertex gadgets simulate planar directed Geography using forced defensive moves.

1. Begin with planar bipartite directed Geography of total degree at most 3.
2. Replace vertices and arcs by chains of ring threats and choices.
3. Gadgets lie far from the border so bridge and fork wins cannot disrupt the simulation.

Fix the opening and compute its score

Input and task change

Kalah: Fixed 6×4 opening — Kalah: Scalable board, unary counts

Fixing the board and opening removes the scalable input. This comparison also changes the requested output from a winner decision to the optimal score.

1. Restrict m to 6 and every initial pit count to 4, with empty stores and South to move.
2. This leaves a single finite opening whose optimal score was computed. It does not establish an asymptotic lower bound.
3. The fixed record reports optimal score, while the scalable record asks only whether a designated player can force a win. This is an input and task comparison, not a proved reduction or a pure input restriction.

Turn numbers into tile runs

Proved polynomial-time reduction

3-Partition: Reduction source → Edge matching: Match every edge?

A forced frame and horizontal tile runs simulate equal-sum bins.

1. Encode each number as a forced run of tiles.
2. Use a frame to enforce row capacities.
3. A filling chooses the required partition.

Colors become matching tabs

Proved polynomial-time reduction

Edge matching: Match every edge? → Jigsaw: Fit every piece?

First encode each unsigned tile by four signed tiles, then turn signs into tabs and pockets.

1. Replace one colored-edge tile by a forced 2×2 signed supertile.
2. Encode positive and negative signs as matching tab/pocket shapes.
3. Flat edges enforce the outer boundary.

Tabs become binary bumps

Proved polynomial-time reduction

Jigsaw: Fit every piece? → Polyomino packing: Pack every piece?

Each tab shape becomes a short binary pattern of grid-cell bumps.

1. Assign each matching shape a binary code.
2. Put complementary bump patterns on neighboring edges.
3. Only the intended matching pieces fit seamlessly.

Pieces become tile assemblies

Proved polynomial-time reduction

Polyomino packing: Pack every piece? → Edge matching: Match every edge?

Unique internal colors force the small tiles to reassemble each input piece.

1. Replace every polyomino cell by an edge-colored tile.
2. Use private internal colors to force each piece.
3. Allow compatible external edges between assembled pieces.

Two saved cards encode choices

Proved polynomial-time reduction

3SAT: Reduction source → Hanabi: Known-deck solitaire

Variable gadgets select which color advances, and clause gadgets test whether a choice satisfies each clause.

1. Pair colors to represent true and false.
2. A two-card storage limit forces a variable choice.
3. Each clause allows all colors to advance only if a literal is satisfied.

Treat every city before time runs out

Proved polynomial-time reduction

Grid Hamiltonian cycle: Reduction source → Pandemic: Known-draw planning

Apply the paper’s Hamiltonian-cycle construction to a grid-graph input.

1. Replace each input vertex by a city gadget about to outbreak.
2. Set draws so an unvisited gadget causes the final losing outbreak.
3. Returning to the cure lab in time requires visiting every gadget.

Protect every clause checker

Proved polynomial-time reduction

3SAT: Reduction source → Backgammon: Known rolls & opponent

A literal choice sends checkers to protect clause positions.

1. Choose the true or false route for each variable.
2. Chosen literals cover the corresponding clause checker.
3. An uncovered clause lets the prescribed opponent capture and trap a checker.