Heyawake

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

.

• 1 Правила
• 2 Методы решения
• 3 Варианты
• 4 Вычислительная сложность
• 5 См. Также
• 6 Примечания
• 7 Ссылки
• 8 Внешние ссылки

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

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

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

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

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

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

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

Остальные правила отличают Хейаваке от других головоломок «династии»:

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

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

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

Список типов головоломок Николи

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

• Страница Николи на Хейаваке