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.
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.
Puzzles and games that are proven to be in some class, along with what reduces to them…