Как научиться составить кроссворд

МЕТОДИЧЕСКИЕ
РЕКОМЕНДАЦИИ ПО СОСТАВЛЕНИЮ КРОССВОРДОВ

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

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

Затраты времени на составление кроссвордов
зависят от объёма информации, её сложности и определяются преподавателем.
Ориентировочное время на подготовку одного кроссворда объёмом не менее 10 слов
– 1 ч.

Алгоритм самостоятельной работы по
составлению кроссворда:

1.    внимательно прочитайте учебный
материал по изучаемой теме (конспекты, дополнительные источники);

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

3.    составьте вопросы к выбранным
понятиям (каждому понятию надо дать правильное, лаконичное толкование);

4.    продумайте дизайн кроссворда, его
эстетическое оформление;

5.    начертите кроссворд и оформите
список вопросов к нему;

6.    оформите ответы на кроссворд на
отдельном листе;

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

Общие правила составления кроссвордов:

·        
загаданные
слова должны быть в именительном падеже и единственном числе, кроме слов,
которые не имеют единственного числа;

·        
не
используются слова, пишущиеся через тире и имеющие уменьшительно – ласкательную
окраску;

·        
не
используются аббревиатуры и сокращения;

·        
в каждую белую
клетку кроссворда вписывается одна буква;

·        
каждое слово
начинается в клетке с номером, соответствующим его определению, и заканчивается
чёрной клеткой или краем фигуры;

·        
имён
собственных в кроссворде может быть не более 1/3 от всех слов;

·        
не следует
применять при составлении кроссвордов слова, которые могут вызвать негативные
эмоции, жаргонные и нецензурные слова;

·        
не желательно
при создании кроссвордов употреблять малоизвестные названия, устаревшие и
вышедшие из обихода слова;

·        
начинать
составлять кроссворд рекомендуется с самых длинных слов.

Правила оформления кроссвордов:

·        
кроссворд
может быть оформлен от руки на листах формата А 4 или набран на компьютере с
использованием любого текстового или табличного редактора и распечатан на
принтере;

·        
при
составлении кроссворда можно использовать специальные компьютерные программы
типа «Hot Potatoes», «Eclipse Crossword», «Decalion» или бесплатные онлайновые
сервисы типа «Фабрика кроссвордов». При этом кроссворд должен быть сохранён на
электронный носитель в виде исполняемого файла и может быть представлен в
электронном виде;

·        
рисунок
кроссворда должен быть чётким;

·        
сетка
кроссворда должна быть выполнена в двух экземплярах:

1-й экземпляр – с заполненными словами;

2-й экземпляр – пустая сетка только с
цифрами позиций.

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

·        
каждому слову
в сетке кроссворда присваивается номер. При этом номера расставляются
последовательно слева направо, от верхней строчки к нижней;

·        
ответы на
кроссворд оформляются на отдельном листе.

·        
готовая работа
предоставляется на контроль в установленный срок.

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

КРИТЕРИИ
ОЦЕНКИ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО СОСТАВЛЕНИЮ КРОССВОРДА

Оценка «5» (отлично) выставляется, если термины и определения написаны
грамотно, допускается 1 ошибка; в содержан кроссворда используются термины по
изучаемой теме; определение терминов не вызывает у обучающегося затруднений;
определения терминов не повторяют дословно текст учебника или конспекта;
кроссворд содержит не менее 15-10 слов информации; эстетически, аккуратно и
точно оформлен в соответствии с правилами оформления; кроссворд оформлен
иллюстрациями; сетка кроссворда имеет заливку, красочно оформлен; при
оформлении кроссворда использовано специальное программное
обеспечение; содержание соответствует теме; грамотная формулировка
вопросов; кроссворд выполнен без ошибок; представлен на контроль в срок.

Оценка «4» (хорошо) выставляется, если содержание материала в
таблице соответствует заданной теме, но есть недочёты: ячейки таблицы
заполнены материалом, подходящим по смыслу, но представляет собой пространные
пояснения и многословный текст; кроссворд содержит не менее 10 слов
информации; не достаточно грамотная формулировка вопросов; в
оформлении таблицы имеются незначительные недочеты и небольшая
небрежность; эстетически оформлен; представлен на контроль в срок.

Оценка «3» (удовлетворительно) выставляется, если студент работу не
выполнил в полном объёме: кроссворд содержит менее 8 – 9 слов информации;
содержание ячеек таблицы не соответствует заданной теме; имеются не заполненные
ячейки; оформлен небрежно; содержание не вполне соответствует теме; не
точная формулировка вопросов; кроссворд выполнен с ошибками; не представлен на
контроль в срок.

Методические рекомендации

 “Как составить предметный кроссворд”

Почему учащимся важно учиться составлять кроссворды

Составление кроссвордов учащимися – одна из часто используемых форм работы с учебным материалом, которая позволяет эффективно решать многие дидактические задачи:
1) достижение личностных результатов учебной деятельности: 
а) развитие мотивации к изучению учебного предмета; 
б) использование для создания кроссворда личностно значимой информации; 
в) расширение кругозора.
2) достижение метапредметных результатов учебной деятельности: 
а) регулятивных умений (целеполагание, планирование, самоконтроль, коррекция, оценка);
б) коммуникативных умений (сотрудничество с учителем, постановка вопросов); 
в) эффективных приёмов информационного поиска и оформления его результатов (выбор источников информации, анализ и оценка найденной информации, чёткое изложение мыслей, презентация кроссворда и др.).
3) достижение предметных результатов учебной деятельности: 
а) закрепление понятий темы, по которой составляется кроссворд; 
б) более глубокое изучение учащимися материала.

Этапы создания предметного кроссворда

Работа по созданию предметного кроссворда включает пять этапов.
1. Формирование информационной потребности. 
Необходимо предлагать учащимся составлять кроссворды по темам, которые позволяют 
2. Формулировка и уточнение информационного запроса, определение круга источников информации.
Для создания кроссворда необходимо рекомендовать учащимся использовать различные информационные источники: учебник; дополнительная литература, в которой рассматриваются изучаемые вопросы; интернет (для уточнения некоторых формулировок, поиска иллюстративного материала). 
3. Составление кроссворда.
На данном этапе учащимся предлагается использовать следующий алгоритм.
1. Составьте перечень слов по выбранной теме. Проанализируйте соответствующие теме параграфы учебника. При необходимости используйте дополнительные источники (книги, журналы, интернет). 
Примечания. 
1. В традиционных кроссвордах не используются прилагательные, слова, которые пишутся с дефисом, однокоренные слова.
2. Слова-ответы должны быть существительными в именительном падеже и единственном числе, множественное число допускается только тогда, когда оно обозначает единственный предмет.
3. В тематических кроссвордах, этими правилами можно пренебречь (при необходимости).
2. Составьте к каждому слову текстовое определение.
Оно должно в описательной или вопросительной форме (первый вариант более предпочтителен) указывать слово, являющееся ответом. 
Определения должны содержать достаточно информации для разгадывания слова и раскрывать его с наименее известной стороны, а также должны быть верными, лаконичными, исключающими двоякое толкование. 
3. Составьте сетку кроссворда.
Способ 1. Составьте сетку кроссворда, используя бумагу в клетку. 
Способ 2. Составьте сетку кроссворда, вычерчивая и заполняя таблицу в приложении Excel или Word. 
Способ 3. Используйте специальные программы, например, сайты «Cross: составь свой кроссворд онлайн» (http://cross.highcat.org); «Фабрика кроссвордов» (http://puzzlecup.com).
Примечания.
1. В каждую клетку кроссворда вписывается одна букв.
2. Каждое слово начинается в клетке с номером, соответствующим его определению, и заканчивается чёрной клеткой или краем фигуры.
3. Слова должны быть записаны в именительном падеже и единственном числе, кроме слов, которые не имеют единственного числа.
4. Пронумеруйте сетку кроссворда.
Номера расставляйте, двигаясь по сетке кроссворда сверху вниз, слева направо. Номер записывайте в той клетке, с которой начинается слово.
5. Продумайте и выполните оформление кроссворда.
Способ 1. Раскрасьте кроссворд, выделив в его сетке определённые клетки каким-либо цветом, или изобразите линии сетки цветом.
Способ 2. «Наложите» сетку кроссворда на изображение (рисунок, фотографию), которое будет фоном.
Способ 3. Поместите различные изображения (фотографии, рисунки, формулы и т. п.) в оставшиеся между сеткой кроссворда места и вокруг неё.
6. Напишите (напечатайте) текстовые определения.
Укажите слова, которые располагаются по горизонтали и по вертикали. 
При наличии в кроссворде ключевого слова, составьте и укажите его текстовое определение. 
7. Проверьте правильность кроссворда и исправьте ошибки (при необходимости).
Проверьте: 
1) правильность написания слов (орфография) в сетке и текстовых определениях; 2) соответствие текстовых определений и ответов на них в сетке (для этого нужно решить кроссворд, не заглядывая в ответы).
8. Предложите решить кроссворд одноклассникам или родителям.
4. Проверка и оценка составленного кроссворда учителем. 
При оценке предметного кроссворда важно учитывать следующие критерии:
1) соответствие слов в кроссворде заданной или выбранной теме;
2) правильность и точность текстовых определений;
3) соблюдение правил составления кроссвордов, указанных в алгоритме;
4) оформление кроссворда.
5. Использование составленного кроссворда в учебной деятельности.
Кроссворды, составленные учащимся не должны ложиться “мёртвым грузом” в папках у учителя. Их необходимо использовать при проведении уроков и во внеурочной деятельности (при проведении внеклассных мероприятий, предметных олимпиад, подготовке газет и т. п.).

