Pull to refresh

Comments 36

Нет, не изучаю. Просто задача довольно интересная.
UFO landed and left these words here
UFO landed and left these words here
Мне кажется, лучше выложить на github и добавить ссылку в статью.
UFO landed and left these words here
Там только информация об ячейках вид полтит. Остальное вполне читаемо. На githab нормально бы хранилось.
Спасибо, отличная статья!

Но как оно решит
  |1 1|
--+---+
 1|   |
 1|   |
--+---+

вот в чём вопрос ,-) (по ссылке, в секции «Трудные сканворды», есть упоминание других типов сканвордов, которые, боюсь, ваша прога не решит, хотя однозначное решение есть)

а вообще, решить задачу, — значит найти решение(-я) или доказать, что его нет.

Успехов! Тема интересная.
Вы правы, оно не решит этот кроссворд. Программа зациклится, потому что не найдет никакой информации.
Эта программа решает кроссворды, которые являются в некотором смысле «хорошими» — кроссворды с единственным решением и там, где не нужно угадывать положение закрашенной (незакрашенной) клетки. В обратную сторону тоже верно: если программа решила кроссворд, а не зациклилась, то он является хорошим. Именно хорошие кроссворды, как правило, печатают в журналах. Я не ставил задачу исследовать типы кроссвордов, моя задача такова — решить журнальный кроссворд. Правда, не сильно большой, чтобы не переполнить память (количество всех расположений для заданной сетки можете легко подсчитать).
Метод полного перебора соберет всю возможную информацию, какую только можно собрать для конкретного расположения.
Вот с журналами вы ошибаетесь жестоко :-)
И в журналах, и на сайтах размещают какие попало кроссворды. Их никто не проверяет и они очень часто не допускают однозначной разгадки. Бывает, что пол сканворда — «шашечки». Упомянутый ресурс — единственный, где кроссворды проверяются хоть как-то. Они все хорошие в вашем понимании. Хотя это упрощённая хорошесть. Существуют вполне разрешимые кроссворды, но в вашем (и этого сайта) понимании ­— они плохие.
Я как раз и разгадывая в журналах наткнулся на кросворды в которых два решения. Очень удивился, но быстро понял что там обычная прога для генерации сканвордов, без всяких проверок. Ибо это конвеер.
По ссылке не понял в чём проблемы у «тёщи» со ртом: 3 дополнительных варианта противоречят условию по строке «4 5 4», странно как-то.
У «тещи» проблемы в самих данных. Если просуммировать все числа слева сетки (для строк), то получится 114, а если сверху (для столбцов) — 111.
А, тогда тем более. Сложно говорить про «неразрешимый» кроссворд, если он изначально некорректен, это как бы очевидно.
Но если аккуратно записать данные, без ошибок, то вот что дает программа:
Действительно, кроссворд «плохой».
Последний из примеров указанных по ссылке на самом деле однозначен — в 4-й снизу строке явно указано 4, 5, 4, поэтому перечисленные альтернативные варианты не подходят.

P.S. Прошу прощения, не заметил ответ Nikelandjelo
А если совместить это с обработкой изображений… ;-)
Если научить программу понимать, что находится на картинке, то она может разгадывать все кроссворды и отправлять в спортлото редакцию ответы. Какой бизнес можно было бы поднять: покупаешь пачку журналов по 20 рублей, выигрываешь с каждого по 500. Через неделю повторяешь.
Для такой схемы программе достаточно делать 90% рутинной работы, а оставшиеся 10 — додумывать по контексту человеку.
В Математике есть функции для работы с камерой и распознования образов. Хорошая задача для ИИ — увидеть кроссворд и его решить.
UFO landed and left these words here
Совсем некомфортно читать код Mathematica без подсветски синтаксиса.
Согласен с Вами полностью, но Хабрахабр не поддерживает подсветку кода в Mathematica.
Вы мне можете сказать, что можно было бы и цветные картинки вставить с кодом, но, в таком случае, желающие не смогли бы скопировать код.
Можно вставить картинку, и ниже под каждой — спойлер с кодом, как вариант. А вообще спасибо за статью. Знакомился с данным инструментом только в университете, интересно прочитать было.
Да, круто, но для кроссворда из примера в решении на SQL пришлось бы попотеть. Как никак, переборов будет 2600 ≈ 4.1 × 10180.
А нельзя ли на базе японских кроссвордов построить асимметричную криптографию? Закрытый и открытый ключ уже есть (причём открытый намного меньше закрытого), осталось придумать, как с их помощью шифровать или подписывать.
Далеко не каждый рисунок может быть зашифрован так, чтобы потом его можно было бы восстановить.
Одному открытому ключу будет соответствовать много закрытых. Это не проблема, если по открытому ключу нельзя восстановить ни один из подходящих закрытых. Пример: хеш-функции. Одному значению хеш-функции может соответствовать масса открытых текстов, но нельзя построить открытый текст по значению хеш-функции.

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

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

Для алгоритма шифрования нужно преобразовать открытый текст в соответствии с открытым ключом (условием кроссворда) так, чтобы только обладатель закрытого ключа (решения кроссворда) мог восстановить открытый текст. Так как одному открытому ключу в данном случае может соответствовать несколько закрытых, я не уверен, что шифрование возможно, по крайней мере с произвольным кроссвордом. Над алгоритмом подписи ещё стоит подумать.
Статья на смежную тему: «Cryptographic and Physical Zero-Knowledge Proof: From Sudoku to Nonogram».
Вообще-то подобные задачи решаются
с помощью SAT солверов.
Когда развлекал себя японскими кроссвордами, то пришел примерно к такому ходу решения:
— Для каждого столбца и строки ищем крайние возможные положения групп закрашенных клеток, если группа в обоих положениях пересекается с собой, то закрашиваем это пересечение. Это пересечение также может быть найдено с помощью вычислений.
— При поиске крайних положений также находим области где клетки вообще не закрашиваются — помечаем их как недоступные. Сюда же относятся 1 пустая клетка которая является границей групп в одноцветном кроссворде.
— Повторять пока в кроссворде проявляются изменения
Only those users with full accounts are able to leave comments. Log in, please.