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

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

Описание

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

История

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

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

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

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

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

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

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

Методика решения

Рассмотрим простой пример, состоящий из 9 строк и 9 столбцов. Числа слева и сверху означают количество заштрихованных клеток. Заштрихованные клетки будем обозначать квадратом чёрного цвета, а пустое поле — точкой. Для удобства, числа после определения их места положения будем вычёркивать.

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

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

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

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

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

«Сердце» (пример)

• 

  Шаг 1

• 

  Шаг 2

• 

  Шаг 3

• 

  Шаг 4

Компьютерное решение

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

В простейшем виде (квадрат 8×8) японский кроссворд предлагался в 1990-е годы^{[уточнить]} участникам международной олимпиады по информатике (IOI) под названием «острова в море».

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Цветные японские кроссворды

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

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

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

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

См. также

• Кроссворд
• Судоку

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 1 сентября 2012.