Пример работы, созданной учащимися

Материалы сайта http://ped-kopilka.ru/ 

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

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

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

Кроссворд помогает:

• организовать самостоятельную работу;
• вызвать интерес к изучаемой теме;
• формированию терминологической грамотности, то есть более прочному усвоению терминологический аппарата учебной дисциплины.

Виды кроссвордов

При составлении кроссвордов необходимо придерживаться принципов наглядности и доступности.

Правила составления кроссворда

1. Не допускается наличие “плашек” (незаполненных клеток) в сетке кроссворда.
2. Не допускаются случайные буквосочетания и пересечения.
3. Загаданные слова должны быть именами существительными в именительном падеже единственного числа.
4. Двухбуквенные слова должны иметь два пересечения.
5. Трехбуквенные слова должны иметь не менее двух пересечений.
6. Не допускаются аббревиатуры (ЗиЛ и т.д.), сокращения (детдом и др.).
7. Не рекомендуется большое количество двухбуквенных слов.

Преимущества кроссворда как метода обучения

1. Позволяет детализировать конкретные разделы и сложные темы учебной дисциплины.
2. В кроссворде, отгадываемые единицы (термины), должны быть однозначными, лаконичными и конкретными. За счет этого и обеспечивается быстрое запоминание термина и его значения.
3. Активизируется внимание, память, логическое мышление, речь.

Формы работы с кроссвордом:

1. Организация самостоятельной внеурочной деятельности обучающихся.

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

2. Организация работы на занятии.

На этапе повторения материала: пятиминутные проверочные работы.

На этапе проверки знаний: работа с терминами и понятиями учебной дисциплины по конкретной теме.

На этапе изучения нового материала: предвосхищение будущего результата.

Этапы составления учебных кроссвордов

1. Выбираем вид крссворда: лучше использовать ассиметричные, нестандартные, со свободным расположением слов.
2. Составляем список терминов (в зависимости от типа занятия и его целей). Старайтесь включить в кроссворд как общенауные термины, так и специальные.
3. Составляем вопросы к выбраным терминам.
4. Нумеруем поле и вопросы.
5. Печатаем кроссворд (при необходимости).

