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