Татамибари - Tatamibari

Татамибари (Японский: タ タ ミ バ リ) является разновидностью логическая головоломка разработан и опубликован Николи. Пазл основан на японском татами коврики.

Загадка татамибари.
Решенная сетка татамибари

Правила

Загадка Татамибари разыгрывается на прямоугольной сетке с тремя различными типами символов: +, -. и |, Решающая программа должна разбить сетку на прямоугольные или квадратные области в соответствии со следующими правилами:[1]

  • Каждый раздел должен содержать ровно один символ.
  • Символ + должен находиться в квадрате.
  • А | символ должен содержаться в прямоугольнике, высота которого больше ширины.
  • Символ - должен содержаться в прямоугольнике, ширина которого больше высоты.
  • Четыре части никогда не могут находиться в одном углу.

Вычислительная сложность

Проблема поиска решения конкретной конфигурации Татамибари заключается в следующем: НП-полный.[2]

Смотрите также

использованная литература

  1. ^ «Правила и пример татамибари». Получено 16 мая, 2011.
  2. ^ Адлер, Авив; Босбом, Джеффри; Demaine, Erik D .; Demaine, Martin L .; Лю, Quanquan C .; Линч, Джейсон (7 мая 2020 г.). «Татамибари является NP-полным». arXiv:2003.08331 [cs.CC ].