Шакашака
Пример головоломки Шакашака
Та же головоломка, решение отмечено бирюзовым цветом.
Шакашака Николи логическая издательством — головоломка разработанная . , [1]
Правила
[ редактировать ]В шакашаку играют на прямоугольной сетке из белых и черных квадратов. Некоторые черные клетки могут содержать числа.
Цель головоломки — разместить треугольники в некоторых белых клетках. Существует четыре вида треугольников, которые можно сложить в квадраты: 
В полученной сетке
- Белые части сетки (не закрытые черными треугольниками) должны образовывать прямоугольник или квадрат.
- Черные ячейки с номером должны ортогонально примыкать к указанному количеству черных треугольников. [2]
Вычислительная сложность
[ редактировать ]является NP-полной . Решение о том, имеет ли данная головоломка Шакашака решение, [3] Более того, подсчет количества решений данной головоломки Шакашака является #P-полным . [3]
Ссылки
[ редактировать ]- ^ «Пазлы nikoli.com» . Николи . Проверено 18 августа 2021 г.
- ^ «Правила головоломки Шакашака» . Николи . Проверено 18 августа 2021 г.
- ^ Jump up to: а б Демейн, Эрик Д .; Окамото, Ёсио; Уэхара, Рюхей; Уно, Юши (2014), «Вычислительная сложность и модель целочисленного программирования Шакашаки», Транзакции IEICE по основам электроники, связи и компьютерных наук , E97-A (6): 1213–1219, Бибкод : 2014IEITF..97.1213D , doi : 10.1587/transfun.E97.A.1213 , hdl : 10119/12147
 | Эта игрой статья, связанная с , незавершена . Вы можете помочь Википедии, расширив ее . |