Критерии оценивания результата

Несомненно, критерии зависят от многих факторов и должны определяться преподавателем индивидуально, можно лишь выделить отдельные базовые пункты:

• доля отгаданных слов;
• доля ключевых терминов;
• точность и однозначность формулировок вопросов.

Составление кроссвордов в Microsoft Office

Создание кроссвордов с применением Microsoft Word, Microsoft Excel, Microsoft PowerPoint.

Достоинства: доступность использования (предустановленное ПО); не нужно время для освоения программ.

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

Специальные он-лайн сервисы для создания кроссвордов

Фабрика кроссвордов

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

Online Test Pad

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

Cross

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

Hot potatoes – Программа для создания кроссвордов. Данное приложение интегрируется, а то и по умолчанию стоит в СДО Мудл.Имеется инструкция по работе на русском языке – Инструкция по созданию кроссворда в Hot Potatoes.

Пример генерации кроссворда

Пример кроссворда с использованием общенаучных и специальных терминов по специальности “Пожарная безопасность”.

Полезные ресурсы по теме:

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

Цветные и черно-белые кроссворды — этот сайт полностью посвящен японским кроссвордам. Любой из них можно распечатать или решать в режиме он-лайн. А для зарегистрированных пользователей доступна возможность сохранения кроссвордов.

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

Учимся играя — представлены кроссворды, викторины, ребусы, головоломки  по всем школьным предметам.

Сочетание кроссворда с другими методами арт-педагогики (коллаж, глоги, интеллект-карта, инфографика, эссе, инсценировки) позволяет расширить возможности метода и задействовать разные типы восприятия информации (зрительная, слуховая и т.д.).

Алгоритм формирования кроссвордов

Эта история начинается с публикации «Самый сложный кроссворд, составленный компьютером». В ней приведен один из самых сложных кроссвордов, составленных программой (см. ниже).

Я был уверен, что все кроссворды давным-давно генерируются программно и был несколько удивлен тем, что это может быть проблемой. Замечу, что речь идет именно о «канадских» кроссвордах, в которых каждое слово имеет пересечение с другим словом на каждой букве или очень близких к ним по сложности. В моей работе аналитика, не так много действительно сложных задач, поэтому мне стало интересно попробовать разработать алгоритм, который мог бы это сделать. Результат размышлений, подкрепленный программой для генерации кроссвордов, приводится в этой статье.

Для заполнения кроссворда всегда используется перебор. Мы ставим первое слово, затем все следующие, проверяя, чтобы буквы на пересечениях совпадали с буквами в словах, поставленных ранее. И так, пока все слова не будут поставлены. Казалось бы – нет ничего проще. Однако простой подсчет количества итераций подбора слов для кроссворда средней длины на 50 слов может изменить это мнение. Так, для установки любого слова, кроме первого, при наличии 1 000 слов соответствующей длины в базе и наличия всего одного заполненного ранее слова на пересечении, в среднем понадобится 1 000/33 = 30 итераций (нам, в среднем, нужно будет просмотреть 30 слов, прежде чем нам попадется слово, имеющее нужную букву на позиции заполненного ранее пересечения). При наличии более одного заполненного ранее слова-пересечения, это количество будет резко расти. Простой подсчет показывает, что для заполнения 50 слов, нам нужно выполнить 30^(50-1) итераций. Это миллиарды миллиардов итераций. Даже на современных компьютерах, это потребует дни и месяцы работы. И здесь на первое место выходит уже не собственно перебор, а алгоритм, который позволит сократить время генерации кроссворда на много порядков.

На дорожку…

Сразу, «на берегу», мы должны принять то, что генерация кроссворда будет состоять из двух этапов:

• Анализ – создание плана генерации, основным результатом которого является определенная последовательность генерации слов кроссворда и другие данные, которые будут помогать на этапе генерации.
• Генерация – последовательное заполнение сетки кроссворда словами, методом полного перебора всех возможных вариантов, с учетом данных, полученных на этапе анализа.

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

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

