 # Jelly-No Puzzle is NP-complete (even with only 1 color)

This is an implementation of the NP-hardness reduction described in the paper "On the Complexity of Jelly-no-Puzzle" by Chao Yang. The reduction is from 3-PARTITION to the problem of deciding whether a Jelly no Puzzle level is solvable. A description of Jelly no Puzzle can be found here.

The 3-PARTITION problem is a well-known NP-complete problem that asks to decide whether a multiset X containing positive integers can be partitioned in groups so that each groups has exactly 3 elements and the sum of the elements in each group are equal.
Clearly, we can restrict to instances (multisets) for which (i) |X| is a multiple of 3, and (ii) the sum S of all integers in X is a multiple of |X|/3, meaning that the sum of every group should be T=3S/|X|. It is easy to see that if any of (i) and (ii) is violated, then the 3-PARTITION instance has answer "no". Furthermore, the problem is known to remain NP-complete even when each integer in S is strictly between T/4 and T/2.

The generated level contains a platform on the top right with a jelly for each integer in the input set on top. A generic integer x in S will correspond to a jelly of height 1 and width x. On the bottom of the level there be exactly |S|/3 "bins" of width T.
To win the level, a group of jellies with a total width of T needs to be (suitably) moved into each bin, effectively solving the associated 3-PARTITION instance.

## Play the reduction!

Insert a 3-PARTITION instance, separating integers with a comma and/or a space, then press "Generate level!". The chosen instance should satisfy conditions (i) and (ii) described above.
To move a jelly, select it by clicking on it and use the A and D keys. Good luck!

## About the authors

The author of the reduction is Chao Yang. The author of the implementation is Giorgio Ciotti.