Tentai Show (

Japanese Japanese may refer to: * Something from or related to Japan, an island country in East Asia * Japanese language, spoken mainly in Japan * Japanese people, the ethnic group that identifies with Japan through ancestry or culture ** Japanese diaspor ...

: 天体ショー ''tentai shō''), also known by the names Tentaisho, Galaxies, Spiral Galaxies, or Sym-a-Pix, is a binary-determination

logic puzzle A logic puzzle is a puzzle deriving from the mathematics, mathematical field of deductive reasoning, deduction. History The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the a ...

published by Nikoli.

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.

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.

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. When combined, "Tentai Show" can both mean ''rotational symmetry'' and ''astronomical show''.

Computational Complexity

NP-Completeness

Determining whether a Tentai Show puzzle has a solution is known to be

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

. This was proven by Friedman (2002) by constructing puzzles equivalent to arbitrary

Boolean circuits In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input ...

, which shows NP-completeness because of the

Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

. 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. 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.

Solution Algorithms

Tentai Show puzzles can be solved in

exponential time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

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 In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

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.

References

Logic puzzles NP-complete problems Japanese board games {{Puzzle-game-stub