Hosting
Here is a list of the games for which we host supplementary material.
You are welcome to add your own contribution related to the complexity of games (implementations of hardness reductions, animations, simulations, cool visualizations of proofs, etc...) to this list. Please see
this page for instructions.
-
Candy Crush is (NP-)Hard!
Interactive implementation of the reduction from 1-in-3 positive SAT showing that Bejeweled, Candy Crush and other match-three games are (NP-)Hard.
-
Solitaire Army
Visualization of solutions to the solitaire army problem for several different types of deserts. An interactive version of the game is playable.
-
Trainyard is NP-Hard
Interactive implementation of the reduction from Minimum Monotone SAT showing that Trainyard NP-hard.
-
Trainyard Verification is PSPACE-complete
Interactive implementation of the reduction from Iterated Monotone Boolean Circuit showing that the problem of veryfing a Trainyard solution is PSPACE-complete.
-
Two-Dots is NP-Hard
Interactive implementation of the reduction from Exact Cover by 3-Sets showing that Two Dots is NP-hard even with 2 goals and 3 colors.