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