Also known as Complexity of Games and Puzzles. Original title was NPcompleteness. Most likely will be more uptodate 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 partiallysolved 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 NPcomplete. Anyone knows whether the papers are available online?
Last updated 06Jun2016
Puzzles and games that are proven to be in some class, along with what reduces to them…
NPcomplete
 Akari (satisfiability) from 3SAT
 Battleships (satisfiability) from 3SAT, from bin packing
 Bejeweled (whether a given gem can be popped) from 1in3 SAT
 Corral (satisfiability) from 3colorability of planar graphs
 Cryptarithms (Verbal Arithmetic) (satisfiability) from 3SAT
 Fillomino (satisfiability) from 3SAT
 Galaxies (satisfiability) from 3SAT
 Hashi(wokakero) (satisfiability) from existence of Hamiltonian circuits in unitdistance graphs
 Heyawake (satisfiability) from 3SAT
 Kakuro (satisfiability) from 3SAT
 KenKen (TomTom) (satisfiability) from Latin Square
 Kurodoko (satisfiability) from 3SAT
 Latin Square (satisfiability) from triangulation of tripartite graphs
 Lemmings (satisfiability) from 3SAT
 Mastermind (satisfiability) from vertex cover
 Masyu (satisfiability) from existence of Hamiltonian circuits in cubic graphs
 Minesweeper (satisfiability) from 3SAT
 Nonogram (satisfiability) from Nondeterministic Constraint Logic
 Nurikabe (satisfiability) from 3SAT
 Patterna (satisfiability) from 3SAT
 Ripple Effect (satisfiability) from 3SAT, Latin Square
 Slitherlink (satisfiability) from existence of Hamiltonian circuits in cubic graphs
 Solitaire Chess (satisfiability) from 3SAT
 Sudoku (satisfiability) from Latin Square
 Super Mario Bros (whether one can reach a target point) from 3SAT
 Tetris (whether one can survive over a known finite sequence of pieces) from 3partition
 TrackMania (whether one can finish the lap) from 3SAT
 Zen Puzzle Garden (satisfiability) from existence of Hamiltonian circuits in cubic graphs
coNPcomplete
 Patterna (soundness) from 3UNSAT
NPhard
 Pokémon (with only Trainers) (whether one can reach a target point) from 3SAT
 Game about Squares (consistency) from 3SAT
PSPACEcomplete
 2048 (reaching target configuration) from Nondeterministic Constraint Logic
 Bloxorz from Nondeterministic Constraint Logic
 Sokoban from simulating linear bounded automata
PSPACEhard
 Pokémon (whether one can reach a target point) from Sokoban
Undecidable
 Braid (whether one can reach a target point) from simulating counter machine
Pingback: NPComplete Games and Puzzles  Chaos at the Sky
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, NPcomplete is arguably the second most common complexity categorization (after P), so I focus more on NPcomplete.
Solitaire Chess is NPcomplete: http://arxiv.org/pdf/1501.06398v1.pdf
Bloxorz is PSPACEcomplete: http://arxiv.org/pdf/1411.5951.pdf
Trackmania is NPcomplete: http://arxiv.org/pdf/1411.5765.pdf
2048 is PSPACEhard: http://arxiv.org/pdf/1408.6315.pdf
Game About Squares is NPhard: http://arxiv.org/pdf/1408.3645.pdf
Mastermind is NPcomplete: http://arxiv.org/pdf/cs/0512049v1.pdf
Hashiwokakero is NPcomplete: http://userscs.au.dk/koda/thesis.pdf#page=111
Zen Puzzle Garden is NPcomplete (and probably Right Way Robot and Ice Barn by similar constructions): http://www.sciencedirect.com/science/article/pii/S0020019011002870
Hexcells is NPcomplete, from 3SAT (informal proof): https://youtu.be/3yHEYy0LpRk?t=426
That’s essentially Minesweeper.
True, true.
I would like to comment on the fact that I myself did not bring up the difference between soundness and consistency; this is merely an interpretation of my words.
My original comment criticized the idea that playing Minesweeper (or similar games such as my own Patterna, or the fabulous HexCells) is a process of solving an NPcomplete problem. The original proof for NPcompleteness of Minesweeper concerns the Minesweeper Consistency Problem (which is also how it was listed on this page), which asks whether there is a way to place mines on the board that is consistent with the information given on the Minesweeper board. To me, this is not a question of whether there is *a solution* to the board (and thus a question of consistency), since the vast majority of these assignments will lead to you loosing the game. If you are asking whether a level is solvable, you are asking whether there is a way to uncover the (necessarily) unique solution by using a sound logical argument, i.e., a proof. Thus the solution of a Minesweeper board must be a consistent assignment together with a proof that this is the only assignment that makes it work. In this perspective, a Minesweeper level is more appropriately specified as a grid with all information given (i.e., you already know where the mines are to begin with) and a set of cells that are initially revealed to the actual player of the game. The question then is whether the player can deduce the position of all mines on the board. This seems more appropriate since it better models the actual playing of the game and is close to the way that Minesweeper levels are stored in memory. In theory, there could of course also be a variant of Minesweeper where there are no mines to begin with, but only hints about where mines should be. Then your job would be to place mines in such a way that is fulfills are the constraints given by the hints — and *this problem* is NPcomplete. (Call this problem Minelayer, instead of Minesweeper.) You can read the article about Patterna linked above in the list to read about my point in more detail.
I would also like to address the question of uniqueness of solutions in this context. The prototypical NPcomplete problem is SAT – that is, given a formula, is it satisfiable? There is a variant of this problem, called UniqueSAT, which reads as “given a formula, is there exactly one satisfying assignment of the variables”? (Not to be confused with UnambiguousSAT, which asks whether a formula that is guaranteed to have at most one satisfying assignment is actually satisfiable.) While SAT is NPcomplete, UniqueSAT is not. In fact, it is coNPhard and in DP (but only DPcomplete under deterministic polytime reductions if coNP=NP [it is DPcomplete under randomized reductions]). It is currently not known whether UniqueSAT is in coNP. I would guess that something similar is true for the uniqueness variant of the Minesweeper Consistency Problem.