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.
-
Bamboo Garden Trimming
Interactive simulation of three Trimming Oracles: compact data structures that can quickly generate the sequence of bamboos to cut in the Bamboo Garden Trimming problem according to some perpetual cutting strategy.
-
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.
-
Jelly-No Puzzle
An interactive implementation of a reduction from 3-PARTITION showing that deciding whether a level of Jelly no Puzzle is solvable is NP-hard.
-
Peg Solitaire is NP-Hard
Playable implementation of the reduction from Hamiltonian cycle in a directed planar bigraph, showing that deciding on the solvability of a generalized Peg Solitaire level is NP-hard.
-
Simultaneous Maze Solving
Interactive implementation of the reduction from SAT showing that finding a short sequence of moves that solves several mazes at once is 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.