И последнее. В статье будет опущено все, что касается генерации базы слов для программы. Эта часть «стоила» не менее 50% всего затраченного времени. Сейчас в базе более 158 тыс. слов, из которых более 125 тыс. являются уникальными. База в максимальной степени вычищена программным способом, однако все еще требует к себе внимания в ручном режиме. Я не стал каким либо способом закрывать или шифровать базу – она лежит открытая в текстовом виде и простейшем key-value формате. Вы можете удалить или добавить в ней слова, подкорректировать описания или полностью заменить своей (например, на другом языке).

Начало пути

Первое, что нужно определить – последовательность заполнения слов. Для этого имеются весьма простые и очевидные решения.

Решение № 1: Слова будут генерироваться в последовательности, зависящей в первую очередь, от их длины. Чем длиннее слово, тем больше у него может быть пересечений и тем труднее будет найти слово для установки. Напротив, самые короткие слова, длиной в 2 или 3 буквы, будут иметь минимальное количество пересечений и их максимально удобно подбирать на завершающем этапе генерации. Данное решение используется на этапе анализа.

Решение № 2: Из слов с одинаковой длиной, в первую очередь будут устанавливаться слова с наибольшей сложностью установки. Сложность установки – расчетный параметр, который показывает «насколько сложно будет подобрать значение в это слово» и «насколько большая будет цена ошибки, если слово подобрать не удастся». Понятно, что слова одинаковой длины, например, 5 букв, могут пересекаться как с одним словом, так и сразу с пятью, при этом сложность установки будет совершенно разная. Данное решение используется на этапе анализа.

Решение № 3: C учетом предыдущих решений, слова у нас расположены в такой последовательности, которая не гарантирует пересечение двух соседних слов между собой. Это означает, что если мы не нашли слово для установки, тогда нужно изменить не предыдущее слово, а одно из ранее установленных слов, которые пересекаются с этим словом и по сути задают для него условия подбора. Логично из всех ранее установленных слов-пересечений, заменить слово, установленное последним, чтобы откатиться на минимальное количество слов генерации. Данное решение используется на этапе генерации.

Фрагменты

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

На рисунке цветами показана последовательность установки первых слов в сетку кроссворда в порядке, соответствующем известному «Каждый охотник желает знать, где сидит фазан». Первым будет установлено слово, помеченное красным. После него – слово, помеченное желтым и т.д. После установки всего 2-х слов в кроссворде образовался локальный фрагмент, помеченный голубым цветом.

Прежде, чем продолжить, определимся сначала с терминологией:

• Фрагмент – группа слов в количестве от 1 слова до 50% от общего количества слов кроссворда, генерация которых никак не зависит от всех остальных, еще не поставленных слов.
• Стартовое слово – слово, после установки которого образовался фрагмент (на рисунке выше – это слово, выделенное желтым цветом).
• Первое слово – слово фрагмента, имеющее минимальную очередность установки из всех слов фрагмента.
• Глубина фрагмента – количество слов, составляющих фрагмент.

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

Решение № 4: Для каждого устанавливаемого слова будет выполняться поиск фрагментов. Все слова, принадлежащие одному фрагменту будут иметь последовательную очередность установки, начиная от стартового слова, либо от первого слова фрагмента. Данное решение используется на этапе анализа.

В данный момент, часть алгоритма по изменению последовательности генерации слов фрагментов выглядит следующим образом:

1. Находим фрагменты.
2. Определяем сложность заполнения фрагмента.
3. Определяем слово, за которым нужно расположить все слова фрагмента по следующим правилам:
4. Слова, являющиеся членами фрагментов, устанавливаем друг за другом.

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

1. Определяется последовательность генерации слов.
2. Выполняется подбор и установка слова с учетом ранее установленных слов.
3. При отсутствии слова для установки, выполняется откат на последнее пересекающееся с ним слово, поиск которого продолжается так, как будто предыдущее его значение не было найдено вовсе.

