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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Paint by numbers Animation.gif

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

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

Изображения зашифрованы числами, расположенными слева от строк, а также сверху над столбцами. Числа показывают, сколько групп чёрных (либо своего цвета, для цветных кроссвордов) клеток находятся в соответствующих строке или столбце и сколько слитных клеток содержит каждая из этих групп (например, набор чисел 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 строк и 9 столбцов. Числа слева и сверху означают количество заштрихованных клеток. Заштрихованные клетки будем обозначать квадратом чёрного цвета, а пустое поле — точкой. Для удобства, числа после определения их местоположения будем вычёркивать.

Обратим внимание на столбцы, где числа выделены красными кружками. Число 3 означает, что в столбце заштриховано 3 подряд клетки, а это значит, что они задают однозначное место положения заштрихованных клеток, так как у нас всего три строчки. Заштрихуем их.

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

Обратим внимание на столбцы 1-й и 7-й, а также на 2-ю строку. В них есть группы заштрихованных клеток длиной в одну клетку. Поэтому после заштрихованной клетки мы ставим одну пустую. В 3-м и 9-м столбцах уже определены заштрихованные клетки, значит все остальные клетки в этих столбцах пустые. Обозначим их.

Во 2-й строке осталась не определена группа из трёх заштрихованных клеток. Она как раз поместилась в пустую неопределённую область. Заштрихуем эту область.

Выделенные группы клеток уже определены, отметим пустые клетки. Теперь можно сказать об однозначном местоположении выделенных групп. В результате всех этих действий получена картинка. Кроссворд решён.

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

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

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

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


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

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

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

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

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

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

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