Учимся разгадывать японские кроссворды . Как обычно на примерах, т.к. по моему – это более наглядно. Так же будут комментарии к рисункам – почему именно так.
Правила разгадывания: цифра - это количество закрашенных клеток в строке или столбце.
Если в строке только одна цифра 8, то значит в этой строке - где-то надо закрасить 8 клеток последовательно без пробелов.
Если в строке несколько цифр, например: 3, 2, 1, то в этом порядке они и будут в строке, однако между соседними цифрами должен быть минимум 1-н пробел (может быть 2 и больше).
Мы имеем право закрашивать клетку только в том, случае, если это однозначное
решение, т.е. иначе просто не влезет.
А теперь ближе к примерам, чтобы это все лучше понималось.
Предлагаю начинать разгадывать японский кроссворд с самых больших цифр, т.к. это наиболее просто. Самой большой у нас является 9, а значит начнем с нее (возьмем любую).
Давайте отсчитаем 9 клеток с левого края от девятки – я выделил это цветом.
А теперь сделаем тоже самое, только с противоположного края – отсчитываем 9 клеток:
А теперь о том, зачем это делаем. Т.к. у нас больше нет никаких цифр в строке с 9, то в ней может быть закрашено только 9 клеток, причем последовательно без перерывов. (напротив строки одна цифра 9).
Наша строка имеет длину 14 клеток. Поэтому мы отмеряем нашу девятку – по минимуму, т.е. с самого начала и по максимуму – с самого конца. Все для того, чтобы найти пересечение. Я закрасил пересечение черным цветом, потому что как бы вы не закрасили 9 клеток последовательно, 4 из них всегда будут закрашены (напомню – всего клеток 14).
После того, как мы закрасили первые 4 клетки строки, давайте взглянем на столбцы, ведь клетки в строках и столбцах пересекаются. Я выделил цифры столбцов, которые совпадают с закрашенными клетками из строки.
Что означает запись 1 1 2 1 1 в строке или столбце? Это означает, что в данном столбце/ строке будет 1 закрашенная клетка, потом промежуток не закрашенный (буду обозначать его “х
”) потом снова 1 закрашенная клетка, потом снова не закрашенный промежуток, потом 2 клетки подряд закрашены и т.д.
Пример возможного (но не факт!!) заполнения столбца №6:
Из этого важно понять – мы можем закрашивать только то, что закрашивается однозначно (как 4 клетки выше). Но так же мы помним, что хотя бы 1-н пробел должен быть между разными закрашиваемыми цифрами . Т.е. после выделенных нами единиц в столбцах будет минимум 1-н пробел – отметим эти пробелы:
Теперь чуточку ускоримся – берем вторую девятку, отмечаем её минимум и максимум, закрашиваем черным пересечение и т.к. в строках у нас единицы – ставим для них минимум один пробел (x).
Как видно пересечение по 8-е дает нам только одну закрашенную клетку.
Но если взглянуть на строку 1 1 (8-я строка)– там всего 2 клетки должны быть закрашены черным.
А ведь нас уже есть 2 клетки, закрашенные в черный в этой строке – одна в начале, другая – в конце, значит все остальные клетки заполняем пробелами (х).
Рассмотрим пятерки в столбцах – напомню, что в столбцах цифры закрашиваются сверху вниз по порядку, а в строках слева на право. Как видим, минимум 1-н пробел сохраняется между единицей и пятеркой столбца.
Ну что ж, давайте пожалуй на этом закончим наше изучение. Очень надеюсь, что суть разгадывания японских кроссвордов вы поняли.
Из комментариев вижу, что не все поняли смысл, поэтому предлагаю так же посмотреть видеоролик, возможно с ним будет более понятно. Ролик для самого начального уровня..
Вы заметили, что в последнее время многие вокруг вас стали разгадывать не обычные, а японские кроссворды? И этому есть объяснение. Обычные кроссворды и их облегченная версия - сканворды уже давно не заставляют напрягать интеллект. Из газеты в газету кочуют одни и те же формулировки типа «попугай из 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 незакрашенная клетка и договариваемся, что такие клетки мы будем помечать крестиками. Такие клетки ни при каких условиях закрашиваться не будут
.jpg)
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», а дальше рассуждайте логически и будьте внимательны, все клетки будут вырисовываться с каждым следующим шагом. В результате у нас получился рисунок мышонка в ботинке.
Я поздравляю вас с первым успехом!
Надеюсь, что вам понравилось и вы пополните наши ряды любителей японских кроссвордов!
В японском кроссворде картинка зашифрована с помощью цифр, расположенных слева и сверху от сетки. Каждая цифра указывает, сколько клеточек подряд нужно закрасить в этой строке или столбце. Рассмотрим конкретный пример решения японского кроссворда:
Сначала нужно найти самые большие числа, которые больше чем половина длины строки или столбца в котором эта цифра находится. В данном примере это 8 и 10 (первая и вторая строка) и 7 (второй и девятый столбец). Вторая строка закрашивается полностью, так как число 10 соответствует длине строки. Для удобства можно отметить эту строку, как отгаданную, для этого кликните на цифре 10, и она станет серого цвета. В первой строке стоит число 8, значит, в любом случае будут закрашены 6 клеточек в центре строки. Это утверждение проверяется следующим образом: предположим, что 8 клеток располагаются вначале строки, тогда в конце строки остаётся 2 не закрашенные клеточки, а теперь предположим что эти 8 клеточек расположены в конце строки, тогда не закрашенными останутся 2 первые клеточки. Значит, оставив по 2 не закрашенных клеточки в начале и конце строки мы учитываем оба случая, и смело закрашиваем оставшиеся клеточки. Тоже самое проделываем со вторым и девятым столбцом, только здесь известно, что вторая клеточка закрашена. i5;оэтому внизу столбца оставляем 3 клеточки не закрашенными, а вверху закрашиваем все клеточки до уже известной второй клетки. Теперь отметим две последние клеточки во втором и девятом столбце крестиками, так как они не могут быть закрашены. Посмотрите сами, закрашены 6 клеточек из 7, значит оставшаяся клеточка будет либо в начале либо в конце этих 6 закрашенных клеточек.
Теперь закрасим клеточки в 3-8 столбцах. В них закрашены первые клеточки, а значит остаётся только закрасить оставшиеся клеточки, в соответствии с самым верхним числом, и поставить в конце крестик, как показано на рисунке ниже.
В третьей и четвёртой строках всё понятно, закрашиваем первую и последнюю клетки. В первом и девятом столбцах зачёркиваем крестиками 5 нижних клеток, так как закрашенных клеточек там быть не может. В шестой и седьмой строках остаётся только ограничить вторые и девятые клеточки крестиками. В десятой строке закрашиваем 2 центральные клеточки, и ограничиваем их сверху крестиками.
Обратим внимание на третий и восьмой столбцы. В них осталось закрасить блок из двух клеточек, поэтому отмечаем крестиком пятые клеточки. Тогда в пятой строке закрашиваем первую и последнюю клеточки. Теперь посмотрим на первый и последний столбцы, в них получились блоки из четырёх закрашенных клеточек, поэтому вычёркиваем первые клеточки в этих столбцах. В первой строке закрашиваем оставшиеся клеточки. Во втором и девятом столбце образовались блоки из семи закрашенных клеточек, поэтому в оставшихся клетках ставим крестики.
В третьем и в восьмом столбцах закрашиваем девятые клеточки. Тогда в девятой строке получилось два блока по одной клеточки, значит помечаем оставшиеся клетки крестиками. В восьмой строке только один вариант расположения блоков, поэтому просто закрашиваем их по порядку. Третий и восьмой столбцы разгаданы, поэтому ставим крестики в последних клеточках. И теперь в последн 77;й строке не остаётся ничего другого как закрасить оставшееся клеточки. В пятом и шестом столбцах закрашиваем пятые клеточки. Тогда пятая строка будет разгадана полностью.
Факультет компьютерных наук и технологий
Кафедра программной инженерии
Специальность Программная инженерия
Японские кроссворды. Алгоритм решения
Сейчас есть очень много разных головоломок, которые позволяют весело и с интересом провести время. Среди них особенно выделяются японские головоломки: какуро, судоку и, конечно, японские кроссворды. Ещё в детстве мне нравилось решать судоку и я всегда смотрел на японские кроссворды, расположенные в тех же журналах, с недоумением. Они для меня были очень сложные и непонятные, хотя я пытался в них разобраться. Так как разобраться у меня не получилось, то я их оставил. И вернулся к ним лет через 10, когда был уже в университете. На летних каникулах было много свободного времени и я решил попробовать разобраться с ними ещё раз и уже в этот раз получилось. С того времени они являются, наверное, самыми любимыми головоломками.
Среди магистров нашего университета есть несколько людей, которые осветили эту тему в своём индивидуальном разделе [ , ]. Причём Нина Авджи сделала это очень хорошо, рассказав об общем описании кроссвордов, истории их возникновения, общей методике и принципах решения. Она также осветила особенности чёрно-белых и цветных кроссвордов. Однако сам алгоритм решения и методы не были описаны в подробностях, поэтому в данном разделе я хочу их описать формализовано, в таком виде, в котором их можно будет использовать для написания программы для решения японских кроссвордов как человек.
Проектирование программной модели
Для того, чтобы подробно описать алгоритм решения японских кроссвордов сначала нужно вкратце описать программную модель и порядок её работы. Японский кроссворд состоит из основного поля, на котором расположены клетки, которые могут иметь 3 состояния: заполнена, пустая и неопределённая. Данное поле разделено на строки и столбцы, рядом с которыми есть числа, указывающие на количество клеток, которые должны быть закрашены. Исходя из этого была разработана диаграмма классов, представленная на рисунке 1.
Рисунок 1 - Диаграмма классов
Алгоритм решения японского кроссворда будет применяться не ко всему кроссворду сразу, а поочерёдно для строк и столбцов, потому что по сути между ними нет существенных отличий. Следовательно, алгоритм решения сводится к анализу одной линии клеток и соответствующих ей чисел, определяющих закраску.
В классе Nonogram есть очередь номеров линий для анализа. После каждого проведённого анализа линии, метод возвращает номера модифицированных ячеек для того, чтобы их можно было бы добавить в очередь на анализ, так как при модификации ячеек могли появиться какие-то изменения, которые продвинули бы решение.
Необходимо отметить, что разработанная программа не реализует все методы решения как челове. Реализованы только методы, работающие с крайними группами и пустыми промежутками. Остальные методы подробно описаны в .
Исходный код программы можно получить в .
Метод Пересечение крайних границ
Анализируется каждая числовая группа в линии и находятся крайняя правая и крайняя левая границы числовой группы. Если разница между правой и левой границами больше или равна нулю , то можно заполнить клетки, находящиеся между ними (включительно). Стоит отметить, что, как видно из рисунка, в итоговой линии закрашиваются группы, которые пересекаются только сами с собой, поэтому клетка №6 не закрашена, так как в разных позициях (левой и правой) она принадлежит разным числовым группам.
Рисунок 2 - Пример анализа линии, используя пересечения крайних границ
Метод Отталкивание от стен
Анализируются крайние непустые промежутки. Если на расстоянии в числовую группу с края есть закрашенные клетки, то можно закрасить клетки, начиная с закрашенной и до клетки, равной величине числовой группы .
В случае, если количество закрашенных клеток равно величине числовой группы, то числовую группу можно вычеркнуть, а после группы вычеркнуть клетку (минимальное место между группами клеток).
Рисунок 3 - Пример анализа линии, используя отталкивания от стен
Метод Недосягаемость
Анализируются крайние числовые группы. Если расстояние от начала неопределённого фрагмента линии до первой заполненной клетки меньше или равно крайней числовой группе, то необходимо вычеркнуть клетки, до которых числовая группа не достаёт .
Также необходимо рассмотреть случай, если в линии находится одна невычеркнутая группа. В таком случае необходимо вычеркнуть все клетки, которые находятся дальше от заполненных клеток на длину числовой группы.
Японский кроссворд (по-другому нонограмма) - это головоломка, в которой, в отличие от обычных кроссвордов, зашифрованы не слова, а изображения.
Подобные нонограммы появилась в Японии в конце XX века и, несмотря на непривычный вид и пугающую на первый взгляд трудность, смогли завоевать популярность у любителей головоломок во всем мире, в том числе и в России.
Правильно разгадать японский кроссворд – значит, восстановить изображение, зашифрованное с помощью цифр. Шифрованным изображением может быть любой объект: транспорт, животное, человек, любые символы. Профессионально составленный кроссворд должен иметь единственное логическое решение без каких-либо вариантов.
Японские кроссворды делятся на два вида - чёрно-белые и цветные. В чёрно-белых кроссвордах изображение содержит соответственных только два цвета: чёрный и белый, причём само изображение может быть как чёрным на белом фоне, так и белым на чёрном. В цветных кроссвордах изображение создается несколькими цветами.
Научиться разгадывать японские кроссворды несложно. Для этого достаточно усвоить алгоритм решения нонограммы на достаточно простом примере, чтобы понять всю суть данной головоломки, а затем можно смело выбирать кроссворды со сложными изображениями.
Поскольку правила решения цветных и чёрно-белых кроссвордов несколько различаются, рассмотрим, прежде всего, особенности составления и решения чёрно-белых кроссвордов.
Для начала обратим внимание на схему подобного кроссворда.
пример разгаданного японского кроссворда
Как видим, поле японского кроссворда расчерчено горизонтальными и вертикальными линиями разной толщины. Самые толстые линии отделяют поле для картинки от цифр. Более тонкими линиями поле делится на группы по 5 клеток (как по горизонтали, так и по вертикали) исключительно для удобства подсчёта.
Само изображение в японском кроссворде формируется путем закрашивания отдельных клеток в чёрный цвет. Не закрашенная клетка при этом считается белой. В процессе решения необходимо восстановить картинку по имеющимся цифрам.
Таким образом, цифры в сетке японского кроссворда слева и сверху означают количество заштрихованных клеток, идущих подряд, без пропусков, по горизонтали и вертикали соответственно. Каждая отдельная цифра обозначает отдельную группу. Например, набор чисел 7, 1 и 2 в сетке японского кроссворда означает, что в этом ряду есть три группы: первая - из семи, вторая - из одной, третья - из двух чёрных клеток. Причём между группами должна быть как минимум одна не закрашенная клетка. Пустые клетки могут быть и по краям рядов. При решении японского кроссворда необходимо определить размещение этих групп клеток.
Начинать разгадывание рекомендуется с нахождения горизонтальных линий или вертикальных столбцов, где можно сделать какой-либо вывод о том, какие клетки закрашены, а какие не закрашены. Эти логические выводы можно отображать специальными пометками, которые помогут получить новые зацепки для разгадывания кроссворда.
ПРИМЕР РЕШЕНИЯ ЯПОНСКОГО КРОССВОРДА:
Рассмотрим простой пример, состоящий из 9 строк и 9 столбцов.
рисунок 1
Заштрихованные клетки будем обозначать квадратом чёрного цвета, а пустое поле - синим крестиком. Для удобства числа после определения их местоположения будем вычёркивать.
рисунок 2
Для начала посмотрим, имеются ли в кроссворде строки, которые должны быть полностью закрашены. Оказывается, есть - в нашем случае это цифра 9 в пятой строке и пятом столбце, на которые указывают стрелки. Поскольку ширина кроссворда как раз и составляет 9 клеток - значит, все клетки в этой строке должны быть закрашены. Заодно зачеркиваем обе цифры 9, чтобы они нас больше не отвлекали.
рисунок 3
Обратим внимание, что в результате первого шага, у нас автоматически нашлось решение для первой строки, а также для первого и девятого столбца, где во всех случаях быть закрашена всего одна клетка. А это значит, что все остальные клетки в этих рядах будут пустыми. Вычёркиваем все три использованные цифры и отмечаем пустые клетки.
рисунок 4
Опять внимательно изучаем результат предыдущих действий. Становится ясно, что в четвёртой строке снова определяется вся группа из семи идущих подряд клеток, которые можно смело заштриховать.
рисунок 5
Всегда следует обращать внимание на самые большие из предложенных чисел, которые легче дают зацепку для дальнейшего решения головоломки. В нашем случае это две шестёрки во втором и восьмом столбце. Поскольку место положения группы из шести клеток в данных комбинациях буден неоднозначным, попробуем рассуждать логически. Заодно познакомимся с одним из основных принципов решения японских кроссвордов. Запоминаем простое правило. Если число рядом со строкой или столбцом всего одно, и оно составляет больше половины длины, то можно закрашивать несколько клеток в середине. В нашем случае это центральные четыре клетки. Как не размещай в восьми клетках группу из шести клеток, четыре центральные обязательно окажутся закрашенными (т.е. 8-6=2, что означает количество "неизвестных" клеток сверху и снизу). Поскольку, окончательное решение по данным столбцам мы ещё не приняли, сами цифры пока не вычёркиваем, а обводим красным кружком. Сюда мы вернёмся позже, когда получим новую зацепку.
рисунок 6
И снова нам улыбнулась удача. В шестой и седьмой строке решение обозначилось автоматически в результате предыдущих манипуляций. Вычёркиваем ненужные цифры и отмечаем пустые клетки.
рисунок 7
Поскольку кроссворд довольно простой, уже просматривается несколько вариантов его дальнейшего решения. Они очевидны. Можно пойти любым путём. Например, снова обратить внимание на самые большие из оставшихся цифр. Пятёрку в третьей строке пока оставим в покое, т.к. проще сначала вычеркнуть цифру 4 в очевидном шестом столбце. Не забываем отмечать пустые клетки.
рисунок 8
Теперь не оставляет сомнения местоположение группы из трёх клеток в соседнем столбце справа.