Передовые методы решения японских кроссвордов. Как разгадывать японские кроссворды Как гадать японские кроссворды

Вы заметили, что в последнее время многие вокруг вас стали разгадывать не обычные, а японские кроссворды? И этому есть объяснение. Обычные кроссворды и их облегченная версия - сканворды уже давно не заставляют напрягать интеллект. Из газеты в газету кочуют одни и те же формулировки типа «попугай из 3 букв» или «одежда для стен». Скучно…

А чем же хороши «японцы»? О, это совсем другой уровень, каждое задание уникально, а в результате вы получаете моральное удовлетворение не от того, что вспомнили все известные вам слова, а от того, что увидели нарисованную вами самими картинку, причем, чем сложнее кроссворд, тем подробнее будут прорисованы все ее детали.

Правила решения таких кроссвордов не сложные. Давайте учиться? Итак…

Японский кроссворд представляет собой картинку, зашифрованную с помощью цифр. Цифры напротив каждой строки (столбца) обозначают количество закрашенных клеток в этой строке (столбце). Если подряд записано более одного числа, то это означает, что в этой строке (столбце) располагаются несколько групп закрашенных клеток, между которыми находится как минимум одна незакрашенная клетка. Порядок цифр совпадает с порядком расположения закрашенных групп. Ваша цель - определить место всех групп цифр на поле и в результате получить рисунок. Решение у кроссворда может быть только одно, поэтому, если что-то не сходится - возвращаемся на шаг назад и внимательно проверяем все свои шаги. Вот и все правила.

Вроде бы все просто. Но на практике возникает много вопросов. В журналах и газетах, публикующих японские кроссворды, в качестве примера приводятся очень примитивные картинки. И часто так случается, что самостоятельно не выходит разгадать ни один из предложенных вариантов. Поэтому я предлагаю начать учиться на примере более сложной картинки, например, размером 15×15 клеток.

1. Начинаем с поиска самой большой цифры, или группы цифр. Это строка с цифрой 14.
Отсчитываем слева направо 14 клеток и ставим точку. Повторяем отсчет справа налево и тоже ставим точку. Соединяем их и закрашиваем всю группу. У нас получилось 13 закрашенных клеток. Где будет находиться 14-я клетка - справа или слева - мы пока не знаем.

2. Повторяем отсчет для строки с цифрой 9 , так же слева направо и наоборот. Закрашиваем 3 клетки:

3. Теперь давайте рассмотрим самую нижнюю строку с цифрами 8 и 4. Эта запись означает, что в этой строке расположена группа в 8 клеток, затем промежуток минимум в одну клетку, и группа из 4 клеток. Попробуем их вычислить.

Слева направо отсчитываем 8 клеток, ставим точку, пропускаем одну клетку и продолжаем отсчитывать 4 клетки. Ставим точку. Теперь справа налево: отсчитываем 4 клетки (точка), пропускаем одну и отсчитываем 8 клеток (точка). Соединяем попарно точки, относящиеся к восьмерке и четверке, и получаем группы в 6 и 2 клетки. Закрашиваем их. В какую сторону продолжится каждая из групп, пока неизвестно.
Обратите внимание, что когда мы просчитываем по несколько групп в строке или столбце, то мы пропускаем всегда 1 промежуточную клетку, хотя по завершении разгадывания вы увидите, что их иногда становится больше. Но вот такой механизм подсчета мы будем применять всегда, если хотим, чтобы все получилось. Поехали дальше.

4. Такой же алгоритм подсчета применяем к строке «4 — 7». У вас должны получиться группы из одной и четырех клеток - это кусочки от 4 и 7 соответственно.

5. Теперь посмотрим общую картинку:

Обратите внимание на столбцы. Многие из них заканчиваются цифрой 1. Это значит, что самая нижняя группа клеток в этих столбцах равна единице. Поэтому в строке «8 — 4» смело можно отметить те «единицы», которые автоматически у нас вырисовались, и «двойки», которые можно смело дорисовать. При этом мы вспоминаем, что между группами цифр должна быть как минимум 1 незакрашенная клетка и договариваемся, что такие клетки мы будем помечать крестиками. Такие клетки ни при каких условиях закрашиваться не будут

