Тентай Шоу
Tentai Show ( японский : 天体ショー tentai shō ), также известный под названиями Tentaisho , Galaxies , Spiral Galaxies или Sym-a-Pix с двоичным определением, , представляет собой логическую головоломку опубликованную Nikoli . [1]
Правила
[ редактировать ]Тентай-шоу проводится на прямоугольной сетке квадратов. На сетке расположены точки, обозначающие звезды , которые можно найти в центре ячейки, на краю или в углу.
Цель головоломки — провести линии вдоль пунктирных линий, чтобы разделить сетку на области, представляющие галактики .
В полученной сетке все галактики должны иметь вращательную симметрию 180° и содержать ровно одну точку, расположенную в ее центре.
Цвета точек не влияют на логику головоломки и их можно игнорировать при решении. В головоломках с несколькими цветными точками участки готовой сетки можно раскрасить соответствующими цветами точек, чтобы открыть картинку. [2]
Методы решения
[ редактировать ]Головоломки Tentai Show можно решить, выполнив следующие действия.
- Нарисуйте стены между соседними ячейками, содержащими точку или часть точки. Эти ячейки должны принадлежать разным галактикам.
- Нарисуйте стены вокруг точки в соответствии с вращательной симметрией. Границы сетки также считаются стенами.
- Найдите ячейки в областях, которые «захвачены» точкой. Это ячейки, до которых не может добраться никакая другая точка. Эти ячейки могут принадлежать галактике только для этой точки.
Вышеуказанные шаги можно повторять до тех пор, пока головоломка не будет решена.
В более сложных головоломках может возникнуть необходимость учитывать образ вращательной симметрии. Найдите ячейки, которые имеют только одну действительную точку, рассматривая их вращательно-симметричную ячейку. Ячейка может принадлежать галактике, если ее симметричная ячейка также может принадлежать этой галактике. [3]
История
[ редактировать ]Название головоломки «Тентай-шоу» в японском языке имеет двойной смысл. «Десять» (点) означает точку , а «тай сю» (対称) означает симметрию . Японское слово «Тентай» (天体) используется для обозначения астрономических объектов. В сочетании «Тентай-шоу» может означать как вращательную симметрию , так и астрономическое шоу . [2]
Вычислительная сложность
[ редактировать ]NP-полнота
[ редактировать ]Известно, что определение того, имеет ли головоломка Tentai Show решение, является NP-полным . Это было доказано Фридманом (2002) путем построения головоломок, эквивалентных произвольным булевым схемам , что показывает NP-полноту из-за проблемы булевой выполнимости . [4]
Фертин, Джамшиди и Комузевич (2015) усилили этот результат, доказав, что головоломка является NP-полной, когда все галактики имеют размер не более семи. Доказательство сводит головоломку к Positive Planar 1-in-3-SAT , которая, как известно, является NP-полной. [5]
Демейн, Лёффлер и Шмидт (2021) еще больше усилили это утверждение, доказав NP-полноту, даже если все галактики ограничены прямоугольниками размеров 1×1, 1×3 или 3×1.
Они также показали, что поиск минимального набора галактик, точно покрывающих заданную форму, является NP-полным. [6]
Алгоритмы решения
[ редактировать ]Головоломки Tentai Show можно решать за экспоненциальное время , просматривая все возможные разрезы сетки и проверяя, является ли это правильным решением.
Фертин, Джамшиди и Комузевич (2015) показали алгоритм с полиномиальным временем , который может решить головоломку для различных случаев, таких как: (а) когда все галактики имеют размер не более двух, (б) когда все галактики квадратные и ( в) когда все галактики тривиально связаны. [5]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Загадка Николи» . Николи . Проверено 18 августа 2021 г.
- ^ Jump up to: Перейти обратно: а б «Правила Тентай Шоу» . Николи . Проверено 18 августа 2021 г.
- ^ «Техники Sym-a-Pix» . Концептуальные головоломки . Проверено 19 августа 2021 г.
- ^ Фридман, Эрих. «Загадки о спиральных галактиках NP-полные» (PDF) . Проверено 18 августа 2021 г.
- ^ Jump up to: Перейти обратно: а б Фертен, Гийом; Джамшиди, Шахрад; Комусевич, Кристиан (июнь 2015 г.). «К алгоритмическому руководству по спиральным галактикам» . Теоретическая информатика . 586 : 26–39. дои : 10.1016/j.tcs.2015.01.051 . Проверено 18 августа 2021 г.
- ^ Демейн, Эрик; Леффлер, Мартен; Шмидт, Кристиана. «Прямоугольные спиральные галактики все еще тверды» (PDF) . Проверено 18 августа 2021 г.
 | Эта головоломкам/логическим играм, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее . |