# Games Are Hard

Also known as Complexity of Games and Puzzles. Original title was NP-completeness. Most likely will be more up-to-date on my other site.

I love puzzles and games so much. I also enjoy theoretical computer science. Of course this had to be done. Here’s a list of everything I’ve found. This page will (hopefully) be updated every time I get a new thing. Contributions welcome.

### Notes

• In a conversation with Sebastian Schoener, I realized that there is a difference between satisfiability/consistency problems and uniqueness/soundness problems. For certain games/puzzles, there are two questions that make sense: whether a given instance of a puzzle has at least one solution (it is satisfiable/consistent), and whether it has at most one solution (it is sound). We can generalize the soundness problem: given an instance of a partially-solved puzzle, whether there exists “anything” that can be deduced (the contents of a cell, etc).

Soundness matters. For example, if you’re stuck in Minesweeper (it allows no progress; nothing can be deduced), you must guess, which is obviously bad. Likewise, if you’re doing a puzzle competition, and you can’t deduce anything, it means the puzzle has multiple solutions, and so you must guess the solution intended by the author, which is also bad.

In most cases, the more natural problem is satisfiability/consistency; we’re concerned whether there exists at least one solution. However, there are some specific cases in which the soundness problem is more natural instead, for example Minesweeper. I’ve marked (hopefully) everything where consistency and soundness can matter with whether they are about consistency or about soundness.

• This that states several papers showing that Country Road, Ripple Effect, Shikaku, and Yajilin are NP-complete. Anyone knows whether the papers are available online?

### Last updated 06-Jun-2016

Puzzles and games that are proven to be in some class, along with what reduces to them…

## NP-complete

• Akari (satisfiability) from 3-SAT
• Battleships (satisfiability) from 3-SAT, from bin packing
• Bejeweled (whether a given gem can be popped) from 1-in-3 SAT
• Corral (satisfiability) from 3-colorability of planar graphs
• Cryptarithms (Verbal Arithmetic) (satisfiability) from 3-SAT
• Fillomino (satisfiability) from 3-SAT
• Galaxies (satisfiability) from 3-SAT
• Hashi(wokakero) (satisfiability) from existence of Hamiltonian circuits in unit-distance graphs
• Heyawake (satisfiability) from 3-SAT
• Kakuro (satisfiability) from 3-SAT
• KenKen (TomTom) (satisfiability) from Latin Square
• Kurodoko (satisfiability) from 3-SAT
• Latin Square (satisfiability) from triangulation of tripartite graphs
• Lemmings (satisfiability) from 3-SAT
• Mastermind (satisfiability) from vertex cover
• Masyu (satisfiability) from existence of Hamiltonian circuits in cubic graphs
• Minesweeper (satisfiability) from 3-SAT
• Nonogram (satisfiability) from Nondeterministic Constraint Logic
• Nurikabe (satisfiability) from 3-SAT
• Patterna (satisfiability) from 3-SAT
• Ripple Effect (satisfiability) from 3-SAT, Latin Square
• Slitherlink (satisfiability) from existence of Hamiltonian circuits in cubic graphs
• Solitaire Chess (satisfiability) from 3-SAT
• Sudoku (satisfiability) from Latin Square
• Super Mario Bros (whether one can reach a target point) from 3-SAT
• Tetris (whether one can survive over a known finite sequence of pieces) from 3-partition
• TrackMania (whether one can finish the lap) from 3-SAT
• Zen Puzzle Garden (satisfiability) from existence of Hamiltonian circuits in cubic graphs

## PSPACE-complete

• 2048 (reaching target configuration) from Nondeterministic Constraint Logic
• Bloxorz from Nondeterministic Constraint Logic
• Sokoban from simulating linear bounded automata

## PSPACE-hard

• Pokémon (whether one can reach a target point) from Sokoban

## Undecidable

• Braid (whether one can reach a target point) from simulating counter machine

## 8 thoughts on “Games Are Hard”

1. edderiofer says:

How about games that have been proven to be some order of complexity other than NP? There’s this paper that proves that Braid is undecidable, for example. http://arxiv.org/abs/1412.0784

• @Braid: Woah.

@Other complexity: If I find a large enough collection of results, I might consider that. However, NP-complete is arguably the second most common complexity categorization (after P), so I focus more on NP-complete.

2. edderiofer says:

Solitaire Chess is NP-complete: http://arxiv.org/pdf/1501.06398v1.pdf

Bloxorz is PSPACE-complete: http://arxiv.org/pdf/1411.5951.pdf

Trackmania is NP-complete: http://arxiv.org/pdf/1411.5765.pdf

2048 is PSPACE-hard: http://arxiv.org/pdf/1408.6315.pdf

Game About Squares is NP-hard: http://arxiv.org/pdf/1408.3645.pdf

Mastermind is NP-complete: http://arxiv.org/pdf/cs/0512049v1.pdf

Hashiwokakero is NP-complete: http://users-cs.au.dk/koda/thesis.pdf#page=111

Zen Puzzle Garden is NP-complete (and probably Right Way Robot and Ice Barn by similar constructions): http://www.sciencedirect.com/science/article/pii/S0020019011002870