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

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

Описание

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

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

Широкую известность японские головоломки получили в 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-полным задачам относить нельзя, т.к. в любой момент времени при разгадывании кроссворда, у нас есть информация, однозначно указывающая, какие клетки можно открыть далее. По сути, все методы разгадывания кроссвордов, применяемые человеком (за исключением метода "проб и ошибок"), основываются именно на этом.

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

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

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

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

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

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

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

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

См. также

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

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Японский кроссворд

– Вас заставят плясать, как при Суворове вы плясали (on vous fera danser [вас заставят плясать]), – сказал Долохов.
– Qu'est ce qu'il chante? [Что он там поет?] – сказал один француз.
– De l'histoire ancienne, [Древняя история,] – сказал другой, догадавшись, что дело шло о прежних войнах. – L'Empereur va lui faire voir a votre Souvara, comme aux autres… [Император покажет вашему Сувара, как и другим…]
– Бонапарте… – начал было Долохов, но француз перебил его.
– Нет Бонапарте. Есть император! Sacre nom… [Чорт возьми…] – сердито крикнул он.
– Чорт его дери вашего императора!
И Долохов по русски, грубо, по солдатски обругался и, вскинув ружье, отошел прочь.
– Пойдемте, Иван Лукич, – сказал он ротному.
– Вот так по хранцузски, – заговорили солдаты в цепи. – Ну ка ты, Сидоров!
Сидоров подмигнул и, обращаясь к французам, начал часто, часто лепетать непонятные слова:
– Кари, мала, тафа, сафи, мутер, каска, – лопотал он, стараясь придавать выразительные интонации своему голосу.
– Го, го, го! ха ха, ха, ха! Ух! Ух! – раздался между солдатами грохот такого здорового и веселого хохота, невольно через цепь сообщившегося и французам, что после этого нужно было, казалось, разрядить ружья, взорвать заряды и разойтись поскорее всем по домам.
Но ружья остались заряжены, бойницы в домах и укреплениях так же грозно смотрели вперед и так же, как прежде, остались друг против друга обращенные, снятые с передков пушки.


Объехав всю линию войск от правого до левого фланга, князь Андрей поднялся на ту батарею, с которой, по словам штаб офицера, всё поле было видно. Здесь он слез с лошади и остановился у крайнего из четырех снятых с передков орудий. Впереди орудий ходил часовой артиллерист, вытянувшийся было перед офицером, но по сделанному ему знаку возобновивший свое равномерное, скучливое хождение. Сзади орудий стояли передки, еще сзади коновязь и костры артиллеристов. Налево, недалеко от крайнего орудия, был новый плетеный шалашик, из которого слышались оживленные офицерские голоса.
Действительно, с батареи открывался вид почти всего расположения русских войск и большей части неприятеля. Прямо против батареи, на горизонте противоположного бугра, виднелась деревня Шенграбен; левее и правее можно было различить в трех местах, среди дыма их костров, массы французских войск, которых, очевидно, большая часть находилась в самой деревне и за горою. Левее деревни, в дыму, казалось что то похожее на батарею, но простым глазом нельзя было рассмотреть хорошенько. Правый фланг наш располагался на довольно крутом возвышении, которое господствовало над позицией французов. По нем расположена была наша пехота, и на самом краю видны были драгуны. В центре, где и находилась та батарея Тушина, с которой рассматривал позицию князь Андрей, был самый отлогий и прямой спуск и подъем к ручью, отделявшему нас от Шенграбена. Налево войска наши примыкали к лесу, где дымились костры нашей, рубившей дрова, пехоты. Линия французов была шире нашей, и ясно было, что французы легко могли обойти нас с обеих сторон. Сзади нашей позиции был крутой и глубокий овраг, по которому трудно было отступать артиллерии и коннице. Князь Андрей, облокотясь на пушку и достав бумажник, начертил для себя план расположения войск. В двух местах он карандашом поставил заметки, намереваясь сообщить их Багратиону. Он предполагал, во первых, сосредоточить всю артиллерию в центре и, во вторых, кавалерию перевести назад, на ту сторону оврага. Князь Андрей, постоянно находясь при главнокомандующем, следя за движениями масс и общими распоряжениями и постоянно занимаясь историческими описаниями сражений, и в этом предстоящем деле невольно соображал будущий ход военных действий только в общих чертах. Ему представлялись лишь следующего рода крупные случайности: «Ежели неприятель поведет атаку на правый фланг, – говорил он сам себе, – Киевский гренадерский и Подольский егерский должны будут удерживать свою позицию до тех пор, пока резервы центра не подойдут к ним. В этом случае драгуны могут ударить во фланг и опрокинуть их. В случае же атаки на центр, мы выставляем на этом возвышении центральную батарею и под ее прикрытием стягиваем левый фланг и отступаем до оврага эшелонами», рассуждал он сам с собою…
Всё время, что он был на батарее у орудия, он, как это часто бывает, не переставая, слышал звуки голосов офицеров, говоривших в балагане, но не понимал ни одного слова из того, что они говорили. Вдруг звук голосов из балагана поразил его таким задушевным тоном, что он невольно стал прислушиваться.
– Нет, голубчик, – говорил приятный и как будто знакомый князю Андрею голос, – я говорю, что коли бы возможно было знать, что будет после смерти, тогда бы и смерти из нас никто не боялся. Так то, голубчик.
Другой, более молодой голос перебил его:
– Да бойся, не бойся, всё равно, – не минуешь.
– А всё боишься! Эх вы, ученые люди, – сказал третий мужественный голос, перебивая обоих. – То то вы, артиллеристы, и учены очень оттого, что всё с собой свезти можно, и водочки и закусочки.
И владелец мужественного голоса, видимо, пехотный офицер, засмеялся.
– А всё боишься, – продолжал первый знакомый голос. – Боишься неизвестности, вот чего. Как там ни говори, что душа на небо пойдет… ведь это мы знаем, что неба нет, a сфера одна.
Опять мужественный голос перебил артиллериста.
– Ну, угостите же травником то вашим, Тушин, – сказал он.
«А, это тот самый капитан, который без сапог стоял у маркитанта», подумал князь Андрей, с удовольствием признавая приятный философствовавший голос.
– Травничку можно, – сказал Тушин, – а всё таки будущую жизнь постигнуть…
Он не договорил. В это время в воздухе послышался свист; ближе, ближе, быстрее и слышнее, слышнее и быстрее, и ядро, как будто не договорив всего, что нужно было, с нечеловеческою силой взрывая брызги, шлепнулось в землю недалеко от балагана. Земля как будто ахнула от страшного удара.
В то же мгновение из балагана выскочил прежде всех маленький Тушин с закушенною на бок трубочкой; доброе, умное лицо его было несколько бледно. За ним вышел владетель мужественного голоса, молодцоватый пехотный офицер, и побежал к своей роте, на бегу застегиваясь.


