标题： Jelly-No和Hanano游戏在各种约束条件下的复杂性 显示英文标题

标题： Complexity of Jelly-No and Hanano games with various constraints

摘要： 这项工作展示了关于Jelly-No和Hanano游戏复杂性的新结果，这些游戏在棋盘大小和颜色数量的各种约束下进行。 Hanano和Jelly-No是一人玩的2D侧视益智游戏，其动态棋盘由放置在平台上的彩色可移动方块组成。 这些方块可以由玩家移动，并受到重力的影响。 这两种游戏在玩法上有所不同，但目标始终是移动彩色方块以达到特定的配置，并使它们相互作用或与其他游戏元素互动。 在Jelly-No中，目标是合并所有相同颜色的彩色方块，当它们接触时也会发生这种情况。 在Hanano中，目标是通过与相同颜色的花朵接触使所有彩色方块绽放。 Jelly-No由Chao Yang证明，在所有可移动方块都是同一颜色的限制下是NP-Complete的，并且对于更多颜色的情况是NP-Hard的。 Hanano由Michael C. Chavrimootoo证明，在所有可移动方块都是同一颜色的限制下是PSPACE-Complete的。 然而，Jelly-No在超过一种颜色的情况下是否也是PSPACE-complete，或者它是否仍然处于NP中，这个问题仍未解决。 在本文中，我们解决了这个问题，证明了Jelly-No在颜色数量无限制的情况下是PSPACE-Complete的。 我们进一步表明，如果我们允许黑色果冻（即不需要合并的果冻），即使只有一种颜色，游戏也是PSPACE-complete的。 我们还进一步表明，单色Jelly-No和Hanano即使棋盘的宽度或高度是小常数，仍然是NP-Hard的。 显示英文摘要

摘要： This work shows new results on the complexity of games Jelly-No and Hanano with various constraints on the size of the board and number of colours. Hanano and Jelly-No are one-player, 2D side-view puzzle games with a dynamic board consisting of coloured, movable blocks disposed on platforms. These blocks can be moved by the player and are subject to gravity. Both games somehow vary in their gameplay, but the goal is always to move the coloured blocks in order to reach a specific configuration and make them interact with each other or with other elements of the game. In Jelly-No the goal is to merge all coloured blocks of a same colour, which also happens when they make contact. In Hanano the goal is to make all the coloured blocks bloom by making contact with flowers of the same colour. Jelly-No was proven by Chao Yang to be NP-Complete under the restriction that all movable blocks are the same colour and NP-Hard for more colours. Hanano was proven by Michael C. Chavrimootoo to be PSPACE-Complete under the restriction that all movable blocks are the same colour. However, the question whether Jelly-No for more than one colours is also PSPACE-complete or if it too stays in NP was left open. In this paper, we settle this question, proving that Jelly-No is PSPACE-Complete with an unbounded number of colours. We further show that, if we allow black jellies (that is, jellies that do not need to be merged), the game is PSPACE-complete even for one colour. We further show that one-colour Jelly-No and Hanano remain NP-Hard even if the width or the height of the board are small constants.