Головоломки: японские кроссворды
Содержание
- 1. Описание
- 2. История
- 3. Методика решения
- 4. Компьютерное решение
- 5. Цветные японские кроссворды
- 6. "Сердце" пример
- Список использованных источников
Почему я выбрала в качестве темы индивидуального раздела именно японские кроссворды? Потому что мне очень нравится их разгадывать, когда, черкая клеточки, ты в предвкушении того, что же в конце концов получится, какой очередной рисунок выйдет из цифорок и клеточек...А все началось с поездки в поезде в оздоровительный лагерь в Крыму. Подруга с энтузиазмом разгадывала тогда еще не известные мне японские кроссворды и я попросила ее научить меня этой штуковине. И с тех пор я с ними не расстаюсь. А что, собственно, представляют они из себя, думаю, каждый знает, но тем не менее, опишу здесь.
Описание
Японская головоломка (также японский кроссворд, японское рисование, нонограмма) — головоломка, в которой, в отличие от обычных кроссвордов, зашифрованы не слова, а изображения
Изображения зашифрованы числами, расположенными слева от строк, а также сверху над столбцами. Числа показывают, сколько групп чёрных (либо своего цвета, для цветных кроссвордов) клеток находятся в соответствующих строке или столбце и сколько слитных клеток содержит каждая из этих групп (например, набор чисел 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-й строке осталась не определена группа из трёх заштрихованных клеток. Она как раз поместилась в пустую неопределённую область. Заштрихуем эту область. Выделенные группы клеток уже определены, отметим пустые клетки. Теперь можно сказать об однозначном местоположении выделенных групп. В результате всех этих действий получена картинка. Кроссворд решён.
Компьютерное решение
Японский кроссворд — NP-полная задача, не существует её решения за полиномиальное время. В простейшем виде (квадрат 8?8) японский кроссворд предлагался в 1992-ом году участникам международной олимпиады по информатике (IOI) под названием «острова в море»На данный момент существует огромное количество сайтов и программ, предлагающих провести досуг за решением японских кроссвордов. Полезные ссылки приведены ниже.
Цветные японские кроссворды
Главное отличие цветных японских головоломок от черно-белых — наличие трёх и более цветов клеток, что в свою очередь вносит одно существенное отличие в решение головоломки. Надо помнить, что в цветной головоломке между группами клеток разного цвета может и не быть белых клеток. Соответственно, если в черно-белой головоломке при решении исходят из того, что группа закрашенных клеток обязательно отделена от другой хотя бы одной незакрашенной клеткой и учитывают её при подсчетах, то в цветной так сделать нельзя, так как группы клеток могут располагаться вплотную друг к другу. В остальном же решение основывается на тех же принципах, что и у черно-белых головоломок:
- определение областей гарантированно закрашенных клеток
- определение областей, гарантированно не содержащих закрашенных клеток.
"Сердце" пример
Онлайн решение японских кроссвордов
Описание: Онлайн решение японских кроссвордов
Описание: Онлайн решение японских кроссвордов1
Описание: Онлайн решение японских кроссвордов2
Описание: Онлайн решение японских кроссвордов3
Описание: Онлайн решение японских кроссвордов4
Описание: Онлайн решение японских кроссвордов5
Японские кроссворды для Android и IOS
Описание: Японские кроссворды для Android и IOS1
Описание: Японские кроссворды для Android и IOS2
Описание: Японские кроссворды для Android и IOS3
Описание: Японские кроссворды для Android и IOS4
Источник
Описание: Определение японских кроссвордов