Князь Андрей верхом остановился на батарее, глядя на дым орудия, из которого вылетело ядро. Глаза его разбегались по обширному пространству. Он видел только, что прежде неподвижные массы французов заколыхались, и что налево действительно была батарея. На ней еще не разошелся дымок. Французские два конные, вероятно, адъютанта, проскакали по горе. Под гору, вероятно, для усиления цепи, двигалась явственно видневшаяся небольшая колонна неприятеля. Еще дым первого выстрела не рассеялся, как показался другой дымок и выстрел. Сраженье началось. Князь Андрей повернул лошадь и поскакал назад в Грунт отыскивать князя Багратиона. Сзади себя он слышал, как канонада становилась чаще и громче. Видно, наши начинали отвечать. Внизу, в том месте, где проезжали парламентеры, послышались ружейные выстрелы.
Лемарруа (Le Marierois) с грозным письмом Бонапарта только что прискакал к Мюрату, и пристыженный Мюрат, желая загладить свою ошибку, тотчас же двинул свои войска на центр и в обход обоих флангов, надеясь еще до вечера и до прибытия императора раздавить ничтожный, стоявший перед ним, отряд.
«Началось! Вот оно!» думал князь Андрей, чувствуя, как кровь чаще начинала приливать к его сердцу. «Но где же? Как же выразится мой Тулон?» думал он.
Проезжая между тех же рот, которые ели кашу и пили водку четверть часа тому назад, он везде видел одни и те же быстрые движения строившихся и разбиравших ружья солдат, и на всех лицах узнавал он то чувство оживления, которое было в его сердце. «Началось! Вот оно! Страшно и весело!» говорило лицо каждого солдата и офицера.
Не доехав еще до строившегося укрепления, он увидел в вечернем свете пасмурного осеннего дня подвигавшихся ему навстречу верховых. Передовой, в бурке и картузе со смушками, ехал на белой лошади. Это был князь Багратион. Князь Андрей остановился, ожидая его. Князь Багратион приостановил свою лошадь и, узнав князя Андрея, кивнул ему головой. Он продолжал смотреть вперед в то время, как князь Андрей говорил ему то, что он видел.
Выражение: «началось! вот оно!» было даже и на крепком карем лице князя Багратиона с полузакрытыми, мутными, как будто невыспавшимися глазами. Князь Андрей с беспокойным любопытством вглядывался в это неподвижное лицо, и ему хотелось знать, думает ли и чувствует, и что думает, что чувствует этот человек в эту минуту? «Есть ли вообще что нибудь там, за этим неподвижным лицом?» спрашивал себя князь Андрей, глядя на него. Князь Багратион наклонил голову, в знак согласия на слова князя Андрея, и сказал: «Хорошо», с таким выражением, как будто всё то, что происходило и что ему сообщали, было именно то, что он уже предвидел. Князь Андрей, запихавшись от быстроты езды, говорил быстро. Князь Багратион произносил слова с своим восточным акцентом особенно медленно, как бы внушая, что торопиться некуда. Он тронул, однако, рысью свою лошадь по направлению к батарее Тушина. Князь Андрей вместе с свитой поехал за ним. За князем Багратионом ехали: свитский офицер, личный адъютант князя, Жерков, ординарец, дежурный штаб офицер на энглизированной красивой лошади и статский чиновник, аудитор, который из любопытства попросился ехать в сражение. Аудитор, полный мужчина с полным лицом, с наивною улыбкой радости оглядывался вокруг, трясясь на своей лошади, представляя странный вид в своей камлотовой шинели на фурштатском седле среди гусар, казаков и адъютантов.