Как стать автором
Обновить

Решение японских кроссвордов на Haskell

Haskell *
Из песочницы
Японский кроссворд — головоломка, в которой по набору чисел нужно воссоздать исходное черно-белое изображение. Каждой строке и каждому столбцу пикселей соответствует свой набор, каждое число в котором, в свою очередь, соответствует длине блока подряд идущих черных пикселей. Между такими блоками должен быть хотя бы один белый пиксель, но точное их число неизвестно. Журналы, целиком посвященные этим головоломкам, есть в большинстве газетных киосков, так что, думаю, почти все с ними хоть раз да встречались, и потому более подробное описание здесь можно не приводить.

В какой-то момент мне захотелось «научить компьютер» решать японские кроссворды так, как решаю их я сам. Никакой высокой цели, just for fun. Потом уже были добавлены способы, которые сам я применять не могу в силу ограниченных возможностей человеческого мозга, но, справедливости ради, со всеми кроссвордами из журналов программа справляется и без них.

Итак, задача простая: решить кроссворд, а если решений много, то найти их все. Решение написано на Haskell'е, и, хотя код достаточно существенно дополняет словесное описание, даже без знания языка общую суть понять можно. Если хочется пощупать результат вживую, на странице пректа можно скачать исходники (бинарных сборок не выкладывал). Решения экспортируются в Binary PBM, из него же можно извлекать условия.



Несмотря на то, что я пытался писать максимально понятно, это не в полной мере мне удалось. Под катом очень много букв и кода и почти нет картинок.
Читать дальше →
Всего голосов 64: ↑57 и ↓7 +50
Просмотры 26K
Комментарии 23

Решение японских кроссвордов одним запросом SQL

Ненормальное программирование *Oracle *SQL *
Привет хабр! Приближается день программиста, и я спешу поделиться своими ненормальными наработками.

Японский кроссворд — NP-полная задача, как и задача коммивояжёра, укладки рюкзака и др. Когда ее решает человек, следует последовательно определять гарантированно заполненные и пустые ячейки. Одну за другой вычеркивать колонки и строки, пока не сложится весь рисунок. Как же возможно запрограммировать решение подобной задачи на языке, который официально даже не является языком программирования, не содержит циклов и переменных? SQL — язык запросов, его главная задача — выбирать строки. Вот мы и будем генерировать множество всех возможных перестановок и, словно скульптор, отсекать все лишнее.

укусить себя за пятку
Всего голосов 172: ↑165 и ↓7 +158
Просмотры 59K
Комментарии 26

Как я за 4 часа решатель японских кроссвордов написал

Ненормальное программирование *Алгоритмы *
Лениво просматриваю выложенный недавно коллегами из «Сириуса» список курсов, проведенных у школьников… Так, а это что такое? «Поиск комбинаторных объектов с помощью SAT-солверов»? «Мы сделали решатель судоку, японских кроссвордов и прочего»?

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

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

Но тут же это предлагается… ШКОЛЬНИКАМ! Внутри зашевелилось шило в п... творческое начало и заявило: «Ну это, наверное, несложно прикрутить, раз ученикам предлагают. Неужели я не разберусь?? Вон, обещают, что питоновскую библиотеку используют, а питон я в целом знаю...»

А времени было около 9 вечера, что несколько притупило мой критический взгляд на сложность проблемы… (собственно, далее хроники 4-часового программирования)
Читать дальше →
Всего голосов 8: ↑8 и ↓0 +8
Просмотры 4.1K
Комментарии 1