Как решать сложные японские кроссворды

4

Как решать японские кроссворды

Японские кроссворды представляют собой головоломку, скрывающую изображение. Нонограммы появились в конце ХХ в. в Японии. Они отличаются размерами, сложностью, количеством цветов. Есть различия и в том, как решать японские кроссворды, в зависимости от размеров изображения и доступных цифр.

Основная информация про нонограммы

Нонограмма – это головоломка, в которой спрятано изображение. Различают 2 вида японских кроссвордов: черно-белые и цветные. Картинка в обоих случаях представлена в виде закрашенных и пустых клеток на поле.

1. В черно-белом кроссворде используют 2 цвета: из первого складывается рисунок, второй используют для фона.
2. В цветном используют минимум 3 оттенка – 2 для изображения и 1 для фона.

На положение и количество зарисованных квадратов в каждом ряду указывают цифры над верхней и левой границами.

Решить японский кроссворд означает восстановить изначальный вид рисунка, т.е. найти верное расположение всех зарисованных квадратов на поле и закрасить их нужным цветом.

Основные элементы японских кроссвордов:

1. Кроссворд состоит из поля, на котором спрятана картинка, и чисел у левой и верхней границ.
2. Поле поделено на равные квадраты, группы из пяти клеток дополнительно ограничиваются толстыми линиями (это делается для удобства счета).
3. Цифры возле границ поля показывают, сколько подряд закрашенных квадратиков находится в ряду. Если чисел 2 и более, то между зарисованными полосками должен быть как минимум один незакрашенный квадрат. В цветных кроссвордах для групп разного цвета наличие интервала не является обязательным требованием, но между группами одного цвета пробел должен быть.
4. Числа записаны в том же порядке, что и зарисованные клетки, которые им соответствуют. Для горизонтальных рядов направление слева направо, для вертикальных – сверху вниз. То есть квадраты, принадлежащие первой цифре будут расположены на поле левее (или выше), чем обозначенные второй, третьей и т.д.

Требования к кроссворду:

• должен иметь одно решение, к которому можно прийти логическим путем;
• не должно быть строк и столбцов с пустыми клетками.

За счет однозначности правил, можно найти решение всех японских кроссвордов. Главное быть внимательным и выбрать правильную тактику.

Главные правила решения

Пошаговой инструкции, которая объясняет, как разгадывать японские кроссворды, и подходит для всех случаев, нет. Каждая картинка требует индивидуального подхода, но есть несколько основных шагов. Задача перед решающим сводится к определению максимального количества закрашенных и незакрашенных ячеек в каждом ряду.

Начинать следует с поиска наибольших чисел, двигаясь по убыванию.

Для проверки клеток на закрашенность используют несколько методов. Они применимы к кроссвордам любой величины и сложности.

1. Начинать можно как с вертикальных, так и с горизонтальных рядов. Если имеются цифры, совпадающие с количеством клеток в ряду, то их закрашивают первыми, дальше по убыванию.
2. Возможно, что сумма чисел в строке или столбце плюс минимальный интервал будет совпадать с шириной ряда – на это отдельно следует обратить внимание при поиске. Такой шаг поможет сразу зарисовать большее количество квадратов и облегчит дальнейшее разгадывание.
3. Когда все возможные квадраты по вертикали или горизонтали зарисованы, переходят к противоположным рядам, дальше возвращаются к вертикальным. Так постепенно заполняют все поле.
4. Если есть закрашенные ячейки с любого края поля достраиваются все крайние значения.

Освоив основные методы, новичок научится решать простые японские кроссворды.

Чтобы не запутаться, о каких квадратах идет речь, в описании методов используются 3 слова:

• блок – для количества квадратов, которые закрашивают по условию;
• группа – несколько блоков;
• полоса – для уже зарисованных квадратов на поле.

Цифры, которые обозначают уже закрашенные блоки, зачеркивают для удобства.

Отталкивание от границы

Если в строке или столбце первый зарисованный квадрат находится на меньшем расстоянии от границ поля, чем подходящая для него цифра, можно закрасить еще несколько ячеек дальше от него. Количество закрашиваемых квадратов равняется разности между положением уже зарисованного квадрата и первым числом. Работает это для правой и нижней границы, сравнению подлежат последние числа по столбику и по строке.

Например, если первая цифра в строке 5, а на этой линии закрашена 4 клетка, можно закрасить еще 1 после нее – при любом раскладе она будет закрашена.

Так отталкиваются не только от границ поля, но и от клеток с крестиком. Метод применим для второй и следующих цифр в ряду.

Наложение крайних позиций

Если рядом со строкой или столбцом записано одно число, которое больше половины ряда, закрашивают несколько квадратов в середине.

Для этого нужно наложить крайнее левое положение блока на крайнее правое – место, где они пересекаются, точно будет закрашено. Отталкиваться при использовании этого метода можно и от квадратов, помеченных крестиком.

Этим приемом можно пользоваться, если блок не один. Тогда накладывается крайнее левое положение всей группы на крайнее правое, при этом отступ между блоками в группе должен быть минимальным. Закрашивать можно только те клетки, в которых блоки наложились сами на себя.

Разделение имеющихся полос

Если на поле есть 2 полосы и между ними 1 пустая клетка, то нужно проверить, можно ли ее закрасить. Если при зарисовке получается полоса больше, чем допустимая условием в этом ряду, то она точно не будет закрашенной и ее сразу можно отметить крестиком. Часто после такого разделения полосы по обе стороны от крестика можно достроить и вычеркнуть несколько чисел из условия.

Например, если в ряду есть только цифры 1 и 2, то три ячейки подряд закрашены быть точно не могут. Значит посередине будет пустая клетка.

Если между полосами есть пробел и вы точно уверены, что обе полосы – это часть одного блока, то пропуск между ними нужно закрасить. Например, в ряду нужно разместить блоки 1, 6, 2 и есть 2 закрашенных полосы по 2 и 3 квадрата. Обе полоски не могут быть частями блоков 1 и 2, а значит, пропуск между ними точно можно закрасить – это части элемента из 6 квадратов.

Проверка пустых клеток

