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

coNP-complete

NP-hard

PSPACE-complete

PSPACE-hard

Undecidable