6. Дальше давайте самостоятельно:
— столбец»2-1-6-2» — после нижней «двойки» идет «шестерка». Отсчитываем 6 клеток и закрашиваем ее полностью. Тут все сложилось само собой. В конце группы не забываем ставить крестик;
— столбец «1-3-5-2» — то же самое проделываем с «пятеркой»;
— строка «9» — у нас есть две закрашенные клетки ближе к правому краю. Оттуда и считаем 9 клеток, ставим точку и соединяем ее с группой из 2 клеток. Закрасим и увидим, что у нас есть 7 из 9 закрашенных клеток. Поскольку в этой строке у нас только одна группа, то от ее предполагаемого левого края оставляем свободными 2 клетки, а остальные помечаем крестиками. Там в любом случае ничего не будет;
— проверяем вертикаль и замечаем появившиеся «тройки» (столбцы «1-1-3-1», «1-3-1-3-1» и «2-1-2-3-1»), закрашиваем их и не забываем отделять их крестиками;
— в строке «1-6» пересчитываем «шестерку»: справа налево отсчитаем шесть клеток (точка) и от крестика слева направо также 6 клеток и ставим точку. Соединям, 5 из 6 клеток закрашиваем. На «единицу» в этой строке пока внимания не обращаем;
— так же пересчитываем строку «7-1», в итоге 6 из 7 клеток закрашиваем;
— проделайте те же действия со строками «1-5» и «7»;
— затем проверьте вертикали и дорисуйте группы, которые начинаются сразу после крестиков. После каждого хода проверяйте, как изменяется картинка, дорисовывайте появившиеся позиции.У вас должна получиться вот такая промежуточная картинка:

В процессе разгадывания рассуждайте логически. Если в строке «1-6» для единицы остается одна-единственная позиция, то она же является и частью «двойки» из первого столбца. Поэтому оставьте место для завершения «двойки», а остальной столбец отметьте крестиками. Теперь можно закончить строку «14» и еще раз пересчитать строки и столбцы, отмечая крестиками те позиции, где ну никак не могут быть закрашенные клетки. Дорисуйте строку «4-1-1», пересчитайте столбцы «1-3-5-2» и «1-3-1-3-1», а дальше рассуждайте логически и будьте внимательны, все клетки будут вырисовываться с каждым следующим шагом. В результате у нас получился рисунок мышонка в ботинке.

Я поздравляю вас с первым успехом!
Надеюсь, что вам понравилось и вы пополните наши ряды любителей японских кроссвордов!

В японских головоломках, в отличие от других кроссвордов, зашифрованы не слова, а изображения. При решении необходимо восстановить картинку по числам, которые проставлены слева от строк над колонками. Числа в сетке японского кроссворда показывают, сколько групп черных клеток находится в соответствующей строке или колонке и сколько слитных черных клеток содержит каждая группа.

Например, набор чисел 4, 1, и 3 в сетке японского кроссворда означает, что в этом ряду есть три группы: первая — из четырех, вторая — из одной, третья — из трех черных клеток. Группы разделены как минимум одной пустой клеткой. Пустые клетки могут быть и по краям рядов. При решении японского кроссворда необходимо определить размещение этих групп клеток.

А теперь на простом примере рассмотрим, как решать японские кроссворды.

Алгоритм решения японского кроссворда таков. Легче всего начинать разгадывать японский кроссворд с тех строчек, которые окажутся закрашенными полностью. В нашем примере только три таких строчки по 9 клеточек (рис. 1).

Теперь обратим внимание на вторую строчку, состоящую из двух групп по 4 клеточки. В данном случае пробел между группами окажется в 5 столбце. После этого в 1 и 9 столбике японского кроссворда у нас оказываются закрашенными по 4 клеточки, что и нужно по условиям.

Все остальные клеточки в данных столбцах японского кроссворда точно оказываются не закрашенными. Их мы отмечаем крестиками (рис. 2). Далее в строчке с числом 7 мы закрашиваем все семь оставшихся клеточек. В среднем столбике образовалось начало группы — 4 из 7 требуемых по условию. Завершаем и эту группу.

Продолжая решение японского кроссворда, заметим, что в строчке с числом 1 клеточка уже есть; все остальные отмечаем крестиком. В нашем японском кроссворде в строчке с числом 3 обязательно остаются свободными вторая и восьмая клеточка, а в строчке с группами 2-2 точно будут закрашены третья и седьмая клеточки (рис. 3).

Далее завершаем 3 и 7 столбики, соединяем между собой три клеточки из строчки с числом 5, закрашиваем две оставшихся клеточки в строке с числом 3. Теперь осталось только закрасить первые клеточки во втором и восьмом столбце, и рисунок японского кроссворда готов (рис. 4).

Желаем удачи в решении японских кроссвордов!

Изображения в японском кроссворде зашифрованы с помощью чисел. Числа расположены слева и сверху от основного игрового поля. Числа показывают сколько ячеек надо закрасить.

В черно-белых кроссвордах используется два цвета: белый - это цвет основного игрового поля и черный - это цвет, которым игрок закрашивает ячейки. Закрашенные ячейки должны быть отделены как минимум одной незакрашенной ячейкой. Для удобства, игровое поле разделено на блоки 5 на 5 жирной линией.

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

Числа слева от игрового поля, показывают сколько закрашенных ячеек должно быть в каждой строке.

Основные требования к японскому кроссворду:

