 | Эту статью следует викифицировать. |
Японская головоломка (также японский кроссворд, японское рисование, нонограмма) — головоломка, в которой, в отличие от обычных кроссвордов, зашифрованы не слова, а изображения.
Описание
 | В этом разделе не хватает ссылок на источники информации. |
Изображения зашифрованы числами, расположенными слева от строк, а также сверху над столбцами. Количество чисел показывает, сколько групп чёрных (либо своего цвета, для цветных кроссвордов) клеток находятся в соответствующих строке или столбце, а сами числа — сколько слитных клеток содержит каждая из этих групп (например, набор из трёх чисел — 4, 1, и 3 означает, что в этом ряду есть три группы: первая — из четырёх, вторая — из одной, третья — из трёх чёрных клеток). В чёрно-белом кроссворде группы должны быть разделены, как минимум, одной пустой клеткой, в цветном это правило касается только одноцветных групп, а разноцветные группы могут быть расположены вплотную (пустые клетки могут быть и по краям рядов). Необходимо определить размещение групп клеток.
Несмотря на большую распространённость, на данный момент нет общего мнения о требованиях, предъявляемых к японским кроссвордам. Основные мнения сводятся к различным сочетаниям следующих утверждений:
- Правильно составленная головоломка должна иметь только одно решение.
- Размер кроссворда (по ширине и высоте) должен быть кратен 5 (чтобы вспомогательная сетка смогла разделить поле на блоки 5х5).
- Количество используемых цветов в цветном японском кроссворде должно быть ограничено, а сами цвета должны быть легко отличимы друг от друга.
- Фоновый цвет (цвет пустых клеток игрового поля) японского кроссворда должен быть белым.
- Кроссворд должен иметь решение, достижимое логическим путём (при этом нет четкого определения, какие из методов решения относить к данной категории). Кроссворд, который имеет одно решение, достичь которое можно только методом перебора, не считается японским кроссвордом (из-за астрономического количества комбинаций, которые человек перебрать не в состоянии).
- Недопустимо наличие строк и столбцов без закрашиваемых клеток (и соответственно, без цифр).
- Недопустимо наличие строк и столбцов, в которых «нечего разгадывать» (обычно под этим подразумевают отсутствие одинарных пустых клеток между группами цифр разных цветов, и отсутствие двойных пустых клеток между группами одного цвета. В этом случае группы цифр имеют единственный вариант расположения, так как они занимают все свободное пространство).
История
| В этом разделе не хватает ссылок на источники информации. |
Японские головоломки появилась в Японии в конце XX века, на их авторство претендуют два человека.
Одна из них — Нон Исида (яп. 石田 のん), иллюстратор и графический редактор, утверждавшая, что ещё в 1970 году она создавала нонограммы как средство общения между людьми и животными. Нон Исида верила, что животные очень разумные существа, но из-за отсутствия средств коммуникации между людьми и животными человек недооценивает земных существ. В результате её научной работы, по утверждению Исиды, родились нонограммы (Nonogram) (NON + diaGRAM) — поля с чёрными и белыми квадратами.
В 1987 году Нон Исида приняла участие в конкурсе рисунков окнами Window Art. Участникам необходимо было создать рисунок на небоскребе с помощью окон, включать или выключать в комнатах свет. Ночью были подведены итоги, и работа Исиды заняла первое место. Сказка о бамбуковом резчике — это японская легенда VIII века, ставшая первой нонограммой, которую увидела многочисленная публика.
В 1988 году вдохновлённая победой в конкурсе рисунков окнами Нон Исида публикует в Японии три головоломки под названием «Window Art Puzzles».
В то же время японский автор головоломок Тэцуя Нисио (яп. 西尾 徹也) придумывает головоломки «Рисование по числам» (Paint by Numbers) и публикует их в другом издании.
Первоначально нонограммы не вызвали особого интереса у любителей головоломок, так как никто не понимал, что из себя представляет эта головоломка, как её разгадывать.
Широкую известность японские головоломки получили в 1989—1990 годах после публикации в британской газете The Telegraph, Джеймс Делгети, известный британский любитель головоломок, убедил руководство газеты еженедельно публиковать японские головоломки. Вскоре о нонограммах или гриддлерах (Griddlers) узнали и в России, здесь они получили название «японские кроссворды» или «японские головоломки».
Методика решения
| В этом разделе не хватает ссылок на источники информации. |
Алгоритм решения японского кроссворда на примере показанного ниже узора «сердце» таков. Легче всего начинать с тех строчек, которые окажутся закрашенными. В нашем примере только три таких строчки по 9 клеток (рис. 1).
Вторая строчка состоит из двух групп по 4 клетки. В данном случае пробел между группами окажется в 5 столбце. После этого в 1 и 9 столбике оказываются закрашенными по 4 клетки, что и нужно по условиям.
Все остальные клетки в данных столбцах точно оказываются закрашенными. Они отмечаются крестиками (рис. 2). Далее в строчке с числом 7 закрашиваются все семь оставшихся клеточек. В среднем столбике образовалось начало группы — 4 из 7 требуемых по условию. Завершается и эта группа.
В строчке с числом 1 — клетка уже есть, а все остальные отмечаются крестиком. В строчке с числом 3 обязательно остаются свободными вторая и восьмая клетка, а в строчке с группами 2-2 точно будут закрашены третья и седьмая клетки (рис. 3).
Далее завершаются 3 и 7 столбики, соединяются между собой три клетки из строчки с числом 5, закрашиваются две оставшихся клеточки в строке с числом 3. Остаётся закрасить первые клетки во втором и восьмом столбце (рис. 4).
«Сердце» (пример)
Рис. 1
Рис. 2
Рис. 3
Рис. 4
Компьютерное решение
Японский кроссворд — NP-полная задача, не существует её решения за полиномиальное время, если P≠NP.
Однако, если к японским кроссвордам относить только кроссворды «имеющие одно решение, достижимое только логическим путем», то такие кроссворды к NP-полным задачам относить нельзя, так как в любой момент времени при разгадывании кроссворда, у нас есть информация, однозначно указывающая, какие клетки можно открыть далее. По сути, все методы разгадывания кроссвордов, применяемые человеком (за исключением метода «проб и ошибок»[2]), основываются именно на этом.
В простейшем виде (квадрат 8×8) японский кроссворд предлагался в 1992 году участникам международной олимпиады по информатике (IOI) под названием «острова в море».
 | Этот раздел не завершён. |
