*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.

- 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

- Patterna (soundness) from 3-UNSAT

- Pokémon (with only Trainers) (whether one can reach a target point) from 3-SAT
- Game about Squares (consistency) from 3-SAT

- 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

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

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