# 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.

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!