This page is no longer updated. I am no longer actively watching this page. There might be styling errors, rotted links, and so on.
. This was the last update time of the original page that I maintained on my WordPress blog. I think I only started setting up a website in 2020, so I copied over the full text as-is, without formatting it.
I'm no longer maintaining this page. Unfortunately, I don't know if there's any other place where these kinds of results are collected. Wikipedia has lists such as NP-complete games and puzzles, although it might be missing some results that are included here. For that reason, I'm keeping the page up to preserve it.
However, I have been lacking the motivation to add new things here for over five years now, so I'll just face the truth that I'm no longer maintaining this page. If you're interested in picking up this project, feel free to do so. What follows below is completely unchanged from its latest update in 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.