Японский кроссворд — головоломка, в которой по набору чисел нужно воссоздать исходное черно-белое изображение. Каждой строке и каждому столбцу пикселей соответствует свой набор, каждое число в котором, в свою очередь, соответствует длине блока подряд идущих черных пикселей. Между такими блоками должен быть хотя бы один белый пиксель, но точное их число неизвестно. Журналы, целиком посвященные этим головоломкам, есть в большинстве газетных киосков, так что, думаю, почти все с ними хоть раз да встречались, и потому более подробное описание здесь можно не приводить.
В какой-то момент мне захотелось «научить компьютер» решать японские кроссворды так, как решаю их я сам. Никакой высокой цели, just for fun. Потом уже были добавлены способы, которые сам я применять не могу в силу ограниченных возможностей человеческого мозга, но, справедливости ради, со всеми кроссвордами из журналов программа справляется и без них.
Итак, задача простая: решить кроссворд, а если решений много, то найти их все. Решение написано на Haskell'е, и, хотя код достаточно существенно дополняет словесное описание, даже без знания языка общую суть понять можно. Если хочется пощупать результат вживую, на странице пректа можно скачать исходники (бинарных сборок не выкладывал). Решения экспортируются в Binary PBM, из него же можно извлекать условия.
Несмотря на то, что я пытался писать максимально понятно, это не в полной мере мне удалось. Под катом очень много букв и кода и почти нет картинок.
Читать полностью »
