Heyawake - Heyawake

Heyawake (Японский: へ や わ け, «разделенные комнаты») - это двоичное определение логическая головоломка опубликовано Николи. По состоянию на 2013 год пять книг, полностью состоящих из Heyawake пазлы были опубликованы Николи. Впервые он появился в Пазл Общение Николи №39 (сентябрь 1992 г.).

Загадка Хейаваке.


Правила

Heyawake играется на прямоугольной сетке ячеек без стандартного размера; сетка разделена на прямоугольные «комнаты» разного размера жирными линиями по краям ячеек. Некоторые комнаты могут содержать одно число, обычно напечатанное в их верхней левой ячейке; в соответствии с первоначальным дизайном каждая комната была пронумерована, но это редко требуется для решения и больше не соблюдается.

Некоторые ячейки головоломки должны быть окрашены в черный цвет; цель головоломки - определить для каждой ячейки, должна ли она быть окрашена или должна быть оставлена ​​пустой (оставаясь белой). На практике часто бывает проще пометить известные «пустые» ячейки каким-либо образом, например, поставив точку в центре ячейки.

Следующие правила определяют, какие ячейки какие:

  • Правило 1: Окрашенные клетки никогда не могут быть соединены ортогонально (они не могут иметь общую сторону, хотя могут касаться диагонально).
  • Правило 2: Все белые клетки должны быть связаны между собой (образовывать единый полимино ).
  • Правило 3: Число указывает, сколько именно окрашенных ячеек должно быть в этой конкретной комнате.
  • Правило 4: Комната без номера может содержать любое количество окрашенных ячеек или ни одной.
  • Правило 5: Если образуется прямая (ортогональная) линия соединенных белых ячеек, она не должна содержать ячеек более чем из двух комнат - другими словами, любая такая линия белых ячеек, которая соединяет три или более комнат, запрещена.

Методы решения

Обратите внимание, что первые два правила также применяются (например) к Хитори головоломки, и поэтому эти головоломки разделяют некоторые из своих методов решения:

  • Если обнаруживается, что ячейка окрашена, сразу становится известно, что все четыре (ортогонально) соседние ячейки должны быть белыми (из правила 1).
  • Часть (ортогонально) смежных белых клеток не может быть отрезана от остальной части сетки (из правила 2). Черные ячейки не могут образовывать диагональное разделение сетки или замкнутый контур; любая ячейка, которая завершит такое «короткое замыкание», должна быть белой.

Более сложные головоломки требуют сочетания Правил 1 и 2, чтобы продвигаться вперед без угадывания; ключом является распознавание того, где ячейки должны принимать одну из двух клетчатых структур, а одна ведет к короткому замыканию.

Остальные правила различают Heyawake из других головоломок "династии":

  • Правило 5 - определяющее правило головоломки; черные клетки должны быть размещены так, чтобы любые (ортогональные) линии белых клеток не пересекали две границы комнаты («гаечные ключи»).
  • Нумерованные комнаты обычно предоставляют решателям отправную точку, помимо других вычетов. Ниже приведены простейшие примеры комнат, определенных в начале:
    • Комната 2 × 2 в углу сетки, содержащая цифру «2», должна иметь одну окрашенную ячейку в углу сетки и второй окрашенный квадрат по диагонали наружу от угла. Поскольку нарисованные квадраты не могут иметь одну сторону (Правило 1), единственной альтернативой будет отключение принудительной белой клетки в углу, что нарушает Правило 2.
    • Комната 2 × 3 со стороной с 3 ячейками вдоль границы сетки, содержащей цифру '3', должна иметь окрашенную ячейку в центре стороны с 3 ячейками вдоль границы и две другие в противоположных углах комнаты, для причины, аналогичные приведенным выше.
    • В комнате размером 1 × 3, содержащей цифру «2», должны быть окрашены две крайние ячейки, так как окрашенная центральная ячейка вызовет нарушение правила 1. В более общем случае, 1 × (2п−1) комната, содержащая п должны быть окрашены все остальные ячейки внутри него.
    • Комната 3x3, содержащая цифру «5», должна иметь клетчатый узор с нарисованными ячейками во всех углах и в центре.

Варианты

  • Heyawacky играется как Хейаваке, но комнаты не обязательно прямоугольные. Ортогональные линии белых клеток не могут выходить и повторно входить в комнату; т.е. такие линии не могут пересекать более чем одну границу региона.
  • Симметрия Хейаваке Играется как Хейаваке, но подсказки показывают, является ли узор черных ячеек в комнате осесимметричным относительно его центра или нет.

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

В вычислительная сложность Хейаваке был проанализирован:[1] решение для данного экземпляра Heyawake, существует ли решение головоломки, НП-полный. Интерпретация этого теоретического результата в терминах непрофессионала состоит в том, что эту загадку так же сложно решить, как и Проблема логической выполнимости, которая является хорошо изученной сложной задачей в Информатика.

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

Список типов пазлов Николи

Примечания

  1. ^ М. Хольцер, О. Рупп (2007)

Рекомендации

  • Хольцер, Маркус; Рупп, Оливер (2007). «Проблемы дизайна интерьера - анализ сложности игры Heyawake» (PDF). Труды 4-й Международной конференции по развлечениям с алгоритмами, LNCS 4475. Шпрингер, Берлин / Гейдельберг. С. 198–212. Дои:10.1007/978-3-540-72914-3_18. ISBN  978-3-540-72913-6.

внешняя ссылка