Бывают ситуации, когда закрашенные полосы могут подсказать, какие квадраты на поле точно будут пустыми. Если ни одно из возможных положений блока, соответствующего этой полосе, не затрагивает какие-то ячейки поля, в них ставится крестик.

Например, в строчке из 10 квадратов зарисованы 2 в середине, а в ряду должно быть закрашено 5 подряд. Тогда любое положение 5 клеток не задевает 1 крайний квадрат справа и 1 слева. Их можно зачеркнуть.

Случается и так, что в ограниченную 2 или больше крестиками область не помещается ни в один блок из этого ряда. Тогда пустые квадраты тоже заполняются крестиками.

Взаимоисключающие позиции

Если любое положение группы блоков исключает возможность закрашивания некоторой клетки, ее отмечают крестиком.

Например, в ряду, состоящем из 13 ячеек, нужно разместить 2 блока по 4 и 3 квадрата, при этом 3 квадрата в центре уже зарисованы, а в 5 нарисован крестик. Если закрашенная полоска относится к блоку из 3 квадратов, то оставшиеся справа ячейки будут пустыми. Если к блоку из 4, то 10-й квадрат будет пустым. В обоих вариантах 10-й квадрат отмечается крестиком.

Отличается ли решение цветных кроссвордов

Главная отличительная черта цветных японских кроссвордов – это наличие 3 и более цветов. Методы заполнения у них остаются прежними.

Дополнительную сложность представляет соответствие цветов в столбцах и строках. Если при решении черно-белой нонограммы не нужно сверять положение каждого квадрата по столбикам и строкам, то при цветной такая необходимость есть. Важно не только правильно определить положение закрашенных клеток, но и не перепутать цвет.

Кроме того, немного отличается поле головоломки: фон у цифр совпадает с цветом закрашенной полосы на поле.

Правила про обязательный отступ между блоками одинакового цвета сохраняется, но между блоками разных цветов пропуска может не быть. В остальном построение кроссвордов идентично.

Проверка цветов на пересечении

Важная особенность цветных кроссвордов – цветовое соответствие. Если выбрана возможная клетка для цвета по горизонтали, в этом ряду по вертикали должен присутствовать такой же цвет, иначе зарисовать квадрат нельзя.

Такая особенность позволяет откинуть множество вариантов расположения цветных блоков и упрощает решение головоломки.

Как и во многих других логических играх, научиться разгадывать японские кроссворды можно только опытным путем. Чем больше вы будете тренироваться, тем быстрее сможете перейти от самых простых загадок к профессиональным.

Передовые методы решения Японских кроссвордов

Следующая Японские кроссворды, правила игры Nonograms Предыдущая

Большинство людей, похоже, не нуждаются в большой инструкции о том, как решать головоломки Японские кроссворды (с разбивкой по числу или нонограммы, griddlers, hanjie, picross или что-то еще, как вам нравится их называть). Базовый метод решения легко продемонстрирован в простом примере, например, на первой странице этого сайта. Я ожидаю, что наиболее разумно умные люди могут понять это, даже не будучи показанными. И эта базовая техника решения действительно довольно мощная и может быть использована для решения большинства головоломок. Однако есть некоторые случаи, когда для решения головоломки требуются несколько более сложные логические трюки.
Эта страница призвана дать некоторые идеи о причудливых методах решения нонограмм, а также установить некоторую терминологию для обсуждения способов решения на форумах на этом сайте.

Линейное решение

«Линейное решение» — это когда вы работаете с одной строкой или одной колонкой за раз. Иногда это просто и прямо, как в случае ниже, где мы знаем, что ячейки с надписью «A» должны быть черными:

Иногда требуется немного подумать о разных случаях, например, в случае ниже, где одиночная ячейка «B» должна быть черной:

И иногда есть вещи, которые довольно чертовы трудно обнаружить, например, тот факт, что ячейка «C» в строке ниже должна быть белой:

Но хотя решение линии не всегда «просто» в смысле простоты, оно, по крайней мере, всегда предполагает просмотр только одной строки или столбца за раз.
Кстати, компьютерные программы, написанные для решения головоломок с разбивкой по числу, поддерживают линию линии. Это то, что любит компьютер, — глядя на одну небольшую часть проблемы одновременно и надеясь, что из этого выйдет общее решение. Пазлы, разрешаемые только линейным решением, почти всегда легко разрешаются компьютерами. Это в тех случаях, когда вы должны смотреть на большую часть загадки, чтобы понять, что люди действительно могут развернуть компьютерные программы.

Симметричность

Вот симметричная головоломка (предупреждение компульсивным решателям: это не похоже на что-либо, когда оно разрешено. Это всего лишь пример симметрии.):

Пример 4.
Линейное решение не дает вам нигде в этой головоломке.
Но головоломка симметрична, в том смысле, что она точно такая же, как зеркальное отражение. Каждый горизонтальный ключ обратим. «1 1» назад — «1 1». Верхний ключ в столбце 1 такой же, как в столбце 4, а верхний ключ в столбце 2 совпадает с столбцом 3.
Очевидно, если вы нашли решение этой головоломки и отразили решение вокруг вертикальной оси, то это зеркальное изображение также было бы решением головоломки. Если есть только одно решение, то мы знаем, что решение должно быть симметричным. Знать, что решение является симметричным, является действительно большим ключом.
К сожалению, на этом веб-сайте, по крайней мере, вы никогда не можете быть уверены, что головоломка действительно имеет только одно решение, и, не зная, что решение проблемы с использованием симметрии — это немного обманщик. Обычно мы не рассматриваем головоломку «логически разрешимой», если ее можно решить только симметрией. Исключением является то, что если автор головоломки помещает некоторую информацию в заголовок головоломки типа «[имеет только одно решение]», то вполне законно использовать симметрию для решения головоломки, потому что эта информация была предоставлена для использования в качестве части головоломки.
Как только вы узнаете, что решение головоломки выше симметрично, тривиально его решить. Во-первых, если какой-либо боковой ключ имеет в нем нечетное количество идентификационных номеров (например, строки «2»), то центральные столбцы должны быть черными. И если у него есть четное число номеров ключей, то центральные столбцы должны быть белыми. (В этом случае у нас есть два центральных столбца, но если головоломка имеет нечетное число столбцов, у нас будет только один.) Этого достаточно для решения большинства симметричных головоломок.
Конечно, существуют и другие формы симметрии. Головоломка может иметь вертикальную симметрию или диагональную симметрию, или вращательную симметрию (хотя она должна быть квадратной для любой из двух или двух последних).
Хотя решение по симметрии является своего рода обманом, это, конечно, не случай, когда он смотрит только на одну строку за раз. Вы действительно должны смотреть на всю головоломку, чтобы обнаружить симметрию.

