Comments 36
В вузе изучаете эту программу?
Нет, не изучаю. Просто задача довольно интересная.
UFO just landed and posted this here
Да, пожалуйста.
Решение японских кроссвордов
Решение японских кроссвордов
Спасибо, отличная статья!
Но как оно решит
вот в чём вопрос ,-) (по ссылке, в секции «Трудные сканворды», есть упоминание других типов сканвордов, которые, боюсь, ваша прога не решит, хотя однозначное решение есть)
а вообще, решить задачу, — значит найти решение(-я) или доказать, что его нет.
Успехов! Тема интересная.
Но как оно решит
|1 1| --+---+ 1| | 1| | --+---+
вот в чём вопрос ,-) (по ссылке, в секции «Трудные сканворды», есть упоминание других типов сканвордов, которые, боюсь, ваша прога не решит, хотя однозначное решение есть)
а вообще, решить задачу, — значит найти решение(-я) или доказать, что его нет.
Успехов! Тема интересная.
Вы правы, оно не решит этот кроссворд. Программа зациклится, потому что не найдет никакой информации.
Эта программа решает кроссворды, которые являются в некотором смысле «хорошими» — кроссворды с единственным решением и там, где не нужно угадывать положение закрашенной (незакрашенной) клетки. В обратную сторону тоже верно: если программа решила кроссворд, а не зациклилась, то он является хорошим. Именно хорошие кроссворды, как правило, печатают в журналах. Я не ставил задачу исследовать типы кроссвордов, моя задача такова — решить журнальный кроссворд. Правда, не сильно большой, чтобы не переполнить память (количество всех расположений для заданной сетки можете легко подсчитать).
Метод полного перебора соберет всю возможную информацию, какую только можно собрать для конкретного расположения.
Эта программа решает кроссворды, которые являются в некотором смысле «хорошими» — кроссворды с единственным решением и там, где не нужно угадывать положение закрашенной (незакрашенной) клетки. В обратную сторону тоже верно: если программа решила кроссворд, а не зациклилась, то он является хорошим. Именно хорошие кроссворды, как правило, печатают в журналах. Я не ставил задачу исследовать типы кроссвордов, моя задача такова — решить журнальный кроссворд. Правда, не сильно большой, чтобы не переполнить память (количество всех расположений для заданной сетки можете легко подсчитать).
Метод полного перебора соберет всю возможную информацию, какую только можно собрать для конкретного расположения.
Вот с журналами вы ошибаетесь жестоко :-)
И в журналах, и на сайтах размещают какие попало кроссворды. Их никто не проверяет и они очень часто не допускают однозначной разгадки. Бывает, что пол сканворда — «шашечки». Упомянутый ресурс — единственный, где кроссворды проверяются хоть как-то. Они все хорошие в вашем понимании. Хотя это упрощённая хорошесть. Существуют вполне разрешимые кроссворды, но в вашем (и этого сайта) понимании — они плохие.
И в журналах, и на сайтах размещают какие попало кроссворды. Их никто не проверяет и они очень часто не допускают однозначной разгадки. Бывает, что пол сканворда — «шашечки». Упомянутый ресурс — единственный, где кроссворды проверяются хоть как-то. Они все хорошие в вашем понимании. Хотя это упрощённая хорошесть. Существуют вполне разрешимые кроссворды, но в вашем (и этого сайта) понимании — они плохие.
Я как раз и разгадывая в журналах наткнулся на кросворды в которых два решения. Очень удивился, но быстро понял что там обычная прога для генерации сканвордов, без всяких проверок. Ибо это конвеер.
По ссылке не понял в чём проблемы у «тёщи» со ртом: 3 дополнительных варианта противоречят условию по строке «4 5 4», странно как-то.
Последний из примеров указанных по ссылке на самом деле однозначен — в 4-й снизу строке явно указано 4, 5, 4, поэтому перечисленные альтернативные варианты не подходят.
P.S. Прошу прощения, не заметил ответ Nikelandjelo
P.S. Прошу прощения, не заметил ответ Nikelandjelo
А если совместить это с обработкой изображений… ;-)
Что именно вы имеете в виду?
Если научить программу понимать, что находится на картинке, то она может разгадывать все кроссворды и отправлять в спортлото редакцию ответы. Какой бизнес можно было бы поднять: покупаешь пачку журналов по 20 рублей, выигрываешь с каждого по 500. Через неделю повторяешь.
В Математике есть функции для работы с камерой и распознования образов. Хорошая задача для ИИ — увидеть кроссворд и его решить.
Совсем некомфортно читать код Mathematica без подсветски синтаксиса.
Да, круто, но для кроссворда из примера в решении на SQL пришлось бы попотеть. Как никак, переборов будет 2600 ≈ 4.1 × 10180.
А нельзя ли на базе японских кроссвордов построить асимметричную криптографию? Закрытый и открытый ключ уже есть (причём открытый намного меньше закрытого), осталось придумать, как с их помощью шифровать или подписывать.
Далеко не каждый рисунок может быть зашифрован так, чтобы потом его можно было бы восстановить.
Одному открытому ключу будет соответствовать много закрытых. Это не проблема, если по открытому ключу нельзя восстановить ни один из подходящих закрытых. Пример: хеш-функции. Одному значению хеш-функции может соответствовать масса открытых текстов, но нельзя построить открытый текст по значению хеш-функции.
Кстати, японские кроссворды уже можно использовать как криптографическую хеш-функцию. Хочется же чего-то большего, например, асимметричной криптографии.
Чтобы сделать алгоритм цифровой подписи, нужно придумать преобразование закрытого ключа (решения кроссворда), зависящее от подписываемого числа, такое, чтобы по результату нельзя было восстановить закрытый ключ или его часть, однако можно было проверить соответствие открытому ключу и подписываемому числу.
Для алгоритма шифрования нужно преобразовать открытый текст в соответствии с открытым ключом (условием кроссворда) так, чтобы только обладатель закрытого ключа (решения кроссворда) мог восстановить открытый текст. Так как одному открытому ключу в данном случае может соответствовать несколько закрытых, я не уверен, что шифрование возможно, по крайней мере с произвольным кроссвордом. Над алгоритмом подписи ещё стоит подумать.
Кстати, японские кроссворды уже можно использовать как криптографическую хеш-функцию. Хочется же чего-то большего, например, асимметричной криптографии.
Чтобы сделать алгоритм цифровой подписи, нужно придумать преобразование закрытого ключа (решения кроссворда), зависящее от подписываемого числа, такое, чтобы по результату нельзя было восстановить закрытый ключ или его часть, однако можно было проверить соответствие открытому ключу и подписываемому числу.
Для алгоритма шифрования нужно преобразовать открытый текст в соответствии с открытым ключом (условием кроссворда) так, чтобы только обладатель закрытого ключа (решения кроссворда) мог восстановить открытый текст. Так как одному открытому ключу в данном случае может соответствовать несколько закрытых, я не уверен, что шифрование возможно, по крайней мере с произвольным кроссвордом. Над алгоритмом подписи ещё стоит подумать.
Статья на смежную тему: «Cryptographic and Physical Zero-Knowledge Proof: From Sudoku to Nonogram».
Вообще-то подобные задачи решаются
с помощью SAT солверов.
с помощью SAT солверов.
Когда развлекал себя японскими кроссвордами, то пришел примерно к такому ходу решения:
— Для каждого столбца и строки ищем крайние возможные положения групп закрашенных клеток, если группа в обоих положениях пересекается с собой, то закрашиваем это пересечение. Это пересечение также может быть найдено с помощью вычислений.
— При поиске крайних положений также находим области где клетки вообще не закрашиваются — помечаем их как недоступные. Сюда же относятся 1 пустая клетка которая является границей групп в одноцветном кроссворде.
— Повторять пока в кроссворде проявляются изменения
— Для каждого столбца и строки ищем крайние возможные положения групп закрашенных клеток, если группа в обоих положениях пересекается с собой, то закрашиваем это пересечение. Это пересечение также может быть найдено с помощью вычислений.
— При поиске крайних положений также находим области где клетки вообще не закрашиваются — помечаем их как недоступные. Сюда же относятся 1 пустая клетка которая является границей групп в одноцветном кроссворде.
— Повторять пока в кроссворде проявляются изменения
Sign up to leave a comment.
Решение японских кроссвордов в Wolfram Mathematica