Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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


Правила [ править ]

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

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

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

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

Способы решения [ править ]

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

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

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

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

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

Варианты [ править ]

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

Вычислительная сложность [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]