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