Логическая головоломка
Шакашака (シャカシャカ) — логическая головоломка, разработанная издателем Николи . [1]
Правила
Шакашака играется на прямоугольной сетке из белых и черных квадратов. Некоторые черные клетки могут содержать число.
Цель головоломки — разместить треугольники в некоторых белых клетках. Существует четыре вида треугольников, которые можно разместить в квадратах:
В полученной сетке
- Белые части сетки (незакрытые черными треугольниками) должны образовывать прямоугольник или квадрат.
- Черные клетки с номером должны быть ортогонально смежны с указанным количеством черных треугольников. [2]
Сложность вычислений
Определение того, имеет ли данная головоломка Шакашака решение, является NP-полной задачей. [3]
Более того, подсчет количества решений данной головоломки Шакашака является #P-полной задачей . [3]
Ссылки
- ^ "Puzzles of nikoli.com". Николи . Получено 18 августа 2021 г. .
- ^ "Правила головоломки Шакашака" . Николи . Проверено 18 августа 2021 г.
- ^ ab Demaine, Erik D .; Okamoto, Yoshio; Uehara, Ryuhei; Uno, Yushi (2014), «Вычислительная сложность и модель целочисленного программирования Shakashaka», IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , E97-A (6): 1213–1219, Bibcode : 2014IEITF..97.1213D, doi : 10.1587/transfun.E97.A.1213, hdl : 10119/12147
