# Games are Hard

Last updated 27 April 2018

I love puzzles and games a lot. I also enjoy theoretical computer science. So, of course this had to be done.

This page documents as many possible puzzles/games/etc and their computational complexity, along with sources leading to them. I strive to make this as complete as possible, but it's obviously very hard, so you're welcome to help; you can contact me through my e-mail, available on the main page.

Note: 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). Most works only talk about whether something is satisfiable, but whether something is sound is also important: most logic puzzles should only have one solution (it's in the name, the solution should be deducible through logic and not guessing); if you have multiple solutions in Minesweeper, you need to resort to guessing and thus might lose just due to chance, etc. I try my best to document this distinction below.

## 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
• 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
• Super Mario Bros (whether one can reach a target point) from QBF

## 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