Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908761332908032 |
|---|---|
| author | Chavrimootoo, Michael C. Youn, Jin Seok |
| author_facet | Chavrimootoo, Michael C. Youn, Jin Seok |
| contents | The Hanano Puzzle is a one-player game with irreversible gravity, where the goal is to make colored blocks make contact with flowers of the corresponding color. The game Jelly no Puzzle shares similar mechanics. In general, determining if a given level of each of the two games is solvable is PSPACE-complete. There are also known restrictions under which determining if a level of Jelly no Puzzle is solvable is NP-complete. We find that under the same restrictions, determining if a level of Hanano Puzzle is solvable remains PSPACE-complete. We thus study several restrictions on Hanano, contrast them with known results about Jelly no Puzzle, and posit that the mechanism at the heart of the PSPACE-hardness is the ability for blocks to carry each other. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_08057 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles Chavrimootoo, Michael C. Youn, Jin Seok Computational Complexity The Hanano Puzzle is a one-player game with irreversible gravity, where the goal is to make colored blocks make contact with flowers of the corresponding color. The game Jelly no Puzzle shares similar mechanics. In general, determining if a given level of each of the two games is solvable is PSPACE-complete. There are also known restrictions under which determining if a level of Jelly no Puzzle is solvable is NP-complete. We find that under the same restrictions, determining if a level of Hanano Puzzle is solvable remains PSPACE-complete. We thus study several restrictions on Hanano, contrast them with known results about Jelly no Puzzle, and posit that the mechanism at the heart of the PSPACE-hardness is the ability for blocks to carry each other. |
| title | Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2601.08057 |