Введение

Логическая головоломка, формирующая изображение в сетке.

Нонограммы, также известные как Hanjie, Paint by Numbers, Picross, Griddlers и Pic a Pix, — это логические головоломки, в которых ячейки сетки необходимо закрасить или оставить пустыми в соответствии с числами, расположенными по краям сетки, чтобы раскрыть скрытое изображение. В этой головоломке числа представляют собой форму дискретной томографии, измеряющую количество непрерывных линий заполненных клеток в любом ряду или столбце. Например, подсказка "4 8 3" означает наличие групп из четырех, восьми и трех заполненных клеток в указанном порядке, при этом между последовательными группами должен быть хотя бы один пустой квадрат. Эти головоломки часто бывают черно-белыми, представляя собой двоичное изображение, но могут быть и цветными. Если головоломка цветная, числовые подсказки также окрашены в соответствующие цвета, указывающие цвет клеток. Два числа разного цвета могут разделяться пробелом, а могут быть и расположены непосредственно друг за другом. Например, черная четверка, за которой следует красная двойка, может означать четыре черные клетки, несколько пустых промежутков и две красные клетки, либо просто четыре черные клетки, сразу за которыми следуют две красные. Нонограммы не имеют теоретических ограничений по размеру и могут быть реализованы не только в квадратном формате. Нонограммы названы в честь Нона Ишиды, одного из двух изобретателей этой головоломки.

Печатные издательства

В 1988 году Non Ishida опубликовала три головоломки с пиктограммами в Японии под названием "Window Art Puzzles". В 1990 году Джеймс Далгети в Великобритании придумал название Nonograms в честь Non Ishida, и The Sunday Telegraph начал публиковать их еженедельно в своей газете. Они также стали популярны в Южной Африке и других странах. В 1998 году The Sunday Telegraph провел конкурс среди читателей для выбора нового названия для этих головоломок. Победителем стало название "Griddlers", выбранное читателями. В 1993 году Ishida опубликовала книгу "Book of Nonograms". В частности, игра предоставляет возможность игрокам делиться своими результатами.

Сегодня

Paint by numbers были опубликованы издательством Sanoma Uitgevers в Нидерландах, Puzzler Media (ранее British European Associated Publishers) в Великобритании и Nikui Rosh Puzzles в Израиле. Журналы с головоломками типа «нонogram» издаются в США, Великобритании, Германии, Нидерландах, Италии, Венгрии, Финляндии, Чехии, Словакии, России, Украине и многих других странах.

Методы растворения

Чтобы решить головоломку, необходимо определить, какие ячейки будут заполнены, а какие останутся пустыми. Решающие часто используют точку или крестик, чтобы отметить ячейки, в которых они уверены, что должно быть пустое место. Ячейки, которые можно определить логически, следует заполнять. Если при решении используются догадки, даже одна ошибка может распространиться по всему полю и полностью испортить решение. Ошибка может проявиться лишь спустя некоторое время, когда исправить головоломку будет очень сложно. Скрытое изображение может помочь обнаружить и устранить ошибку, но в целом оно мало влияет на процесс решения, поскольку может ввести в заблуждение. Многие головоломки можно решить, последовательно рассуждая над каждой строкой или столбцом, затем переходя к следующей и повторяя это до полного решения. Более сложные головоломки могут потребовать различных видов логических рассуждений типа "что, если?", охватывающих несколько строк (или столбцов). Этот метод основан на поиске противоречий: например, если ячейка не может быть заполнена, потому что это приведёт к ошибке в другой ячейке, то она должна оставаться пустой.

Простые пространства

Этот метод заключается в определении пустых областей путем поиска ячеек, находящихся за пределами диапазона любых возможных блоков коробок. Например, рассмотрим ряд из десяти ячеек с коробками в четвертой и девятой ячейках и подсказками 3 и 1. Блок, связанный с подсказкой 3, будет охватывать четвертую ячейку, а подсказка 1 будет находиться в девятой ячейке. Во-первых, подсказка 1 полностью определена, и вокруг связанного блока останутся пустые области. Во-вторых, подсказка 3 может распространяться только между второй и шестой ячейками, поскольку она всегда должна включать в себя четвертую ячейку; однако это может оставлять ячейки, которые в любом случае не могут содержать коробки, например, первую и седьмую. Важно отметить: в этом примере учтены все блоки, но это не всегда так. Игроку следует быть внимательным, так как могут существовать подсказки или блоки, которые еще не связаны между собой.

Клей

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

Пунктуация

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

Ртуть

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

Математический подход

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

Сложите все числа подсказок вместе, добавляя 1 за каждый "пробел" между ними. Например, если подсказка – 6 2 3, то на этом шаге получается сумма 6 + 1 + 2 + 1 + 3 = 13. Вычтите это число из общего количества ячеек в строке (обычно ширина или высота головоломки). Например, если подсказка из шага 1 находится в строке шириной 15 ячеек, то разница будет равна 15 – 13 = 2. Обратите внимание: если пробелы могут располагаться слева или справа (сверху или снизу), это "уменьшает" доступную область. Если известно, что крайняя правая ячейка – пробел, то разница будет равна 14 – 13 = 1. Любые подсказки, значение которых больше числа, полученного на шаге 2, приведут к заполнению нескольких блоков. В примере это относится к подсказкам 6 и 3, но не к 2. Для каждой подсказки из шага 3 вычтите число из шага 2, чтобы определить количество блоков, которые можно заполнить. Например, для подсказки 6 будет (6 – 2 =) 4 заполненных блока, а для подсказки 3 – (3 – 2 =) 1. Обратите внимание: применение той же процедуры к подсказке, которая "не прошла" шаг 3, даст неположительное число, указывающее на то, что для этой подсказки блоки заполняться не будут. Подсказка 2 дает число (2 – 2 =) 0; если бы была подсказка 1, она дала бы число (1 – 2 =) -1. Чтобы заполнить блоки, представьте, что все блоки прижаты к одной стороне, отсчитайте с этой стороны "через" блоки и заполните соответствующее количество ячеек. Это можно сделать в любом направлении. Например, подсказку 6 можно выполнить двумя способами:
Слева: Поскольку 6 – первое число, отсчитайте 6 блоков от левого края, заканчивая 6-м блоком. Теперь "дозаполните" 4 блока (число, полученное на шаге 4), чтобы ячейки с 3 по 6 были заполнены. Справа: начиная с правой стороны, необходимо учесть подсказки, расположенные справа от 6. Начиная с ячейки 15, отсчитайте 3 ячейки для подсказки 3 (до ячейки 13), затем пробел (12), затем подсказку 2 (10), затем пробел (9), затем подсказку 6 (3). От 3-й ячейки "дозаполните" 4 блока, заполнив ячейки с 3 по 6. Результаты будут такими же, как при выполнении подсчета слева, как описано выше. Повторите шаг 5 для всех подсказок, определенных на шаге 3. На иллюстрации строка 1 показывает ячейки, заполненные в соответствии с этой процедурой, строки 2 и 4 показывают, как блоки прижимаются к одной стороне на шаге 5, а строки 3 и 5 показывают ячейки, дозаполненные на шаге 5. Использование этой техники для всех строк и столбцов в начале решения головоломки дает хороший старт для ее завершения. Обратите внимание: некоторые строки/столбцы изначально не дадут никаких результатов. Например, строка из 20 ячеек с подсказкой 1 4 2 5 даст 1 + 1 + 4 + 1 + 2 + 1 + 5 = 15. 20 – 15 = 5. Ни одна из подсказок не больше 5. Кроме того, этот метод можно использовать в меньшем масштабе. Если в центре или с обеих сторон есть свободные ячейки, даже если некоторые подсказки уже известны, этот метод можно использовать с оставшимися подсказками и доступными ячейками.

Более глубокая рекурсия

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

Несколько строк

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

Нонограммы в вычислительной технике

Решение головоломок нонограмм является NP-полной задачей. Это означает, что не существует алгоритма, работающего за полиномиальное время, который бы решал все головоломки нонограмм, если P = NP. Однако определенные классы головоломок, например, те, в которых каждая строка или столбец содержит только один блок ячеек и все ячейки связаны, могут быть решены за полиномиальное время путем сведения задачи к задаче 2-удовлетворимости.

Программные решения

Обширное сравнение и обсуждение алгоритмов решения нонограмм можно найти на сайте WebPBN (Web Paint By Number). Решатель нонограмм, написанный на C++ и опубликованный в журнале Pattern Recognition, решает строки за время, не превышающее квадратичное.

Версии видеоигр

Nintendo выпустила несколько видеоигр под названием "Picross" (ピクロス). Игра Nintendo Game Boy Mario's Picross была первоначально выпущена в Японии 14 марта 1995 года и добилась неплохого успеха. Однако игра не стала хитом на рынке США, несмотря на масштабную рекламную кампанию Nintendo. Игра имеет возрастающую сложность, с последовательными уровнями головоломок, содержащими более крупные сетки. Каждая головоломка имеет ограниченное время на решение. Подсказки (открытие линий) можно запросить с потерей времени, а ошибки также приводят к штрафам по времени (сумма штрафа увеличивается с каждой ошибкой). Picross 2 была выпущена позже для Game Boy, а Mario's Super Picross – для Super Famicom, ни одна из которых не была переведена для рынка США (Super Picross Mario, однако, позже вышла на Wii Virtual Console в сервисе PAL 14 сентября 2007 года в рамках Hanabi Festival, а также в Nintendo Switch Online по всему миру 23 сентября 2020 года). Обе игры представили также Picross с Варио, где роль главного героя играет заклятый враг Марио. Эти раунды отличаются отсутствием функции подсказок, а ошибки не наказываются – но и не показываются. Эти раунды можно пройти только при правильной отметке всех клеток без ошибок. Ограничение по времени также было снято. Nintendo также выпустила восемь томов Picross на японском периферийном устройстве Nintendo Power в Японии, под названием NP Picross, каждый из которых содержал новый набор головоломок, включая головоломки, основанные на различных персонажах Nintendo, таких как Марио, The Legend of Zelda и Pokémon. Nintendo выпустила Picross DS для портативной системы Nintendo DS в 2007 году. Она содержит несколько этапов различной сложности, от сеток 5x5 до 25x20. В обычном режиме игрокам сообщается об ошибках (с потерей времени), а в свободном режиме – нет. Подсказка доступна перед началом головоломки во всех режимах; игра открывает случайную строку и столбец. Дополнительные головоломки были доступны через Nintendo Wi-Fi Connection; некоторые из оригинальных головоломок Mario Picross также были доступны. Однако сервис был закрыт 20 мая 2014 года. Nintendo выпускала новые головоломки раз в две недели. Picross DS вышла в Европе и Австралии 11 мая 2007 года, а в США – 30 июля 2007 года и получила хорошие отзывы критиков, включая Крейга Харриса, Джессику Уодли и Дэйва Маккарти, которые назвали игру "затягивающей". 3D-версия игры, Picross 3D, также вышла для DS в Японии в 2009 году и на международном уровне в 2010 году. Продолжение, Picross 3D: Round 2, было выпущено для Nintendo 3DS в 2015 году. Еще одна загружаемая версия игры была выпущена для Nintendo eShop на Nintendo 3DS под названием Picross e, Picross e2 и Picross e3, вышедшие в 2013 году, а Picross e4 – в 2014 году. Nintendo также выпустила спин-офф Pokémon 7 декабря 2015 года в виде условно-бесплатной игры Pokémon Picross для Nintendo 3DS. My Nintendo Picross The Legend of Zelda: Twilight Princess вышла для Nintendo 3DS 31 марта 2016 года исключительно в качестве премиальной награды для My Nintendo. Другие компании также выпустили игры-нонограммы, такие как Falcross для iOS, Across Stitch от Knitwit Studios для Microsoft Windows и Apple macOS, а также серию игр Color Cross от Little Worlds Studio для Nintendo DS, Microsoft Windows и iOS. Кроме того, головоломки-нонограммы появились в играх, не относящихся к Picross, например, в пятой части Deadly Rooms of Death, The Second Sky. В ней головоломки-нонограммы (снова называемые головоломками "Picross"), представляющие игровые объекты, являются необязательными, разблокируемыми головоломками, появляющимися в конце игры, которые можно решать на уровне "Центральная станция", и их решение открывает бонусные уровни. В 2018 году Konami выпустила игру под названием Pixel Puzzle Collection или Picross Puzzle (ピクロジパズル), в которой представлены классические персонажи и спрайты Konami.

Другие логические головоломки

Пентамино по номерам — это вариант, в котором двенадцать фигур пентамино необходимо разместить в сетке, не касаясь друг друга (даже по диагонали). Триддлер — это ответвление, использующее треугольные фигуры вместо квадратов. Paint by pairs или Link a Pix состоит из сетки, в которой некоторые клетки заполнены числами; пары чисел должны быть правильно расположены и соединены линией, заполняющей общее количество клеток, равное этому числу. Существует только один уникальный способ соединить все клетки в правильно составленной головоломке. После завершения клетки, соединенные линиями, заполняются; контраст с пустыми клетками раскрывает изображение. (Как и выше, существуют цветные версии, в которых используются совпадающие числа одного и того же цвета.) Fill a Pix также использует сетку с числами внутри. В этом формате каждое число указывает, сколько клеток, окружающих его и саму клетку, будет заполнено. Например, клетка с цифрой "9" будет иметь все восемь окружающих клеток и саму себя заполненными. Если она помечена "0", все эти клетки остаются пустыми. Maze a Pix использует лабиринт в стандартной сетке. Когда найден единственный правильный путь от начала до конца, каждая клетка решения заполняется (или, альтернативно, заполняются все клетки, не входящие в решение), чтобы создать изображение. Tile Paint — еще один тип логических головоломок от Nikoli. Она работает как обычные нонограммы, за исключением того, что указывает только общее количество заполненных клеток в каждой строке или столбце, а нерегулярные области в сетке имеют границы, указывающие, что если одна из клеток внутри области заполнена, то все они должны быть заполнены.