Tentai Show

[3] The name of the puzzle, "Tentai Show", has a double meaning when interpreted in Japanese.

[4] Fertin, Jamshidi, and Komusiewicz (2015) strengthened this result by proving the puzzle is NP-complete when all galaxies have size at most seven.

[5] Demaine, Löffler, and Schmidt (2021) further strengthened this by proving NP-completeness even if all galaxies are restricted to be rectangles of sizes 1×1, 1×3, or 3×1.

They also showed that finding a minimal set of galaxies that exactly cover a given shape is NP-complete.

[6] Tentai Show puzzles can be solved in exponential time by going through all possible dissections of the grid and checking if it is a valid solution.

An unsolved Tentai Show puzzle.
The same puzzle, solved. The regions are colored to reveal a picture of a cat.