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

Ярким примером подобного решения может служить одна отечественная разработка. Это приложение, полностью автоматизирующее процесс построения так называемого скандинавского кроссворда - FineCrosser.

Отличительные особенности подобных кроссвордов, особо усложняющие жизнь авторам - это:
        - обязательное отсутствие пустых клеток в кроссворде;
        - высокая плотность, обуславливающая большое количество пересечений слов;
        - расположение загадок в клетках рядом со словом;
        - возможность установки картинок в кроссворд;
        - необходимость вписать кроссворд в заданный прямоугольник.

 

В чем проблема?  

<На рынке масса всяческих построителей кроссвордов> скажите Вы. <Да>, но ни один из них не решает проблему в полном объеме. Некоторые из них позволяют заполнять готовые сетки весьма скромных размеров словами (сеткой в данном случае называется поле кроссворда незаполненное словами), некоторые умеют с горем пополам строить сетки, но не умеют строить сетки с картинками. Кроме того, наполнить подобную сетку словами редко представляется возможным, так как сетка строится без оглядки на возможности используемого словаря. В общем, решение этой проблемы тем  интереснее, чем меньше вероятность её успешного решения, а она (вероятность), верите Вы это или нет, в приведенном случае достаточно мала. Самое забавное в этой истории то, что автор программы Александр Компанеец в жизни своей не составил лично ни одного кроссворда!

Задача построения скандинавского кроссворда более или менее приличных размеров, прежде всего, интересна тем, что не решается <в лоб> простым перебором, по крайней мере, за конечный промежуток времени. Обусловлено это тем, что количество вариантов, которые необходимо рассмотреть, выражается астрономическим числом, и растет в факториальной зависимости с увеличением размера кроссворда! Кроме того, очень сложно вписать кроссворд в заданный прямоугольник так, чтобы не оставалось пустых мест как это допускается в классических кроссвордах. Это условие в свою очередь создает следующую проблему - увеличение количества пересечений для каждого слова, что предъявляет очень серьезные требования к скорости поиска и подстановки слов в кроссворд.

Тем не менее, оригинальные алгоритмы программы справляются с этой задачей за секунды, минуты иногда часы в зависимости от заданных условий.

На построение больших кроссвордов уходят часы, а иногда и сутки. Но основной изюминкой является то, что весь процесс от построения сетки, установки картинок и заполнения сетки словами происходит без вмешательства оператора на протяжении всего процесса. Только звуковой сигнал сообщает о том, что очередной <сканворд> готов. Построенный кроссворд или кроссворды (их можно строить партиями) можно отредактировать, сохранить, экспортировать в несколько популярных графических форматов включая Corel Draw.

Что у нас с классикой? Да, программа строит и классические кроссворды (американские) и сетки к ним  с той же легкостью.  

Всё и сразу!

             Запускаем программу, создаем новый проект, задаем размер сетки. В этом Вам поможет пошаговый <Волшебник>.

           

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

            Можно никуда не <шагать>, а сразу нажать кнопку <Создать>, оставив более тонкие настройки алгоритма и других опций принятыми по умолчанию.

После создания нового проекта мы увидим два окна: слева - окно кроссворда, справа - окно словаря. Но к ним мы вернемся позднее. А сейчас нажмем кнопку <Построить законченный кроссворд> расположенную в левом верхнем углу окна кроссворда. Здесь следует отметить, что программа предоставляет также возможность построить только сетку, либо только заполнить предложенную сетку словами. Но для начала построим кроссворд простейшим способом, то есть всё и сразу!

           

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

:9 секунд. В общем-то, и всё.

           

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

            Кроссворд готов. Теперь его можно сохранить экспортировать или предварительно отредактировать ответы и вопросы.

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

<Дайте два!>  

            На это <вкусности> не заканчиваются. Если Вы нажмете кнопочку <Составить несколько кроссвордов>, то через некоторое время к своему удивлению обнаружите, что  кроссвордов в вашем проекте прибыло.

            

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

А точнее их количество увеличилось на число указанное в настройках при создании проекта, на закладке <Пакет>. Так же на этой закладке можно задать, насколько сильно сетка следующего кроссворда, должна отличаться от сетки предыдущего.  

           

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

            Посмотрим на время (левый нижний угол скриншота): 5 минут 47 секунд. У нас уже 6 кроссвордов!