Цветовая логика

Наиболее очевидным видом логики, которая включает в себя одновременное рассмотрение строк и столбцов, является «цветовая логика». Это происходит в многоцветных головоломках, когда подсказка строки сообщает вам, что ячейка должна быть либо цветом A, либо цветом B, в то время как в подсказке столбца говорится, что это должен быть либо цвет B, либо цвет C, поэтому мы можем заключить, что это должен быть цвет B.
Вот простой пример:

Опять же, линейная логика не работает, но совершенно очевидно, что ячейка «А» должна быть белой. В конце концов, подсказка в строке говорит, что она может быть только красной или белой, а подсказка в столбце говорит, что она может быть только зеленой или белой, поэтому она должна быть белой.
Вот более сложный пример:

Опять же, решение линии не дает нам нигде, и мы проигнорируем вращательную симметрию головоломки (что сложно понять и обмануть).
Производственная линия рассуждений, однако, заключается в том, чтобы спросить, какие ячейки во втором ряду могут быть красными. Посмотрев на главные подсказки, мы видим, что ячейки, отмеченные «А», не могут быть красными. Они могут быть зелеными или белыми, но не красными. Но если это так, то ячейка «B» должна быть красной и может быть отмечена красным цветом, потому что каждое место, которое красные три могут включать в себя эту ячейку. Та же логика может применяться на трех других сторонах головоломки, и как только вы это сделаете, остальная часть головоломки легко решить с помощью решения линии.
Трюк с цветовой логикой запоминает, какие цвета могут быть у каждой ячейки. Некоторые компьютерные программы, такие как «контролер», используемые на этом сайте, сохраняют список возможных цветов для каждой ячейки. Если вы это сделаете, то все вышеописанные головоломки легко решить простым обычным решением (хотя алгоритм решения строк становится немного сложнее). Возможно, вы могли бы придумать какую-то систему обозначений, которая позволила бы вам делать то же самое на бумаге, но я сомневаюсь, что это действительно было бы полезно. На практике это просто вопрос, чтобы понять это в вашей голове. Трудно, но я не думаю, что пример 6 действительно сложнее, чем, скажем, пример 3.

Граничная логика

«Граничная логика» (или «Edge logic») — это логический трюк, часто полезный по краям головоломки. Головоломка № 23 на этом сайте была разработана в качестве примера такого рода вещей. Это выглядит так:

Трудно представить себе головоломку, менее доступную для решения линии. Опытные решатели сразу заметят одну многообещающую функцию: вдоль нижнего края есть довольно большое число («4») с небольшими номерами («2») в следующей строке вверх.
Трюк в таких случаях состоит в том, чтобы рассмотреть эти две строки вместе. Поскольку строка «4» находится прямо на краю головоломки, легко понять, каковы последствия, если «4» находится в разных местах и проверить, соответствуют ли эти последствия строке «2». Поэтому мы просто мысленно пробуем «4» в разных позициях. Мы могли бы начать с предположения, что ячейка «А» была черной. Очевидно, это означало бы, что все ячейки с надписью «B» также должны быть черными. Посмотрев на подсказки столбца, мы видим, что две ячейки с пометкой «C» также должны быть черными. Хотя ячейки с надписью «D» должны быть белыми. Но это делает невозможным образец черных и белых в этой строке. В этой строке может быть только два. Таким образом, это означает, что «А» не может быть черным и должен быть белым.
Как только вы получите представление об этом, довольно легко увидеть, что большинство мест, где вы могли бы разместить четыре в нижнем ряду, создавали бы невозможный шаблон во второй строке снизу. В этой головоломке фактически есть только одно место, которое может быть, это положение, показанное ниже. В любом другом положении он либо дал бы трех черных во втором ряду, либо двух чернокожих с белым между ними.

Если мы хотим продолжить решение этой головоломки, мы снова применим тот же трюк. На этот раз мы будем работать с 4 в столбце 6. Хотя в этом случае мы не работаем с внешним краем головоломки, мы все еще делаем одну и ту же основную вещь на краю неизвестной области.
Логика края полезна во множестве головоломок, но обычно это не работает так же хорошо, как в примере 7. Часто вы обнаружите, что существует несколько разных мест, где может существовать краевой блок. Но этого все равно может хватить, чтобы вы могли расставить несколько ячеек (особенно в углах), и может быть, что все возможные положения перекрываются на нескольких ячейках, которые вы можете нарисовать черным.
Существует множество вариантов краевой логики. Иногда первая строка внутрь может оказаться бесполезной, но вторая строка внутри будет более полезна. Иногда вы даже можете применить его к размещению блока в первой строке вовнутрь, проверяя согласованность со второй строкой внутрь.
Хорошей первой загадкой, чтобы попробовать логику края, является # 6336.

Улыбка логика

Другой шаблон, который часто встречается, — это «улыбка». Мы называем это тем, что самая распространенная форма, в которой он появляется, — головоломка в форме улыбки ниже:

Решение, показанное справа, уникально, но ни один из описанных выше методов не позволяет нам его решить (ну, симметрия, но мы не хотим использовать симметрию).
Ключом к нему являются все те, что указаны в подсказках столбцов. Мы знаем, что в каждом столбце может быть только один черный цвет, поэтому мы знаем, что горизонтальные блоки 1 и 2 никогда не могут перекрывать друг друга. Поскольку 1 не могут быть рядом друг с другом (потому что нам нужно пустое пространство между ними), блоки из двух строк должны чередоваться. Они должны идти 1,2,1.
То же самое рассуждение применимо к головоломке ниже, с решением, которое больше похоже на змею, чем на улыбку:

