Hanano

Description

Hanano is a puzzle game played on a 2D rectangular board. Each tile of the board is either empty, a movable block, an immovable platform, a $1 \times 1$ flower, a $1 \times 1$ stone, or part of a $2 \times 1$ or $1 \times 2$ blossomed stone. Each stone, blossomed stone, and flower is colored with exactly one color among red, yellow, and blue.

A move consists either moving a stone or blossomed stone horizontally (either one position to the left or to the right) or of swapping two adjacent stones, provided that the final positions do not intersect with any other object in the board. Each stone has one associated direction (up, down, left, or right) shown as a small white arrow.

Whenever a stone is adjacent to a flower of the same color, it turns into a $2 \times 1$ or $1 \times 2$ blossomed stone. While a blossomed stone moves as single object, it actually consists of two adjacent tiles: one tile is the stone itself while the other is an adjacent flower. The flower “blossoms” in the direction pointed by the stone’s arrow and can push other stones and blossomed stones in the process.

Finally, stones and blossomed stones are affected by gravity, i.e., they fall towards the bottom of the board when they are not supported by another stone, blossomed stone, or be an immovable platform.

The goal is to find a sequence of moves that causes all the stones to turn into blossomed stones.

Computational complexity

The problem of deciding whether a level admits a solution is NP-hard even when (i) the instance contains no immovable block, (ii) all the stones, blossomed stones, and flowers are of the same color, (iii) all the stones blossom upwards [1].

There solvable instances of Hanano for which any solution requires an exponential number of moves. It is not known whether the above problem lies in NP. [1]

References

[1] Z. Liu, C. Yang, “Hanano Puzzle is NP-hard”, Information Processing Letters, 2019.

@misc{cog:hanano,
    author = "{CoG contributors}",
    title  = "{Hanano --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/hanano/",
    note   = "[Online; accessed 2024-04-13]"
}