Проверено – он реально работает на сетках до среднего уровня сложности. Однако, по мере усложнения сетки кроссворда и увеличении количества слов, количество удачных попыток генерации, стремится к 0. Собственно, с этого момента и начинается самое интересное.

Шаблоны

Первый вопрос, который приходит в голову – можно ли как-нибудь уменьшить количество откатов? Ведь каждый откат на несколько слов назад может стоить десятки и сотни тысяч итераций. Логически верным шагом становится добавление правил, которые уменьшают количество ошибок установки слов, вроде, не ставить мягкий или твердый знак в клетку, с которой начинается слово и т.д. Если не лезть глубоко, описать большинство этих правил для русского языка довольно просто, но есть проблема – они будут абсолютно бесполезны, например, для английского. Мне же хотелось сделать универсальный алгоритм, не зависящий от языка.

Размышления над этим вопросом привели к следующему: «как было бы хорошо, чтобы для каждого еще неустановленного слова, пересекающего текущее устанавливаемое слово, было гарантировано наличие вариантов для установки».

Так появилась идея использовать шаблоны, подобные команде LIKE в Transact-SQL. Шаблон – это символьная строка, по которой будет выполняться сравнение слов. Сам шаблон включает буквы и символы-шаблоны. Во время сравнения с шаблоном необходимо, чтобы буквы в точности совпадали с символами, указанными в строке. Символы-шаблоны могут совпадать с произвольными элементами символьной строки.

Решение № 5: Для каждого стартового слова будут рассчитываться шаблоны всех пересекающихся с ним слов. Стартовое слово должно иметь буквы строго из списка в шаблоне, соответствующего позиции буквы пересечения. Данное решение используется на этапе генерации.

Примеры шаблонов для слов из трех букв приведены ниже:

• Шаблон: “___”

1. Буква № 1: Ё А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я
2. Буква № 2: Ё А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Э Ю Я
3. Буква № 3: Ё А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Э Ю Я

• Шаблон: «ДО_»

1. Буква № 1: Д
2. Буква № 2: О
3. Буква № 3: Г К М Н

На примере последнего, читать шаблоны следует так: для слова из 3-х букв, у которого первые две буквы равны «ДО», в базе есть слова, у которых последняя буква равна одной из «Г К М Н».

Акселераторы

Вернемся снова к фрагментам. Посмотрите на рисунок ниже.

В нем серым отмечены клетки слов, установленных ранее. При установке слова, помеченного красным, образуются сразу два фрагмента, отмеченных голубым и фиолетовым цветами.

Если вы посмотрите на фиолетовый фрагмент, то увидите, что он связан со стартовым словом одним единственным пересечением. И это прекрасно! Это дает нам возможность воспользоваться еще одним решением.

Еще немного терминологии:

• Акселератор – стартовое слово, имеющее дочерний фрагмент, имеющий с ним одно единственное пересечение. Свое название он получил за свойство ускорять генерацию фрагментов на порядок и более.

Решение № 6: При неудачной генерации фрагмента, для которого стартовое слово является акселератором, алгоритм будет хранить список букв, которые были установлены в стартовое слово на пересечении с одним из слов фрагмента для блокировки повторных установок слов, имеющих эти буквы на упомянутом пересечении. Данное решение используется на этапе генерации.

Алгоритм использования акселераторов приведен ниже.

Сначала – как это работает без акселератора:

• Выполняется поиск и установка всех слов фрагмента.
• Если заполнение фрагмента выполнено успешно, то идем дальше, иначе – меняется стартовое слово и процесс заполнения слов фрагмента повторяется.

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

Как это работает с акселератором:

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

Глубина фрагмента та же. Однако, для перебора всех возможных вариантов, нужно количество итераций для заполнения фрагмента умножить уже не на количество вариантов для стартового слова, а всего на 33 (количество букв в алфавите).

Динамическая балансировка сложностью установки

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