Обычно головоломки не начинаются с так много столбцов, содержащих только один. Это скорее своего рода ситуация, которая иногда развивается в головоломке, которая почти завершена, где в столбцах было много других номеров ключей, но они уже были размещены. Логика улыбки — это то, что обычно используется в конце процесса решения, в отличие от краевой логики, которая может применяться в любой точке. (Но для исключения из этого правила см. Гламур # 6542).
Еще одна распространенная вариация логики улыбки встречается в таких ситуациях, как головоломка ниже:

Эта головоломка уже частично решена с использованием классического решения линий, но решение линии не дает нам дальнейших результатов. Но восемь нераскрытых квадратов действительно находятся в той же ситуации, что и базовый шаблон улыбки в примере 8. Для решения этой проблемы могут применяться те же аргументы.

Двусторонняя логика

Пример ниже похож на тот, который я когда-то использовал, когда я застрял. У меня нет по-настоящему умного имени, но на данный момент я называю это «двухсторонней логикой». Это было решено, поскольку решение по линии вас возьмет. Что не столь очевидно, так это то, что все ячейки с надписью «A» должны быть белыми.

Эти рассуждения идут так. Очевидно, что блок «2» в столбце 7 может находиться только в одном из двух положений. Это говорит нам о столбце 6: либо ячейке непосредственно над пунктирной ячейкой, либо непосредственно под пунктирной ячейкой должно быть черным. Таким образом, «2» в этом столбце может находиться только в одной из двух позиций, которые не содержат никаких ячеек «А», поэтому мы можем их расставить. Оттуда остальная часть головоломки легко решается. (Фактически, пример 11 — это не все, что искусно спроектировано, потому что оно также может быть решено с помощью краевой логики).
Итак, основная идея здесь — искать места, где вы знаете, что одна из двух ячеек должна быть черной. Для каждого случая подумайте всего лишь о переезде или о двух, чтобы увидеть, какие другие ячейки вы могли бы установить в этом случае. Если в обоих случаях любые ячейки устанавливаются одинаково, вы можете их пометить.
Несколько другой пример того же трюка показан ниже. Использование двухсторонней логики в двух открытых ячейках в столбце семь позволяет вам установить ровно одну ячейку, которая позволяет решить оставшуюся часть головоломки:

Ты нашел это? Это ячейка в четвертом ряду и шестой столбец, и она должна быть белой. Если «2» в столбце семь находится в верхнем положении, тогда вся остальная часть четвертой строки должна быть белой. Если «2» находится в нижнем положении, верхняя половина столбца шесть должна быть белой. В любом случае, одна ячейка должна быть белой.
Опять же, случается, что эта головоломка также может быть решена с помощью краевой логики. Трудно справиться с маленькими головоломками, которые могут быть решены только двунаправленной логикой.

Подводя итоги

Иногда интересные вещи могут быть достигнуты путем суммирования количества ячеек, которые необходимо установить в определенном регионе. Вот головоломка, надуманная, чтобы продемонстрировать этот трюк:
Иногда интересные вещи могут быть достигнуты путем суммирования количества ячеек, которые необходимо установить в определенном регионе. Вот головоломка, надуманная, чтобы продемонстрировать этот трюк:

Мы использовали простое решение линии, чтобы заполнить много места, но у нас есть нераскрытые области наверху, а внизу все еще предстоит выяснить. Следующее, что мы, естественно, попытаемся завершить эту головоломку, было бы краевой логикой на 12 в первой колонке, но это ничего не дает нам.
Но есть простой трюк, который расскажет нам, где именно должно быть 12. Во-первых, используйте подсказки строк, чтобы добавить количество ячеек, которые необходимы в трех верхних строках. Первая строка равна 1 + 2 + 1 = 4, вторая — 2 + 2 + 1 = 5, а третья — всего 2, поэтому общее число равно 4 + 5 + 2 = 11. Нам нужно в общей сложности 11 черных клеток в трех верхних рядах головоломки.
Теперь, если мы посмотрим на подсказки столбца, мы можем использовать их для определения количества ячеек в трех верхних строках для каждого столбца, кроме первого столбца. Столбец 2 должен иметь 2 ячейки, а остальные восемь столбцов должны иметь по одному, в общей сложности 10.
Итак, поскольку подсказки строки говорят нам, что в верхней части должно быть 11 ячеек, и, поскольку мы знаем, что в столбцах с 2 по 10 есть 10, в первых трех строках столбца 1 должна быть ровно одна черная ячейка. говорит нам точно, где должно быть 12 в столбце 1, а остальная часть головоломки тривиальна для решения.
Я только когда-либо использовал этот трюк в нескольких головоломках, но он отличный, когда он работает.

Решение цветных японских кроссвордов со скоростью света

Японские кроссворды (также нонограммы) — логические головоломки, в которых зашифровано пиксельное изображение. Разгадывать кроссворд нужно с помощью чисел, расположенных слева от строк и сверху от столбцов.

Размер кроссвордов может доходить до 150×150. Игрок с помощью специальных логических приемов вычисляет цвет каждой клетки. Решение может занять как пару минут на кроссвордах для начинающих, так и десятки часов на сложных головоломках.

Хороший алгоритм может решить задачу намного быстрее. В тексте описано, как с помощью наиболее подходящих алгоритмов (которые вообще приводят к решению), а также их оптимизаций и использования особенностей C++ (которые уменьшают время работы в несколько десятков раз) написать решение, работающее почти мгновенно.

В мобильной версии Хабра формулы в тексте могут не показываться (не во всех мобильных браузерах) — пользуйтесь полной версией или другим мобильным браузером, если заметили проблемы с формулами

Правила игры

Изначально холст кроссворда белый. Для ванильных черно-белых кроссвордов нужно восстановить местоположения черных клеток.

В черно-белых кроссвордах количество чисел для каждой строки (слева от холста) или для каждого столбца (сверху от холста) показывает, сколько групп черных клеток находятся в соответствующих строке или столбце, а сами числа — сколько слитных клеток содержит каждая из этих групп. Набор чисел значит, что в определенном ряду есть три последовательные группы из , и черных клеток подряд. Группы могут быть расположены в ряду как попало, не нарушая относительный порядок (цифры задают их длину, а позицию надо угадать), но они обязательно должны разделяться хотя бы одной белой клеткой.

В цветных кроссвордах у каждой группы еще есть свой цвет — любой, кроме белого, это фоновый цвет. Соседние группы разных цветов могут стоять вплотную, но для соседних групп одинаковых цветов разделение хотя бы одной белой клеткой еще обязательно.

Что не является японским кроссвордом

Каждое пиксельное изображение можно зашифровать в виде кроссворда. Но восстановить обратно может быть невозможно — получившаяся головоломка может либо иметь более одного решения, либо иметь одно решение, но не может быть решена логическим путем. Тогда оставшиеся клетки в процессе игры приходится отгадывать, используя квантовые компьютеры шаманские технологии.

Такие кроссворды являются не кроссвордами, а графоманией. Считается, что корректный кроссворд — такой, что логическим путем можно прийти к единственному решению.

«Логический путь» — это возможность восстановить каждую клетку одну за другой, рассматривая строку/столбец по отдельности, или их пересечение. Если такой возможности нет, количество рассматриваемых вариантов ответа может быть очень много, намного больше, чем человек сможет посчитать сам.

Неправильная нонограмма — решение единственное, но решить нормально нельзя. Оранжевым помечены «нерешаемые» клетки. Взято из Wikipedia.

Такое ограничение объясняется так — в самом общем случае японский кроссворд это NP-полная задача. Однако, NP-полной задачей разгадывание не становится, если есть алгоритм, в каждый момент времени однозначно указывающий, какие клетки открыть далее. Все методы разгадывания кроссвордов, применяемые человеком (за исключением метода Монте-Карло проб и ошибок), основываются именно на этом.

У наиболее православных кроссвордов ширина и высота делится на 5, нет рядов, которых можно посчитать мгновенно (такие, где либо цветные клетки забивают все места, либо их нет совсем), и ограничено количество дополнительных цветов. Эти требования не обязательные.

Наипростейший неправильный кроссворд:

Часто не решаются взад закодированные пиксельные арты, в которых используется «шахматный порядок» для имитации градиента. Лучше понять будет, если вы наберете в поиске «pixelart gradient». Градиент как раз похож на этот фейловый кроссворд 2×2.

Возможные варианты решений

У нас есть размер кроссворда, описание цветов и всех строк и столбцов. Как можно собрать из этого картинку:

Полный перебор

Для каждой клетки перебираем все возможные состояния и проверяем на удовлетворительность. Сложность такого решения для черно-белого кроссворда , для цветного . По аналогии с клоунской сортировкой это решение можно тоже назвать клоунским. Оно годится для размера 5×5.

Backtracking

Перебираются все возможные методы расстановки горизонтальных групп клеток. Ставим группу клеток в строке, проверяем, что она не ломает описание групп столбцов. Если ломает — ставим дальше на 1 клетку, опять проверяем. Поставили — переходим к следующей группе. Если группу поставить нельзя никак — откатываем две группы, переставляем предыдущую группу, и так далее, пока не поставим последнюю группу успешно.

Отдельно для каждого ряда

Это решение намного лучше и оно истинно верное. Мы можем проанализировать каждую строку и каждый столбец по отдельности. У каждого ряда попытаемся раскрыть максимум информации.

Алгоритм для каждой клетки в ряду узнает больше информации — может оказаться, что в какой-то цвет клетку окрасить невозможно, группы не сойдутся. Сразу строку полностью раскрыть нельзя, но полученная информация «поможет» раскрыться лучше нескольким столбцам, а когда мы начнем их анализировать, те опять «помогут» строкам, и так в течение нескольких итераций, пока для всех клеток не останется один возможный цвет.

Истинно верное решение

Одна строка, два цвета

Эффективное отгадывание черно-белого «однострочника», для которого некоторые клетки уже отгаданы — весьма жесткая задача. Она встречалась в таких местах, как:

• Четвертьфинал ACM ICPC 2006 — задачу можно попробовать решить самому. Тайм-лимит 1 секунда, ограничение количества групп 400, длины ряда тоже 400. Имеет сильно высокий уровень сложности по сравнению с другими задачами.
• International Olympiad in Informatics 2016 — условие, сдать задачу. Тайм-лимит 2 секунды, ограничение кол-ва групп 100, длины ряда 200’000. Такие ограничения оверкилл, но решение задачи с ограничениями ACM набирает 80/100 баллов в этой задаче. Тут тоже уровень не подкачал, школьники со всего мира с жестоким уровнем IQ тренируются несколько лет решать разную жесть, потом проходят на эту олимпиаду (пройти должны только 4 человека от страны), решают 2 тура по 5 часов и в случае epic win (бронза в разные годы за 138-240 баллов из 600) поступление в Оксфорд, потом офферы от понятных компаний в отдел поиска, долгая и счастливая жизнь в обнимку с дакимакурой.

Монохромный однострочник тоже можно решать по-разному, и за (перебор всех вариантов, проверка на корректность, выделение клеток, которые имеют один и тот же цвет во всех вариантах), и еще как-то менее тупо.

Основная идея в том, чтобы использовать аналог бэктрекинга, но без лишних вычислений. Если мы как-то поставили несколько групп и сейчас находимся в какой-то клетке, то требуется узнать, можно ли поставить оставшиеся группы, начиная с текущей клетки.

Такой подход называется динамическим программированием. Псевдокод упрощен, и там даже запоминание вычисленных значений не производится.

Функции CanInsertBlack/CanInsertWhite нужны, чтобы проверить, можно ли теоретически поставить группу нужного размера в нужное место. Все что им надо сделать — проверить, что в указанном интервале клеток нет «100% белой» клетки (для первой функции) или «100% черной» (для второй). Значит, они могут работать за , это можно сделать с помощью частичных сумм:

Такое же колдунство с частичными суммами ждет строки вида

Тут можно вместо = True увеличивать число на 1. А если нам надо произвести много прибавлений на отрезке в неком массиве , и притом этот массив мы никак не используем перед разными прибавлениями (про такое говорят, что эта задача «решается оффлайн»), то вместо цикла:

Можно сделать так:

Таким образом, работает весь алгоритм за , где — количество групп черных клеток, — длина строки. И мы проходим на полуфинал ACM ICPC или получаем бронзу межнара. Решение ACM (Java). Решение IOI (C++).

Одна строка, много цветов

При переходе на многоцветные нонограммы, которых еще непонятно, как решать, мы узнаем страшную правду — оказывается, на каждую строку магическим образом влияют все столбцы! Это понятнее через пример:

В то время как двухцветные нонограммы нормально обходились без этого, им не надо было оглядываться на ортогональных друзей.
На картинке видно, что у левого примера три крайние правые клетки пустые, потому что поломается конфигурация, если окрасить эти клетки в те цвета, в которых окрасить себя не-белый цвет.

Но этот прикол математически разрешим — надо каждой клетке выдать число, где -й бит будет означать, можно ли дать этой клетке -й цвет. Изначально у всех клеток значение . Решение динамики поменяется не очень сильно.

Можно будет наблюдать следующий эффект: в этом же левом примере, по версии строк, крайняя справа клетка может иметь либо синий либо белый цвет.
По версии столбцов, эта клетка имеет либо зеленый, либо белый цвет.
По версии здравого смысла, эта клетка будет иметь только белый цвет. И дальше мы продолжаем вычислять ответ.

Если считать нулевой бит «белым», первый «синим», второй «зеленый», то строка вычислила для последней клетки состояние , а столбец . Значит, реально у этой клетки состояние

Много строк, много цветов

Постоянно делаем обновление состояний всех строк и столбцов, описанное в прошлом пункте, пока не останется ни одной клетки с больше чем одним битом. В каждой итерации после обновления всех строк и столбцов, обновляем состояния всех клеток в них через взаимный AND.

Первые результаты

Допустим, что код мы писали не как дятлы, то есть никуда по ошибке объекты не копируем вместо передачи по ссылке, нигде в алгоритме не косячим, велосипедов не изобретаем, для битовых операций используем __builtin_popcount и __builtin_ctz (особенности gcc), все аккуратно и чисто.

Посмотрим на время работы программы, которая считывает из файла головоломку и решает ее полностью. Стоит оценить достоинства машинки, на которой все это добро писалось и тестировалась:

Понятно, что такой суперкомпьютер был выбран, потому что оптимизации на нем имеют больший эффект, чем на летающей шайтан-машине.

Итак, после прогона нашего алгоритма на самом сложном кроссворде (по версии nonograms.ru), получаем не очень хороший результат — от 47 до 60 секунд (в это входит считывание из файла и решение). Надо заметить, что «сложность» на сайте посчитана хорошо — этот же кроссворд во всех версиях программы так же был самым тяжелым, другие наиболее сложные кроссворды по мнению архива держались в топе по времени.

Для быстрого тестирования была сделана функциональность для бенчмарка. Для получения данных для него я специальным скриптом спарсил 4683 цветных кроссворда (из 10906) и 1406 черно-белых (из 8293) с nonograms.ru (это один из крупнейших архивов нонограмм в интернете) и сохранил их в формате, понятном программе. Можно считать, что эти кроссворды являются случайной выборкой, поэтому бенчмарк показал бы адекватные средние значения. Также номера пары дюжин самых «сложных» кроссвордов (также самых больших по размеру и количеству цветов) записал в скрипт для загрузки ручками.

Оптимизация

Здесь показаны возможные приемы для оптимизации, которые были сделаны (1)во время написания всего алгоритма, (2)для ужимания времени работы с полминуты до долей секунды, (3)те оптимизации, которые могут быть полезны далее.

Во время написания алгоритма

• Специальные функции для битовых операций, в нашем случае __builtin_popcount для подсчета единиц в двоичной записи числа, и __builtin_ctz для количества нулей перед первой самой младшей единицей. Таких функций может не оказаться в некоторых компиляторах. Для Windows подойдут такие аналоги:

• Организация массивов — меньший размер стоит вначале. Например, лучше использовать массив [2][3][500][1024], чем [1024][500][3][2].
• Самое главное — общая адекватность кода и избегание лишних забот для вычислений.

Что уменьшает время работы

• Флаг -O2 при компиляции.
• Чтобы не бросать в алгоритм полностью решенную строку/столбец заново, можно в отдельном std::vector/массиве завести флаги для каждого ряда, помечать их при полном решении, и не давать идти дальше, если решать уже нечего.
• Специфика многоповторного решения задачи на динамику предполагает, что специальный массив, который содержит флаги, помечающие уже «вычисленные» куски задачи, следует обнулять каждый раз при новом решении. В нашем случае это двумерный массив/вектор, где первое измерение — количество групп, второе — текущая клетка (см. псевдокод EpicWin сверху, где этого массива нет, но идея ясна). Вместо обнуления можно сделать так — пусть у нас будет переменная-«таймер», а массив состоит из чисел, показывающих последнее «время», когда этот кусок пересчитывался в последний раз. При запуске новой задачи «таймер» увеличивается на 1. Вместо проверки булевого флага следует проверять равенство элемента массива и «таймера». Это эффективно особенно в тех случаях, когда далеко не все возможные состояния покрываются алгоритмом (а значит, обнуление массива «считали ли мы уже это» занимает здоровый кусок времени).
• Замена несложных однотипных операций (циклы с присваиванием и т.д.) на аналоги в STL или более адекватные вещи. Иногда работает быстрее велосипеда.
• std::vector<bool> в С++ сжимает все булевые значения до отдельных битов в числах, что работает при доступе чуть медленнее, чем если бы это было обычное значение по адресу. Если программа ну очень-очень часто обращается к таким значениям, то замена bool на целочисленный тип может хорошо повлиять на производительность.
• Остальные слабые места можно искать через профайлеры и править их. Я сам использую Valgrind, его анализ производительности удобно смотреть через kCachegrind. Профайлеры встроены во многие IDE.

Этих правок оказалось достаточно, чтобы получить такие данные на бенчмарке:

Можно заметить, что в среднем черно-белые кроссворды «сложнее» цветных. Это подтверждает наблюдения любителей игры, которые также считают, что «цветные» решаются в среднем легче.

Таким образом, без радикальных правок (таких как переписывание всего кода на на С или ассемблерных вставок с fastcall и опусканием указателя фрейма) можно достичь высокой производительностью, заметим, на весьма скромном компьютере. К оптимизациям может быть применим принцип Парето — окажется, что мелкая оптимизация влияет сильно, потому что этот кусок кода критичен и вызывается очень часто.

Дальнейшая оптимизация

Следующие методы могут сильно улучшить производительность программы. Некоторые из них работают не во всех случаях, а при некоторых условиях.

• Переписывание кода на C-style и прочий 1972 год. Заменяем ifstream на сишный аналог, векторы на массивы, учим все опции компилятора и боремся за каждый такт процессора.
• Распараллеливание. Например, в коде есть кусок, где последовательно обновляются строки, потом столбцы:

Эти функции независимы друг от друга и у них нет общей памяти, кроме переменной solver (тип OneLineSolver), так что можно создать два объекта «решателя» (здесь очевидно только один — solver) и запустить два потока в этой же функции. Эффект такой — в цветных кроссвордах «самый тяжелый» решается в два раза быстрее, в черно-белых такой же на треть быстрее, а среднее время увеличилось, за счет сравнительно больших затрат на создание потоков.

Но вообще я бы не советовал делать прямо так в текущей программе и спокойно использовать — во-первых, создание потоков затратная операция, не стоит постоянно создавать потоки для микросекундных задач, во-вторых, при некоторой комбинации аргументов программы, потоки могут обращаться одновременно к какой-то внешней памяти, например при создании картинок решения — это надо бы учесть и обезопасить.

Если бы задача была серьезной и у меня было бы много данных и многоядерные машины, я бы пошел еще дальше — можно завести несколько постоянных потоков, у каждого будет свой объект OneLineSolver, и еще одна thread-safe структура, которая рулит распределением работы и по запросу к ней выдает референс на очередную строку/столбец для решения. Потоки после решения очередной задачи обращаются к структуре заново, чтобы решать что-то еще. Какую-то задачу-нонограмму в принципе можно начать решать, не закончив предыдущей, например когда эта структура занимается взаимным AND всех клеток, и тогда какие-то потоки свободны и ничего не делают. Еще распараллеливание можно провести на графическом процессоре через CUDA — вариантов много.

• Использование классических структур данных. Обратите внимание — когда я показывал псевдокод решения для цветных нонограмм, функции CanInsertColor и PlaceColor работают вовсе не за , в отличие от черно-белых нонограмм. Выглядит в программе это так:

То есть работает за линию, за (Позже будет объяснение смысла именно такого кода).

Посмотрим, как можно получить лучшую сложность. Возьмем CanPlaceColor . Эта функция проверяет, что среди всех чисел вектора в отрезке бит номер установлен в 1. Эквивалентно этому можно взять всех чисел этого отрезка и проверить бит номер . Используя тот факт, что операция коммутативная, также как сумма, минимум/максимум, произведение, или операция , для быстрого подсчета всего отрезка можно использовать почти любую структуру данных, работающую с коммутативными операциями на отрезке. Это:

1. SQRT-декомпозиция. Предподсчет , запрос . Статья на Хабре.
2. Дерево отрезков. Предподсчет , запрос . Сотни статей в интернете.
3. Разреженная таблица (Sparse Table). Предподсчет , запрос . Статья.

К сожалению, особо сильные колдунства как алгоритм Фарака-Колтона и Бендера (предподсчет , запрос ) использовать нельзя, так как вкурив статьи, можно понять, они созданы только для таких операций , что , то есть результат коммутативной операции — один из аргументов (жаль, а так хотелось. )

Теперь возьмем SetPlaceColor . Тут надо произвести операцию на отрезке массива. Это тоже можно делать с SQRT-декомпозицией или деревом отрезков с ленивым обновлением (оно же «с проталкиванием»). А для обеих функций одновременно можно еще использовать убер-структуру декартово дерево по неявному ключу с обновлением и запросом за логарифм.

Еще можно использовать расширение алгоритма для черного-белого кроссворда — частичные суммы для всех цветов.

Итак, возникает вопрос — почему мы не используем все это богатство комплюктерн саенс, а делаем за линию? На это есть несколько ответов:

1. Меньшая сложность вычислений не значит меньшее время работы. Алгоритм за может потребовать различных преподсчетов, выделений памяти, другой тряски ресурсов — у этого алгоритма может быть довольно высокая константа (не в смысле magic number в нейроночках, а аффект по времени работы). Очевидно, что если , то условный алгоритм за будет работать условные 10 секунд, а условный алгоритм за условные 0.150 секунд, но все может поменяться при достаточно маленьких , особенно когда таких вычислений много. Еще непонятнее, когда сложности очень похожие и одной сложности сложно перебить другую сложность (сложные приколы): versus . В нашей задаче (длина ряда) очень маленькое — в среднем около 15-30.
2. Запросов может оказаться достаточно мало, чтобы предпосчеты были бесполезными и жрали ресурсы просто так.

То есть объяснение простое — оба этих пункта выполняются и вставка этих чудес программерской мысли вместо тупого алгоритма либо очень слабо оптимизирует программу, либо только увеличивает время работы из-за специфики вычислений — очень маленького и не такого большого количества запросов, чтобы они грузили процессор. Факт про запросы доказывает то, что по мнению профайлера те функции занимают

11% времени соответственно, то есть довольно мало для такого потенциально слабого места программы. Даже если у нас из-за этого возникает большая оценка сложности алгоритма, стоит понимать, что в таких типах задач это оценка сверху, а реальное время работы на рандомном кроссворде всегда премного ниже.

Но не стоит забывать про структуры данных — они могут пригодиться в других случаях, так что я включил их в список оптимизаций. Переходим к следующему по списку.

• Правки алгоритма. Может оказаться так, что в среднем алгоритм на этих входных данных очень неплохо начинает работать, если поменять что-то неочевидное. В нашем случае этим может быть такое: логично же предположить, что если мы успешно обновили данные в строке, то обновленные в нем клетки скорее всего «триггерят» соответствующие столбцы? Значит, лучше эти столбцы обновить быстрее всех, сразу после этой строки! То есть образуется очередь из таких подзадач. Я не пробовал именно такой алгоритм, может это реально быстрее на нашем датасете.
• Внезапные изменения техзадания (окажется, что поступают кроссворды по 1337 цветов или размером 1000×1000) тоже требуют оптимизации. Для большого количество цветов можно использовать быстрый std::bitset, для размера — те же структуры данных, и так далее.

В общем, вот такие прикольные оптимизации. «Пихание» бедного алгоритма в зависимости от условий это весело и познавательно. Можно узнать про разные крутые вещи, как встроенное декартово дерево по неявному ключу в C++ (это rope, но велосипедная писанина практически всегда работает быстрее), особые встроенные сорта деревьев и спрятанный hashtable, работающий в 3-6 раза быстрее по вставке/удалению и в 4-10 раз по записи/чтению, чем unordered_map. Не говоря уже про различные нестандартные мазафаки со стороны, например из boost.

ROFL Omitting Format Language

Вдохновившись гениями давно минувших дней и их мыслительными продуктами, в частности совершенно новыми алгоритмами архивации и операционками с нескучными обоями, я также придумал принципиально новый формат картинок, основанный на японских кроссвордах и эффекте Даннинга-Крюгера.

ROFL — рекурсивный акроним, прямо как «GNU’s Not Unix». Собственно, смысл формата в том, что картинка кодируется в виде японского кроссворда, а редактор, чтобы прочитать ее, должен решить этот кроссворд. Отсюда и слово Omitting в названии — формат как бы скрывает истинное положение дел в картинке (что, кстати, может быть полезным в криптографии: можно передавать японские кроссворды с зашифрованными в нем паролями — все хакеры повесятся).

Лучше, если формат был бы похож на Matroska — в начале файла 4 байта [52][4F][46][4C], затем в трех байтах размер картинки и количество цветов, потом описание цветов, потом цвета, каждый по 3 байта, и потом описание всех групп — длина, количество клеток и цвет.

Формат свободный, лицензия MIT, финансовые отчисления добровольные — мне на кофе, как автору.

Исходники

Исходники программы лежат на GitHub. У программы есть множество возможных аргументов, генерация кроссворда из картинки, генерация картинок из кроссворда (кстати, почти все картинки в статье сгенерированы через этот код). Дополнительными библиотеками были Magick++ и args.

Как решать сложные японские кроссворды

Что такое японские кроссворды?

Японские кроссворды — это головоломки, в которых нужно разгадать цветные или черно-белые изображения по заданным числам.

Каждое число обозначает один горизонтальный или вертикальный блок. Число обозначает количество клеток в каждом из них, цвет — соответственно цвет клеток. Между блоками одного цвета должно быть не менее одной пустой клетки.

Найденные пустые клетки можно помечать крестиками (правая клавиша, либо выбрать крестики в цветовой панели). Под кроссвордом есть множество параметров, которые помогут настроить процесс решения. Если цвета трудно различимы, кликнув на кнопку в левом верхнем углу кроссворда можно поменять цвет на абсолютно любой другой.

В каталоге можно легко искать решенные и сохраненные японские кроссворды. Кроссворды, которые вы не хотите видеть в списках (кроме фильтра «любой статус») можно добавить в блэк-лист.

Примеры картинок

В японских кроссвордах могут быть зашифрованы самые разнообразные картинки! Люди, животные, растения, предметы, все что угодно!

Как решать японские кроссворды?

Весь процесс решения заключается в последовательном нахождении закрашеных клеток и пустых мест, которые точно закрашены быть не могут анализируя попеременно горизонтали и вертикали. Чем больше клеток вы помечаете, тем больше новых зацепок у вас появляется.

Рассмотрим решение маленького японского кроссворда.

В первую очередь ищем слева или сверху самые большие числа, и лучше всего у самых краев, с них проще всего начинать решение. В последнем столбце видим число 6. Это значит, что в столбце есть один блок из 6 закрашеных подряд черным цветом клеток. Так как японскик кроссворд в высоту всего 8 клеток, этот блок в нашем случае может расположится тремя способами — прилегая к верхнему краю, к нижнему и посредине. Если взять два крайних положения, становится понятно, что указанные ниже клетки будут закрашены в любом случае.

Посмотрите теперь на две горизонтальные строки с цифрами — 5. В каждой из этих строк есть по блоку из 5 клеток. Благодаря тому, что мы нашли одну закрашенную клетку с краю для каждого, мы точно знаем, как эти блоки расположены. Смело закрашиваем. Полезная фишка: удерживая клавишу CTRL можно закрасить сразу целый прямоугольный блок.

Программа автоматически зачеркнет числа, которые найдены правильно и поставит крестики в свободные ячейки. Эту функцию можно отключить в настройках, если вы хотите самостоятельно контролировать весь процесс. В этом случае, крестики можно будет ставить правой клавишей мыши, либо выбрав крестики в цветовой панели. Кроме того, настройками можно отрегулировать внешний вид крестиков, цвет и прозрачность подсветки и многое другое.

Теперь обратите внимание на четвертую строку. В ней есть розовый блок из двух клеток. Взглянув на верхние число видим, что розовый есть только в двух столбцах, поэтому и горизонтальный блок может располагаться только в указанных ниже клетках

В третьем столбце над розовой клеткой должен располагаться блок из трех клеток. Так как там всего и осталось три пустых клетки, значит мы точно знаем его положение.

Во второй строке должен быть блок из трех клеток. Одна закрашенная клетка уже есть, и она ограничена крестиком с правой стороны. Это значит блок может быть продолжен только в одну сторону, закрашиваем его.

Применяем аналогичные приемы на оставшихся клетках и получаем готовую картинку, японский кроссворд полностью решен!