Теперь ваша задача, как автора кроссвордов, упрощается в разы. Просто выбирайте понравившийся Вам кроссворд и сохраняйте его в нужном формате или печатайте на принтере.  

Что внутри?  

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

И так. Первое, настройка алгоритма программы:

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

Настройки хранятся индивидуально для каждого проекта, так же как и размер сетки и другие опции, так что Вам не придется запоминать или записывать их отдельно.

<Алгоритм> - метод рассмотрения вероятно тупиковых вариантов.

<Картинки> - встраивать ли картинки в кроссворд, с какой частотой, сколько и какие пропорции допустимы.

<Установка слов> - максимальный размер слова в кроссворде.

<Подбор слов> - как осуществлять подбор слов в кроссворд, это опция позволяет с меньшей вероятностью использовать часто повторяющиеся из кроссворда в кроссворд слова и/или использовать слова в случайной последовательности.

<Другое> - <Двойные загадки> - позволить алгоритму размещать до двух загадок в одной клетке, при этом клетка будет разделена на две части. <Случайна сетка> - генерировать сетку, используя элемент случайности.

<Замена символов> - часто при составлении и разгадывании кроссвордов существует неписанное правило, позволяющее рассматривать некоторые символы как идентичные, например, <И> и <Й>.  

            Второе, закладка <Слова>

            

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

<Расположение загадок> - как относительно слова, можно размещать клетки с загадками.

<Допустимое количество слов заданной длины в кроссворде> -

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

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

Словарь  

Качественный словарь - неотъемлемая часть кроссворда. Поэтому мы уделили ему особо много внимания. Программа имеет встроенный тематический словарь, позволяет добавлять и редактировать новые словари, как скачанные с официального сайта программы www.finecrosser.com, так и загруженные из простых текстовых файлов.

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

При построении кроссворда используются только слова отмеченные <галочкой>, так что Вы сами можете исключать нежелательные слова списком или по отдельности из перебора.

Кроме того, каждое слов в словаре может хранить как текстовое описание, так и соответствующее слову изображение. Пропорции и размер изображения, выраженные в клетках кроссворда можно выбрать самому, либо предоставить алгоритму программы сделать это автоматически при построении кроссворда.  

Кликните на изображение чтобы открыть иллюстрации к статье (в новом окне)

Как это работает?  

Программа весьма требовательна к ресурсам, хотя и способна работать на достаточно старых компьютерах с небольшим объемом (128М) оперативной памяти.    Минимальная конфигурация, на которой тестировалась программа: MS Windows 98, Pentium II 233, 64Mб. Но для комфортной работы Вам потребуется MS Windows XP, Pentium 4 или совместимый и 512 Мб оперативной памяти. Связано это с тем, что алгоритмы программы максимально используют оперативную память компьютера для эффективной индексации словаря и кэширования данных.  

Выводы.  

Проект FineCrosser постоянно развивается, и, сравнивая производительность программы с результатами, опубликованными три года назад в  следующей статье http://www.fcenter.ru/online.shtml?articles/software/utilities/6216, где указано, что кроссворд 24 на 18 клеток составлялся 30 часов, можно сказать, что автор не потратил это время зря. Наш результат для кроссворда такого же размера 44 секунды!

За время написания этой статьи FineCrosser составил около 30 кроссвордов размером 17 на 21, работая в фоновом режиме и используя встроенный словарь, на том же компьютере, на котором я печатал эту статью (MS Windows XP, Celeron 1.7Гц, 512Мб). Что здесь говорить?!

Цена - $65 или 1800 рублей в пересчете на сэкономленное время, я думаю, даже занижена, если Вы занимаетесь составлением кроссвордов профессионально. Если нет, демоверсия  программы не имеет ограничений по времени использования, и позволит Вам самим без труда убедиться в том, как легко составлять и сохранять кроссворды, используя этот уникальный в своем роде инструмент. Демоверсия не позволит экспортировать и печатать результаты вашей работы.

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

 

FineCrosser Pro