Однажды, при генерации кроссворда, программа выдала такое сообщение: «Время полного перебора: 11 471 день …». Это сообщение появляется только в том случае, если был выполнен перебор всех вариантов для самого первого слова и требуется найти для него новое значение. Программа уже затраченное время просто умножает на оставшееся количество вариантов. Меня это позабавило и заставило задуматься, можно ли это время конвертировать в результат? Идея состоит в том, чтобы обдуманно обрезать некоторые варианты перебора, имеющие минимальную вероятность успеха.

Основной тезис этого решения – пусть лучше программа за минимально возможное время выдаст отрицательный результат (т.е. среди наиболее оптимальных вариантов подбор не удался), чем будет заниматься подбором столько времени, что будут превышены все мыслимые границы.

Решение № 7: При установке слова, которое пересекают слова с большой сложность установки, запрещено ставить на позицию упомянутого пересечения буквы, частота применения которых в словах пересечениях минимальна. Данное решение используется на этапе генерации.

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

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

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

Тестирование

Для систематизации сеток по сложности генерации введен атрибут «Сложность генерации», который рассчитывается на основании количества слов, их длины и количества пересечений. По факту — более менее стабильно результат можно получать при сложности до 600 единиц. Все что выше — на удачу.

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

Сетка № 1

Несложная тестовая сетка для опытов, с небольшим количеством слов.

• Сложность генерации: 248
• Количество слов: 28
• Среднее время успешной генерации, сек.: 5 (от 1 до 32)

Подитог: Сетки такой сложности генерируются быстро и стабильно.

Сетка № 2

Это сетка посложнее. Это маленький «канадский» кроссворд, где все слова имеют пересечения на всех буквах.

• Сложность генерации: 372
• Количество слов: 34
• Среднее время успешной генерации, сек.: 62 (от 1 до 472)

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

Сетка № 3

Эта довольно сложная сетка оказалась весьма «удобной» для генерации.

• Сложность генерации: 544
• Количество слов: 46
• Среднее время успешной генерации, сек.: 1 (от 1 до 2)

Подитог: Благодаря тому что эта сетка очень хорошо фрагментируется и пересечения имеются не на всех буквах длинных слов, программа генерирует его почти мгновенно.

Сетка № 4

А вот эта сетка уже имеет «целевую» сложность. Это полноценный «канадский» кроссворд, правда, далеко не самый сложный.

• Сложность генерации: 570
• Количество слов: 78
• Среднее время успешной генерации, сек.: 250 (от 10 до 989)

Подитог: Программа справилась! Успешный результат генерации, в самом крайнем случае, можно получить всего за 17 минут. Среднее время генерации чуть более 4 минут.

Сетка № 5

И, наконец – тот, самый сложный кроссворд, с которого все началось. В нем 72 слова, что не так уж и много. Однако, сложность генерации получилась очень высокой. Основной проблемой для генерации являются четыре самых длинных слова, с которыми пересекаются почти все остальные слова кроссворда. Они как кости скелета, на которые нужно нанизать все остальные слова. Откаты отбрасывает процесс генерации почти на самое начало. Таким образом, процесс генерации этой сетки можно сравнить с Сизифом, толкающим камень в гору. И каждый раз, когда до цели остается совсем немного, камень скатывается к самому началу пути.

Увы – эта вершина осталась непокоренной! Я запускал несколько генераций с разными настройками, с лимитом по длительности до 10 часов, однако ни одна из них не была завершена успешно. Времени явно не хватает. Кто знает, может быть эта непокоренная вершина вдохновит кого-нибудь на новый штурм!

Резюме

И все-таки да! Генерация кроссворда, даже для самых современных компьютеров, является сложной задачей. Я уверен, что возможности улучшить этот алгоритм далеко не исчерпаны, однако, независимо от возможностей алгоритма и мощности компьютера, всегда можно усложнить сетку кроссворда еще чуть-чуть, чтобы программа пообещала Вам результат, лет, через 20-30.
Надеюсь, вам было интересно, и вы дочитали до конца.