Tentai Show (Japanese: 天体ショー tentai shō), also known by the names Tentaisho, Galaxies, Spiral Galaxies, or Sym-a-Pix, is a binary-determination logic puzzle published by Nikoli.[1]
Tentai Show is played on a rectangular grid of squares. On the grid are dots representing stars, which can be found on the grid either on the center of a cell, an edge, or a corner.
The objective of the puzzle is to draw lines along the dashed lines to divide the grid into regions representing galaxies.
In the resulting grid, all galaxies must have 180° rotational symmetry and contain exactly one dot located at its center.
The colors of the dots do not affect the logic of the puzzle and can be ignored when solving. In puzzles with multiple colored dots, the regions of the finished grid may be colored with the corresponding dot colors to reveal a picture.[2]
Tentai Show puzzles can be solved using the following steps.
The above steps can be repeated until the puzzle is solved.
In more advanced puzzles, it may be necessary to consider the image of rotational symmetry. Find cells which only have one valid dot when considering its rotationally symmetric cell. A cell can belong to a galaxy if its symmetric cell can also belong to that galaxy.[3]
The name of the puzzle, "Tentai Show", has a double meaning when interpreted in Japanese. "Ten" (点) stands for dot, while "tai shō" (対称) stands for symmetry. The Japanese word "Tentai" (天体) is used to refer to astronomical objects. When combined, "Tentai Show" can both mean rotational symmetry and astronomical show.
Determining whether a Tentai Show puzzle has a solution is known to be NP-complete. This was proven by Friedman (2002) by constructing puzzles equivalent to arbitrary Boolean circuits, which shows NP-completeness because of the Boolean satisfiability problem.[4]
Fertin, Jamshidi, and Komusiewicz (2015) strengthened this result by proving the puzzle is NP-complete when all galaxies have size at most seven. The proof reduces the puzzle to Positive Planar 1-in-3-SAT, which is known to be NP-complete.[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.
Fertin, Jamshidi, and Komusiewicz (2015) showed a polynomial-time algorithm that can solve the puzzle for various cases, such as: (a) when all galaxies have size at most two, (b) when all galaxies are squares, and (c) when all galaxies are trivially connected.