Tentai Show
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]
Rules
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]
Solution Methods
Tentai Show puzzles can be solved using the following steps.
- Draw walls between adjacent cells that contain a dot or a fraction of a dot. These cells must belong to different galaxies.
- Draw walls around the dot according to rotational symmetry. Borders of the grid also count as walls.
- Find cells in areas that are 'captured' by a dot. These are cells which cannot be reached by any other dot. These cells can only belong to the galaxy for that dot.
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]
History
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. Combined together, "Tentai Show" can both mean rotational symmetry and astronomical show.[2]
Computational Complexity
NP-Completeness
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]
Solution Algorithms
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.[5]
See also
- List of Nikoli puzzle types
References
- ↑ "Puzzle of Nikoli". Nikoli. https://www.nikoli.co.jp/en/puzzles/index.html.
- ↑ 2.0 2.1 "Rules of Tentai Show". Nikoli. https://www.nikoli.co.jp/en/puzzles/astronomical_show.html.
- ↑ "Sym-a-Pix techniques". https://www.conceptispuzzles.com/index.aspx?uri=puzzle/sym-a-pix/techniques.
- ↑ Friedman, Erich. "Spiral Galaxies Puzzles are NP-complete". https://erich-friedman.github.io/papers/spiral.pdf.
- ↑ 5.0 5.1 Fertin, Guillaume; Jamshidi, Shahrad; Komusiewicz, Christian (June 2015). "Towards an Algorithmic Guide to Spiral Galaxies". Theoretical Computer Science 586: 26–39. doi:10.1016/j.tcs.2015.01.051. https://hal.archives-ouvertes.fr/hal-01159940. Retrieved 18 August 2021.
- ↑ Demaine, Erik; Löffler, Maarten; Schmidt, Christiane. "Rectangular Spiral Galaxies are Still Hard". https://weber.itn.liu.se/~chrsc91/papers/spiral-galaxies.pdf.
 |  |
