Jelly No Puzzle
A single player side-view game in which colored jellies can be moved horizontally and are affected by gravity. When two jellies of the same color touch they merge into a single jelly. The goal is to merge all jellies of each color.
Description
Jelly No Puzzle is a single-player side-view game played on a rectangular grid. Some cells of the board contain are immovable platforms while others are empty or contain jellies. The cells on the sides of the grid always contain immovable platforms.
A jelly occupies a group of connected (w.r.t. 4 adjacency) cells of the grid and has a color. Jellies are affected by gravity and fall downwards when they are not supported by a wall or another jelly. More precisely, if every cell of a jelly J is directly above a cell that is either empty or part of the same jelly, then J moves downwards by 1 cell. This process repeats until no jelly satisfies the above condition.
The player can move any jelly J of choice either left or right as long as this does not cause J to intersect with any immovable platform or other jelly.
Two jellies of the same color are adjacent if they share at least one edge of the constituting cells. The jellies of the same color are connected if there is a monochromatic path (sequence) of jellies between them such that any two neighboring jellies in the path are adjacent to each other. After each move all unsupported jellies are affected by gravity and then all (maximal) connected groups of jellies of the same color merge into a single jelly: the new jelly occupies all cells of the constituting jellies and has their same color.
The goal of the game is to merge all jellies of the same color into a single jelly.
Computational Complexity
The problem of deciding whether a given level of Jelly no Puzzle can be won has been shown to be NP-hard via a reduction 3-PARTITION [1]. The above result holds even when all jellies have the same color, in which case the problem belongs to NP.
It is not known whether the general problem (in which jellies can have multiple colors) belongs to NP.
Notes
A playable version of the NP-hardness reduction of [1] is available here.
References
[1] Chao Yang, “On the Complexity of Jelly-no-Puzzle”, in JCDCG^3 2018.
@misc{cog:jelly-no-puzzle,
author = "{CoG contributors}",
title = "{Jelly No Puzzle --- Complexity of Games}",
year = "2024",
url = "https://www.isnphard.com/i/jelly-no-puzzle/",
note = "[Online; accessed 2024-04-13]"
}
