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

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

Кроссворд «Зима», имеющий одно решение, недостижимое логическим путём[1]

Оранжевым цветом выделены не просчитываемые логическим путём клетки[1]

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

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

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

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

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

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

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

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

Широкую известность японские головоломки получили в 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).

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

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

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

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

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

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

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

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

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

• Методы решения японских кроссвордов