Тентай Шоу
Tentai Show ( японский : 天体ショーtentai shō ), также известный под названиями Tentaisho , Galaxies , Spiral Galaxies или Sym-a-Pix , представляет собой логическую головоломку с двоичным определением, опубликованную Nikoli . [1]
Правила
Tentai Show играется на прямоугольной сетке из квадратов. На сетке находятся точки, представляющие звезды , которые можно найти на сетке либо в центре клетки, либо на краю, либо в углу.
Цель головоломки — провести линии вдоль пунктирных линий, чтобы разделить сетку на области, представляющие галактики .
В полученной сетке все галактики должны иметь вращательную симметрию 180° и содержать ровно одну точку, расположенную в ее центре.
Цвета точек не влияют на логику головоломки и могут игнорироваться при решении. В головоломках с многоцветными точками области готовой сетки могут быть окрашены соответствующими цветами точек, чтобы раскрыть картинку. [2]
Методы решения
Головоломки Tentai Show можно решить, выполнив следующие шаги.
- Нарисуйте стены между соседними ячейками, содержащими точку или часть точки. Эти ячейки должны принадлежать разным галактикам.
- Нарисуйте стены вокруг точки в соответствии с вращательной симметрией. Границы сетки также считаются стенами.
- Найдите ячейки в областях, которые «захвачены» точкой. Это ячейки, которые не могут быть достигнуты никакой другой точкой. Эти ячейки могут принадлежать только галактике для этой точки.
Вышеуказанные шаги можно повторять до тех пор, пока головоломка не будет решена.
В более сложных головоломках может потребоваться рассмотреть изображение вращательной симметрии. Найдите ячейки, которые имеют только одну допустимую точку при рассмотрении вращательно-симметричной ячейки. Ячейка может принадлежать галактике, если ее симметричная ячейка также может принадлежать этой галактике. [3]
История
Название головоломки «Tentai Show» имеет двойное значение при интерпретации на японском языке. «Ten» (点) означает точку , а «tai shō» (対称) означает симметрию . Японское слово «Tentai» (天体) используется для обозначения астрономических объектов. В сочетании «Tentai Show» может означать как вращательную симметрию , так и астрономическое шоу . [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) продемонстрировали алгоритм с полиномиальным временем , который может решить головоломку для различных случаев, таких как: (a) когда все галактики имеют размер не более двух, (b) когда все галактики являются квадратами и (c) когда все галактики тривиально связаны. [5]
Смотрите также
Ссылки
- ^ "Загадка Николи". Николи . Проверено 18 августа 2021 г.
- ^ ab "Rules of Tentai Show". Николи . Получено 18 августа 2021 г.
- ^ "Техники Sym-a-Pix". Головоломки Conceptis . Получено 19 августа 2021 г.
- ^ Фридман, Эрих. «Загадки спиральных галактик являются NP-полными» (PDF) . Получено 18 августа 2021 г.
- ^ ab Fertin, Guillaume; Jamshidi, Shahrad; Komusiewicz, Christian (июнь 2015 г.). «Towards an Algorithmic Guide to Spiral Galaxies». Теоретическая информатика . 586 : 26–39. doi : 10.1016/j.tcs.2015.01.051 . Получено 18 августа 2021 г.
- ^ Демейн, Эрик; Лёффлер, Маартен; Шмидт, Кристиан. «Прямоугольные спиральные галактики все еще твердые» (PDF) . Получено 18 августа 2021 г.
 | Эта статья, связанная с головоломкой/логической игрой, является заглушкой . Вы можете помочь Википедии, расширив ее. |