Цветные японские кроссворды
| В этом разделе не хватает ссылок на источники информации. |
Главное отличие цветных японских головоломок от черно-белых — наличие двух и более цветов клеток (цвет фона как отдельный цвет не учитывается), что в свою очередь вносит одно существенное отличие в решение головоломки. Надо помнить, что в цветной головоломке между группами клеток разного цвета может и не быть белых клеток.
Соответственно, если в черно-белой головоломке при решении исходят из того, что группа закрашенных клеток обязательно отделена от другой хотя бы одной незакрашенной клеткой и учитывают её при подсчетах, то в цветной так сделать нельзя, так как группы клеток могут располагаться вплотную друг к другу.
Также, в особо сложных цветных кроссвордах дополнительно нужно учитывать цвета на пересечении клеток.
В остальном же решение основывается на тех же принципах, что и у черно-белых головоломок:
- определение областей гарантированно закрашенных клеток;
- определение областей, гарантированно не содержащих закрашенных клеток.
Цветные японские кроссворды, в основном, решать гораздо легче, нежели чёрно-белые.
Примечания
- 1 2 Под «логическим путём» подразумеваются любые методы решения японских кроссвордов, за исключением метода «проб и ошибок»
- ↑ Метод «проб и ошибок» предназначен именно для кроссвордов, которые не относятся к группе «имеющие одно решение, достижимое только логическим путем», а следовательно могут не содержать информацию, однозначно указывающую на открываемые клетки в следующем ходе
Ссылки
 Компания Nikoli | |
|---|---|
| Персоналии | |
| Головоломки | |
| В этой статье не хватает ссылок на источники информации. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .