Реши японскую головоломку, ЯПОНСКИЕ ГОЛОВОЛОМКИ
Похожие природные условия есть и в других уголках планеты, но, пожалуй, нигде вы не найдете места, где земля была бы так сильно изменена деятельностью людей. Комментарии Комментарии Кроссворд полностью разгадан! Мы добавляем 4 черных треугольника к трем уже имеющимся и закрашиваем остаток линии белым.
Теперь смотрим на строки. Во второй строке сейчас закрашена одна клетка, а в числовом обозначении стоит единственное число 2. Это значит что должна быть закрашна еще одна клетка возле нее. Она может быть сразу слева или справа. В четвертой строке должно быть закрашено сначала две, а потом одна клетка.
Блок из двух клеток уже закрашен, обрамляем его крестиками с двух сторон. Единичка должна быть в пятой или шестой клетке. Так как мы не знаем где точно, то поставить крестики не можем.
Идем дальше. В пятой строке должно быть закрашено сначала три, потом одна клетка. Как бы не располагались эти два блока, третья клетка слева будет обязательно закрашена. В шестой строке - число 4.
Так как у нас уже закрашена одна клетка, то мы видим, что блок из четырех клеток может начинаться только или с первой, или со второй клетки и не может начинаться из крайнего правого положения, поэтому помечаем ее крестиком.
Возвращаемся к стобцам. В первом и во втором у нас ничего не прояснилось. В третьем стобце мы видим, что там должен быть блок из 4 клеток, 3 из них уже закрашены.
Четвертая может быть только, или сверху, или снизу от блока. В четвертом стобце должен быть блок из трех клеток.
Одна уже закрашена. Так как в четвертой клетке стоит крестик, у нас остается только один вариант расположения этого блока. Закрашиваем его, помечаем крестиками оставшиеся клетки в этом столбце. В шестом столбце зачеркиваем первую и последнюю клетку, так как на второй и предпоследней позиции стоят крестики, а в этом столбце может быть только один блок из двух клеток. На оставшихся трех клетках наш блок может располагаться в двух вариантах, но в обоих центральная клетка будет закрашена.
Смотрим на вторую строку и видим что осталась только одна пустая клетка. Закрашиваем ее и получаем блок из двух клеток, как и задано в условии. В четвертой строке мы уже нашли оба блока 2 и 1 , поэтому зачеркиваем цифры в легенде и помечаем пустую пятую клетку крестиком. В пятой строке оказался найденным блок из трех клеток. Для единички остается одна пустая клетка, которую мы и закрашиваем.
В седьмой строке для чисел 3 и 1 остался единственный возможноый вариант расположения. Закрашиваем и зачеркиваем клетки. В третьем зачеркиваем пустую клетку, так как четверка уже найдена.
В пятом столбце закрашиваем предпоследнюю клетку, так как на последней позиции закрашена одна клетка, а судя по верхней числовой легенде у нас должен быть блок из двух клеток. Незакрашенных клеток не осталось, а это значит, что мы полностью решили японский кроссворд! Получился маленький симпатичный котенок. Вы может самостоятельно попробовать решить этот японский кроссворд здесь.
Аналогично решаются и цветные японские кроссворды. Особенность их в том, что если подряд идут 2 группы разных цветов, то между ними пустой ячейки может и не быть. Между последовательностями одного цвета пробел, как и в черно-белых японских кроссвордах, обязателен! Набор чисел значит, что в определенном ряду есть три последовательные группы из , и черных клеток подряд. Группы могут быть расположены в ряду как попало, не нарушая относительный порядок цифры задают их длину, а позицию надо угадать , но они обязательно должны разделяться хотя бы одной белой клеткой.
В цветных кроссвордах у каждой группы еще есть свой цвет — любой, кроме белого, это фоновый цвет. Соседние группы разных цветов могут стоять вплотную, но для соседних групп одинаковых цветов разделение хотя бы одной белой клеткой еще обязательно.
Каждое пиксельное изображение можно зашифровать в виде кроссворда. Но восстановить обратно может быть невозможно — получившаяся головоломка может либо иметь более одного решения, либо иметь одно решение, но не может быть решена логическим путем.
Тогда оставшиеся клетки в процессе игры приходится отгадывать, используя квантовые компьютеры шаманские технологии. Такие кроссворды являются не кроссвордами, а графоманией. Считается, что корректный кроссворд — такой, что логическим путем можно прийти к единственному решению.
Если такой возможности нет, количество рассматриваемых вариантов ответа может быть очень много, намного больше, чем человек сможет посчитать сам. Неправильная нонограмма — решение единственное, но решить нормально нельзя.
Оранжевым помечены "нерешаемые" клетки. Взято из Wikipedia.
Такое ограничение объясняется так — в самом общем случае японский кроссворд это NP-полная задача. Однако, NP-полной задачей разгадывание не становится, если есть алгоритм, в каждый момент времени однозначно указывающий, какие клетки открыть далее.
Все методы разгадывания кроссвордов, применяемые человеком за исключением метода Монте-Карло проб и ошибок , основываются именно на этом. У наиболее православных кроссвордов ширина и высота делится на 5, нет рядов, которых можно посчитать мгновенно такие, где либо цветные клетки забивают все места, либо их нет совсем , и ограничено количество дополнительных цветов.
Эти требования не обязательные. Часто не решаются взад закодированные пиксельные арты, в которых используется "шахматный порядок" для имитации градиента.
Лучше понять будет, если вы наберете в поиске "pixelart gradient". Градиент как раз похож на этот фейловый кроссворд 2x2. У нас есть размер кроссворда, описание цветов и всех строк и столбцов. Как можно собрать из этого картинку:. Для каждой клетки перебираем все возможные состояния и проверяем на удовлетворительность. Сложность такого решения для черно-белого кроссворда , для цветного.
По аналогии с клоунской сортировкой это решение можно тоже назвать клоунским. Оно годится для размера 5x5. Перебираются все возможные методы расстановки горизонтальных групп клеток.
Ставим группу клеток в строке, проверяем, что она не ломает описание групп столбцов. Если ломает — ставим дальше на 1 клетку, опять проверяем. Поставили — переходим к следующей группе. Если группу поставить нельзя никак — откатываем две группы, переставляем предыдущую группу, и так далее, пока не поставим последнюю группу успешно. Это решение намного лучше и оно истинно верное. Мы можем проанализировать каждую строку и каждый столбец по отдельности.
У каждого ряда попытаемся раскрыть максимум информации. Алгоритм для каждой клетки в ряду узнает больше информации — может оказаться, что в какой-то цвет клетку окрасить невозможно, группы не сойдутся. Сразу строку полностью раскрыть нельзя, но полученная информация "поможет" раскрыться лучше нескольким столбцам, а когда мы начнем их анализировать, те опять "помогут" строкам, и так в течение нескольких итераций, пока для всех клеток не останется один возможный цвет.
Эффективное отгадывание черно-белого "однострочника", для которого некоторые клетки уже отгаданы — весьма жесткая задача. Она встречалась в таких местах, как:. Монохромный однострочник тоже можно решать по-разному, и за перебор всех вариантов, проверка на корректность, выделение клеток, которые имеют один и тот же цвет во всех вариантах , и еще как-то менее тупо.
Основная идея в том, чтобы использовать аналог бэктрекинга, но без лишних вычислений. Если мы как-то поставили несколько групп и сейчас находимся в какой-то клетке, то требуется узнать, можно ли поставить оставшиеся группы, начиная с текущей клетки.
Такой подход называется динамическим программированием. Псевдокод упрощен, и там даже запоминание вычисленных значений не производится. Значит, они могут работать за , это можно сделать с помощью частичных сумм:. А если нам надо произвести много прибавлений на отрезке в неком массиве , и притом этот массив мы никак не используем перед разными прибавлениями про такое говорят, что эта задача "решается оффлайн" , то вместо цикла:.
Таким образом, работает весь алгоритм за , где — количество групп черных клеток, — длина строки. Решение ACM Java.
При переходе на многоцветные нонограммы, которых еще непонятно, как решать, мы узнаем страшную правду — оказывается, на каждую строку магическим образом влияют все столбцы! Это понятнее через пример:. Источник — Методы решения японских кроссвордов. В то время как двухцветные нонограммы нормально обходились без этого, им не надо было оглядываться на ортогональных друзей. На картинке видно, что у левого примера три крайние правые клетки пустые, потому что поломается конфигурация, если окрасить эти клетки в те цвета, в которых окрасить себя не-белый цвет.
Но этот прикол математически разрешим — надо каждой клетке выдать число, где -й бит будет означать, можно ли дать этой клетке -й цвет.
Изначально у всех клеток значение. Решение динамики поменяется не очень сильно. Можно будет наблюдать следующий эффект: в этом же левом примере, по версии строк, крайняя справа клетка может иметь либо синий либо белый цвет. По версии столбцов, эта клетка имеет либо зеленый, либо белый цвет. По версии здравого смысла, эта клетка будет иметь только белый цвет.
И дальше мы продолжаем вычислять ответ. Если считать нулевой бит "белым", первый "синим", второй "зеленый", то строка вычислила для последней клетки состояние , а столбец. Значит, реально у этой клетки состояние. Постоянно делаем обновление состояний всех строк и столбцов, описанное в прошлом пункте, пока не останется ни одной клетки с больше чем одним битом.
В каждой итерации после обновления всех строк и столбцов, обновляем состояния всех клеток в них через взаимный AND. Посмотрим на время работы программы, которая считывает из файла головоломку и решает ее полностью. Стоит оценить достоинства машинки, на которой все это добро писалось и тестировалась:. Понятно, что такой суперкомпьютер был выбран, потому что оптимизации на нем имеют больший эффект, чем на летающей шайтан-машине.
Итак, после прогона нашего алгоритма на самом сложном кроссворде по версии nonograms. Надо заметить, что "сложность" на сайте посчитана хорошо — этот же кроссворд во всех версиях программы так же был самым тяжелым, другие наиболее сложные кроссворды по мнению архива держались в топе по времени.
Для быстрого тестирования была сделана функциональность для бенчмарка. Для получения данных для него я специальным скриптом спарсил цветных кроссворда из и черно-белых из с nonograms. Можно считать, что эти кроссворды являются случайной выборкой, поэтому бенчмарк показал бы адекватные средние значения. Также номера пары дюжин самых "сложных" кроссвордов также самых больших по размеру и количеству цветов записал в скрипт для загрузки ручками.
Здесь показаны возможные приемы для оптимизации, которые были сделаны 1 во время написания всего алгоритма, 2 для ужимания времени работы с полминуты до долей секунды, 3 те оптимизации, которые могут быть полезны далее. Можно заметить, что в среднем черно-белые кроссворды "сложнее" цветных.
