Supplementary Material

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.
  • Constrained Colored Token Swapping
    Swap adjacent colored tokens placed on the vertices of a graph in order to reach a target final configuration. Not all color pairs can be swapped.
  • 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.
  • Solo-Chess
    An interactive implementation of two reductions showing that Solo-Chess with uniform budgets and only knights or only rooks is NP-Hard.
  • Torus Puzzle
    A playable version of the Torus Puzzle along with an implementation of a solution strategy that uses an asymptotically optimal number of unit rotations, up to polylogarithmic factors.
  • Trainyard is NP-Hard
    Interactive implementation of the reduction from Minimum Monotone SAT showing that Trainyard NP-hard.
  • 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.