天体ショー（てんたいショー）は、Tentaisho、Galaxies、Spiral Galaxies、またはSym-a-Pixという名称でも知られる、ニコリによって出版された領域分割型の論理パズル（ペンシルパズル）である。
歴史 このパズルは、ゲサクによって考案され、日本のパズル雑誌『パズル通信ニコリ』の96号（2001年9月10日発売）において初めて掲載された。その後、同誌の98号において、特定のブロックを黒く塗りつぶすことで絵が浮かび上がるという現在のルールが追加された。
このパズルの名称は、「点対称」と「天体ショー（天文のショー）」を掛け合わせたもの（ダジャレ）となっている。
ルール 天体ショーは、正方形のマスからなる長方形の盤面を用いて行う。盤面上のマスの中央、辺上、または頂点上には、「白丸」や「黒丸」などの点が配置されている（「星」と表現される）。
パズルの目的は、マスの境界線（点線）に沿って線を引き、盤面をいくつかのブロックに分割することである。
完成した盤面において、すべてのブロックは点対称（180度回転対称）であり、その中心にちょうど1つの点を含んでいなければならない。
点の色はパズルの論理には影響を与えないため、解く際には無視して構わない。複数の色の点が配置されたパズルでは、完成した盤面の領域を対応する点の色で塗りつぶすことで、絵が浮かび上がるようになっている場合がある。
解法 天体ショーを解く際の一般的な手がかりとして、以下の手順が知られている。
点、または点の一部を含む隣接するマスの間に壁（境界線）を引く。これらのマスは互いに異なるブロックに属さなければならない。点対称の性質に従って、点の周囲に壁を引く。盤面の外枠も壁として扱われる。ある点によって「捕獲」された領域内のマスを見つける。これらは、他のどの点からも到達できないマスである。これらのマスは、その点に対応するブロックにしか属することができない。以上の手順を、パズルが解けるまで繰り返す。
より難易度の高いパズルでは、点対称の像を考慮する必要がある場合がある。点対称となるマスを考慮した際に、有効な点が1つしか存在しないマスを見つける。あるマスがブロックに属することができるのは、その対称となるマスもまた、そのブロックに属することができる場合のみである。
計算量 NP完全性 天体ショーのパズルに解が存在するかどうかの判定は、NP完全であることが知られている。これはFriedman (2002) によって、任意の論理回路と等価なパズルを構築することによって証明された。この構築は充足可能性問題の性質によりNP完全性を示すものである。
Fertin, Jamshidi, Komusiewicz (2015) は、すべてのブロックのサイズが最大でも7である場合においてもこのパズルがNP完全であることを証明し、この結果をさらに強固なものとした。この証明は、NP完全であることが知られているからの還元を構成している。
Demaine, Löffler, Schmidt (2021) は、すべてのブロックが1×1、1×3、または3×1のサイズの長方形に制限されている場合でもNP完全であることを証明した。また、与えられた形状を過不足なく覆う最小のブロックの集合を見つける問題についても、NP完全であることを示している。
解法アルゴリズム 天体ショーは、盤面の考えうるすべての分割方法を網羅し、それが有効な解であるかどうかを確認することにより、指数時間で解くことができる。
Fertin, Jamshidi, Komusiewicz (2015) は、（a）すべてのブロックのサイズが2以下の場合、（b）すべてのブロックが正方形の場合、（c）すべてのブロックが自明に連結している場合、といった様々なケースにおいてパズルを解くことができる多項式時間アルゴリズムを示した。
関連項目 ニコリ
脚注