Японский кроссворд

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Японский кроссворд "футбол" с анимацией процесса решения кроссворда

Японская головоломка (также японский кроссворд, японское рисование, нонограмма) — головоломка, в которой, в отличие от обычных кроссвордов, зашифрованы не слова, а изображения.

Описание[править | править вики-текст]

Изображения зашифрованы числами, расположенными слева от строк, а также сверху над столбцами. Количество чисел показывает, сколько групп чёрных (либо своего цвета, для цветных кроссвордов) клеток находятся в соответствующих строке или столбце, а сами числа — сколько слитных клеток содержит каждая из этих групп (например, набор из трёх чисел — 4, 1, и 3 означает, что в этом ряду есть три группы: первая — из четырёх, вторая — из одной, третья — из трёх чёрных клеток). В чёрно-белом кроссворде группы должны быть разделены, как минимум, одной пустой клеткой, в цветном это правило касается только одноцветных групп, а разноцветные группы могут быть расположены вплотную (пустые клетки могут быть и по краям рядов). Необходимо определить размещение групп клеток.

Кроссворд "Зима", имеющий одно решение, недостижимое логическим путем
Оранжевым цветом выделены не просчитываемые логическим путем клетки

Несмотря на большую распространённость, на данный момент нет общего мнения о требованиях, предъявляемых к японским кроссвордам. Основные мнения сводятся к различным сочетаниям следующих утверждений:

  1. Правильно составленная головоломка должна иметь только одно решение.
  2. Размер кроссворда (по ширине и высоте) должен быть кратен 5 (чтобы вспомогательная сетка смогла разделить поле на блоки 5х5).
  3. Количество используемых цветов в цветном японском кроссворде должно быть ограничено, а сами цвета должны быть легко отличимы друг от друга.
  4. Фоновый цвет (цвет пустых клеток игрового поля) японского кроссворда должен быть белым.
  5. Кроссворд должен иметь решение, достижимое логическим путём. Кроссворд, который имеет одно решение, достичь которое можно только методом перебора - не может являться кроссвордом (из-за астрономического количества комбинаций, которые человек перебрать не в состоянии).
  6. Недопустимо наличие строк и столбцов без закрашиваемых клеток (и соответственно, без цифр).
  7. Недопустимо наличие строк и столбцов, в которых "нечего разгадывать" (обычно под этим подразумевают отсутствие одинарных пустых клеток между группами цифр разных цветов, и отсутствие двойных пустых клеток между группами одного цвета. В этом случае группы цифр имеют единственный вариант расположения, т.к. они занимают все свободное пространство).

История[править | править вики-текст]

Японские головоломки появилась в Японии в конце XX века, на их авторство претендуют два человека.

Одна из них — Нон Исида (яп. 石田 のん), иллюстратор и графический редактор, утверждавшая, что ещё в 1970 году она создавала нонограммы как средство общения между людьми и животными. Нон Исида верила, что животные очень разумные существа, но из-за отсутствия средств коммуникации между людьми и животными, человек недооценивает земных существ. В результате её научной работы, по утверждению Исиды, родились нонограммы (Nonogram) (NON + diaGRAM) — поля с чёрными и белыми квадратами.

В 1987 году Нон Исида приняла участие в конкурсе рисунков окнами Window Art. Участникам необходимо было создать рисунок на небоскребе с помощью окон, включать или выключать в комнатах свет. Ночью были подведены итоги, и работа Исиды заняла первое место. Сказка о бамбуковом резчике — это японская легенда VIII века, ставшая первой нонограммой, которую увидела многочисленная публика.

В 1988 году вдохновлённая победой в конкурсе рисунков окнами Нон Исида публикует в Японии три головоломки под названием «Window Art Puzzles».

В то же время японский автор головоломок Тэцуя Нисио (яп. 西尾 徹也) придумывает головоломки «Рисование по числам» (Paint by Numbers) и публикует их в другом издании.

Первоначально нонограммы не вызвали особого интереса у любителей головоломок, так как никто не понимал, что из себя представляет эта головоломка, как её разгадывать.

Широкую известность японские головоломки получили в 19891990 годах после публикации в британской газете The Telegraph, Джеймс Делгети, известный британский любитель головоломок, убедил руководство газеты еженедельно публиковать японские головоломки. Вскоре о нонограммах или гриддлерах (Griddlers) узнали и в России, здесь они получили название «японские кроссворды» или «японские головоломки».

Методика решения[править | править вики-текст]

Алгоритм решения японского кроссворда на примере показанного ниже узора «сердце» таков. Легче всего начинать с тех строчек, которые окажутся закрашенными полностью. В нашем примере только три таких строчки по 9 клеточек (рис. 1).

Теперь обратим внимание на вторую строчку, состоящую из двух групп по 4 клеточки. В данном случае пробел между группами окажется в 5 столбце. После этого в 1 и 9 столбике у нас оказываются закрашенными по 4 клеточки, что и нужно по условиям.

Все остальные клеточки в данных столбцах точно оказываются не закрашенными. Их мы отмечаем крестиками (рис. 2). Далее в строчке с числом 7 мы закрашиваем все семь оставшихся клеточек. В среднем столбике образовалось начало группы — 4 из 7 требуемых по условию. Завершаем и эту группу.

Опять же, в строчке с числом 1 — клеточка уже есть, а все остальные отмечаем крестиком. В строчке с числом 3 обязательно остаются свободными вторая и восьмая клеточка, а в строчке с группами 2-2 точно будут закрашены третья и седьмая клеточки (рис. 3).

Далее завершаем 3 и 7 столбики, соединяем между собой три клеточки из строчки с числом 5, закрашиваем две оставшихся клеточки в строке с числом 3. Теперь осталось только закрасить первые клеточки во втором и восьмом столбце, и рисунок готов (рис. 4).

«Сердце» (пример)[править | править вики-текст]

Компьютерное решение[править | править вики-текст]

Японский кроссворд — NP-полная задача, не существует её решения за полиномиальное время, если P≠NP.

Однако, если к японским кроссвордам относить только кроссворды "имеющие одно решение, достижимое только логическим путем", то такие кроссворды к NP-полным задачам относить нельзя, т.к. в любой момент времени при разгадывании кроссворда, у нас есть информация, однозначно указывающая, какие клетки можно открыть далее. По сути, все методы разгадывания кроссвордов, применяемые человеком (за исключением метода "проб и ошибок"[1]), основываются именно на этом.

В простейшем виде (квадрат 8×8) японский кроссворд предлагался в 1992 году участникам международной олимпиады по информатике (IOI) под названием «острова в море».


Цветные японские кроссворды[править | править вики-текст]

Главное отличие цветных японских головоломок от черно-белых — наличие двух и более цветов клеток (цвет фона как отдельный цвет не учитывается), что в свою очередь вносит одно существенное отличие в решение головоломки. Надо помнить, что в цветной головоломке между группами клеток разного цвета может и не быть белых клеток.

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

Также, в особо сложных цветных кроссвордах дополнительно нужно учитывать цвета на пересечении клеток.

В остальном же решение основывается на тех же принципах, что и у черно-белых головоломок:

  • определение областей гарантированно закрашенных клеток;
  • определение областей, гарантированно не содержащих закрашенных клеток.

Следует заметить, что цветные японские кроссворды, в основном, решать гораздо легче, нежели черно-белые

Примечания[править | править вики-текст]

  1. Метод "проб и ошибок" предназначен именно для кроссвордов, которые не относятся к группе "имеющие одно решение, достижимое только логическим путем", а следовательно могут не содержать информацию, однозначно указывающую на открываемые клетки в следующем ходе

См. также[править | править вики-текст]