Хейауэйк

Пазл Хейауэйк

Heyawake ( японский с двоичным определением, : へやわけ, «разделённые комнаты») — логическая головоломка опубликованная Николи . пять книг, полностью состоящих из головоломок Хейявке По состоянию на 2013 год Николи опубликовал . Впервые он появился в журнале Puzzle Communication Nikoli № 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 n −1), содержащая n, должна иметь все другая ячейка внутри него закрашена.
  • Комната 3х3, содержащая цифру 5, должна иметь клетчатый узор с закрашенными клетками во всех углах и в центре.

Варианты

• В Хейаваки играют так же, как и в Хейаваке, но комнаты не обязательно прямоугольные. Ортогональные линии белых клеток не могут выходить из комнаты и возвращаться в нее; т.е. такие линии не могут пересекать более чем одну границу региона.
• Симметрия Heyawake (также известная как ekawayeH и Ayaheya ) играется так же, как Heyawake, но подсказки указывают, является ли рисунок черных клеток в комнате вращательно-симметричным вокруг ее центра или нет.

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

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

См. также

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

Ссылки

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

Внешние ссылки

• Страница Николи на Heyawake