Кроссворд должен иметь только 1 решение, т.е. все закрашиваемые ячейки можно просчитать логическим путем.
Количество строк и столбцов должно быть кратно 5
Не должно быть строк и столбцов с пустыми ячейками.

Основные шаги для решения

При решении кроссворда вам необходимо:

Найти ячейки, которые точно будут закрашены
Найти ячейки, которые точно не будут закрашены
Закрасить ячейки, положение чисел которых точно известно

Пример решения японского кроссворда

Давайте попробуем решить простой японский кроссворд «Письмо» :

Размер кроссворда 10 на 7. Давайте попробуем разгадать его.

Для начала найдем все ячейки. В первой и последней строке есть число 10, значит вся строка будет закрашена полностью. Также в первом и последнем столбце есть число 7, значит весь столбец будет закрашен полностью. Давайте закрасим эти строки и столбцы и зачеркнем соответствующие числа.

Теперь внимательно посмотрим на вторую и 6 строку. У этих чисел есть начальные и конечные закрашенные ячейки. Соответственно, мы их можем продолжить или завершить.

Теперь давайте отметим крестиками те ячейки, где точно не могут быть закрашены

Посмотрите на 3 и седьмую строки. Т.к. между закрашенными ячейками должна быть одна пустая ячейка и есть первые две закрашенные клетки, мы можем закрасить остальные

Факультет компьютерных наук и технологий

Кафедра программной инженерии

Специальность Программная инженерия

Японские кроссворды. Алгоритм решения

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

Среди магистров нашего университета есть несколько людей, которые осветили эту тему в своём индивидуальном разделе [ , ]. Причём Нина Авджи сделала это очень хорошо, рассказав об общем описании кроссвордов, истории их возникновения, общей методике и принципах решения. Она также осветила особенности чёрно-белых и цветных кроссвордов. Однако сам алгоритм решения и методы не были описаны в подробностях, поэтому в данном разделе я хочу их описать формализовано, в таком виде, в котором их можно будет использовать для написания программы для решения японских кроссвордов как человек.

Проектирование программной модели

Для того, чтобы подробно описать алгоритм решения японских кроссвордов сначала нужно вкратце описать программную модель и порядок её работы. Японский кроссворд состоит из основного поля, на котором расположены клетки, которые могут иметь 3 состояния: заполнена, пустая и неопределённая. Данное поле разделено на строки и столбцы, рядом с которыми есть числа, указывающие на количество клеток, которые должны быть закрашены. Исходя из этого была разработана диаграмма классов, представленная на рисунке 1.

Рисунок 1 - Диаграмма классов

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

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

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

Исходный код программы можно получить в .

Метод Пересечение крайних границ

Анализируется каждая числовая группа в линии и находятся крайняя правая и крайняя левая границы числовой группы. Если разница между правой и левой границами больше или равна нулю , то можно заполнить клетки, находящиеся между ними (включительно). Стоит отметить, что, как видно из рисунка, в итоговой линии закрашиваются группы, которые пересекаются только сами с собой, поэтому клетка №6 не закрашена, так как в разных позициях (левой и правой) она принадлежит разным числовым группам.

Рисунок 2 - Пример анализа линии, используя пересечения крайних границ

Метод Отталкивание от стен

Анализируются крайние непустые промежутки. Если на расстоянии в числовую группу с края есть закрашенные клетки, то можно закрасить клетки, начиная с закрашенной и до клетки, равной величине числовой группы .

В случае, если количество закрашенных клеток равно величине числовой группы, то числовую группу можно вычеркнуть, а после группы вычеркнуть клетку (минимальное место между группами клеток).

Рисунок 3 - Пример анализа линии, используя отталкивания от стен

Метод Недосягаемость

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

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

Наложение крайних позиций

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

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

Отталкивание от стен

Если в строке имеется закрашенная клетка, расстояние от которой до левой границы кроссворда меньше, чем значение первой цифры - значит можно закрасить несколько клеток справа. Для этого отсчитаем значение первой цифры от левой границы кроссворда - все клетки, которые окажутся справа от разгаданной, закрашиваем. Аналогичный метод работает для последней цифры и правой границы кроссворда - можно закрасить клетки слева от разгаданной.

Недосягаемость

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

Не помещается

Бывают ситуации, когда в строке появляются ограниченные крестиками области, в которые не может поместится ни одна цифра из заявленных. Соответственно, такие области заполняются крестиками. Аналогично поступаем, когда эта область формируется в начале/конце строки, и в ней не помещается первая/последняя цифра.

Разделение

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

Объединение

Если в строке имеются некоторые закрашенные клетки, которые явно относятся к одной и той же цифре, то пространство между этими клетками закрашивается.

Двойственное положение

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

И закрашиваем те клетки, которые в обоих вариантах расположения являются закрашенными.

Цвета на пересечении

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

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