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