Программа "Генератор кроссвордов"

1. Введение

1. История кроссворда

Кроссворд появился в начале 20 века и быстро завоевал популярность во всем мире. Слово кроссворд образовалось из двух английских слов cross - пересечение  и word - слово. Решение кроссвордов  тренирует память и расширяет  кругозор, некоторые типы кроссвордов  способствуют развитию сообразительности  и ассоциативного мышления. Медики стали использовать кроссворд как  успокаивающее средство. Преподаватели  тоже применяют кроссворд в своей работе, это позволяет учащимся усваивать знания в игровой форме. Сфера применения кроссвордов постоянно расширяется, кроссворды применяются для тестирования профессиональных качеств.

2. Основные  методы составления кроссворда. Машинный и творческий подходы к заполнению сетки

Составление кроссворда –  занятие достаточно трудоемкое и  кропотливое, требующее внимательности и усидчивости. Для составления  кроссвордов необходимо иметь доступ к словарям со списками слов и толкований.

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

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

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

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

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

Целью настоящего курсового  проекта является разработка классического  генератора кроссвордов, а также  закрепление полученных навыков  в области программирования на языке  C++, усвоение ключевых понятий концепции объектно-ориентированного программирования, проявления творческих подходов к разработке сложного программного обеспечения.

2. Постановка задачи

Составить генератор классических кроссвордов.

1. Предметная область

Кроссворд - это задача-головоломка, заключающаяся в заполнении буквами  перекрещивающихся рядов клеток так, чтобы по горизонталям и вертикалям получились заданные по значениям слова. В переводе с английского языка - cross-word означает пересечение слов. Для заполнения классического кроссворда в качестве вопросов используют толкования слов, однако, есть и другие варианты, например использование слов-анаграмм – слов, которые образуются из текущего слова перестановкой букв. Например «врач è рвач».

Рис. 1Типичная сетка классического суперкроссворда

 

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

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

Рис. 2Типичный современный сканворд

2. Обзор существующих решений

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

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

Одна из таких программ – «Крестословица» (http://kslov.chat.ru/obz.html). Ранее это был коммерческий проект, однако спустя некоторое время автор пустил свою разработку в мир фриварных (freeware) программ, однако возможности у этой программы очень даже неплохие. Она способна заполнить сложную сетку как классического, так и сканворда, а также позволяет корректировать сетку в ручном режиме.

следующая разработка – Crossword Forge 5.25 (http://f1cd.ru/soft/windows/useful/crossword_generator/crossword_forge_525_20/) Она будет интересна людям, которые любят на досуге посидеть и поразгадывать кроссворды, а также всем, кто хочет быть в роли составителя, причём для этого не нужно особых навыков: подберите вопросы и ответы на них, заполните поля и вот кроссворд готов!

3. Требования к  программе

Для работы программы необходима операционная система Windows XP (SP1-SP3). Программа не тестировалась на старых версиях Windows 3-Windows 98.

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

Программа к ресурсам не требовательна.

4. Функции программы.

Основная функция программы  – составление кроссворда.

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

Сохраненную сетку можно  загрузить, подкорректировать и  сохранить под другим именем.

Рис. 3Главное окно приложения

Описание кнопок.

База слов – позволяет просмотреть базовый словарь, состоящий из нескольких тысяч слов.

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

Очистка – очистка сетки от слов. Чистится без предупреждения.

Рисование и разметка – переключает между режимами рисования сетки и блокировеи изменения сетки – режим только просмотра.

Размер сетки – позволяет задать размер:

Рис. 4Изменение размеров сетки

После задания сетки нужно  повторно нажать на кнопку Размер сетки. Это скроет панель ввода размеров и выровняет размеры клеток. Изменение размеров сетки приводит к полному уничтожению данных кроссворда.

5. Ручное составление  кроссворда

Щелчок по списку масок  приведет к появлению нгового  списка – по заданной маске будут  подобраны слова:

Рис. 5Подбор слов по маске

Щелчок по правому списку – впишет слово в кроссворд:

Рис. 6Подбор слов

После вставки слова обновляются  все маски:

Рис. 7Процесс составления кроссворда

6. Входные данные

Для работы программы нужен  словарь, которые хранится в базе данных WordBase.mdb.

В базе данных имеется только две таблицы – рабочая и словарь. Словарь Words состоит из полей:

Definition – толкование слова;

Length – длина слова;

Word слово в словаре.

Рабочая таблица mWorks состоит из полей:

Mask – маска слова для поиска в словаре

Ok – признак того, что слов заполнено;

Nom – номер слова;

Direction – направление слова (V/H);

Row в каком ряду в сетке слов начинается;

Col в какой колонке в сетке слово начинается;

Length длина слова.

7. Выходные данные

Каждая клетка в словаре  связана со структурой:

Рис. 8База слов

struct WCell

{

  char Cell;    //0 - Пустое  поле  // 1 Закрашенная клетка  2 - клетка с буквой

  unsigned int Start; // 0 - не  начало слова. не 0 - начало слова

  char Direction;     // 'V' / 'H'

  char Letter;        // буква

  bool Selected; //Выделение слова в сетке

};

Файл хранит в себе в  заголовке, состоящем из двух целых  чисел (unsigned int) размер сетки, затем описание сетки в виде вышеприведенной структуры.

3. Вычислительная  система

Для работы приложения необходима операционная система Windows (XP/2k/NT/Vista/Seven и другие линейки Windows).

Выбор именно этой системы  обоснован тем, что ее не надо «тонко»  настраивать, как например *nix системы.

Выбор языка программирования C++ обосновывается тем, что этот язык современный, хотя появился он давно, но современность его в том, что на базе его синтаксиса появляются новые языки, например C#, Java, что говорит о том, что синтаксис его удобный, лаконичный, но в тоже время мощный и гибкий, позволяющий создавать на языке изящные конструкции кода. Однако С++ опасен тем, что не контролирует работу программиста с памятью, поэтому надо четко отслеживать, чтобы не было утечек памяти, чтобы указатели указывали на существующие объекты. В противном случае ошибки, сделанные в программах на C++ могут привести (и приводят) к краху даже такой устойчивой системы, как Windows XP, что вынудит перезагрузить в итоге компьютер.

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

4. Объектно-ориентированное  программирование

Схема приложения

Описание функций

void __fastcall GridDrawCell(TObject *Sender, int ACol, int ARow,

          TRect &Rect, TGridDrawState State); отрисовка клеток кроссвордной сетки

  void __fastcall EditXChange(TObject *Sender); обработка события изменения размера сетки по горизонтали

  void __fastcall EditYChange(TObject *Sender); обработка события изменения размера сетки по вертикали;

  void __fastcall GridCellsSize(); выравнивание ячеек сетки

  void __fastcall btnModeClick(TObject *Sender); переключение между режимами отрисовки и просмотра

  void __fastcall CreateCrossword(); создание кроссворда (создание динамического массива заданной структуры)

  void __fastcall KillCrossword(); уничтожение кроссворда (очистка памяти)

  void __fastcall GridSelectCell(TObject *Sender, int ACol, int ARow,

          bool &CanSelect); обработчик события выбора клетки

  void __fastcall SetCell(int C, int R); настройка ячейки в зависимости от режима

  void __fastcall btnClearClick(TObject *Sender);  обработка нажатия очистки кроссворда

  byte __fastcall GetStartPosition(int PosX,int PosY); поиск в сетке признаков начала слова

  bool __fastcall CellBack(int PosX,int PosY); проверка выхода за пределы по горизонтали

  bool __fastcall CellUp(int PosX,int PosY); проверка выхода за пределы сетки по вертикали

  void __fastcall GetMasks(); пориск и формирование масок на основе сетки

  void __fastcall GetHorizontalMask(int yy,int xx); получение маски горизонтального слова

  void __fastcall GetVerticalMask(int yy,int xx); получение маски вертикального слова

  void __fastcall SetWord(int Nom,String Dir); запись слова в сетку

  void __fastcall GetWord(int Nom,String Dir); получение слова из сетки

  void __fastcall DbGridWorkCellClick(TColumn *Column); обработчки нажатия на список масок

  void __fastcall WriteWord(int Nom,String Dir); запись слова в кроссворд

  void __fastcall DbGridWordsCellClick(TColumn *Column); выбор слова из списка найденных

5. Описание аппартных  и программных средств

Для работы программы необходима операционная система Windows XP (SP1-SP3). Программа не тестировалась на старых версиях Windows 3-Windows 98.

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

Для работы программы необходим  в системе OLEDB провайдер.

Для работы программы необходим  IBM совместимый компьютер с утсановленной любой из операционных систем линейки Windows, начиная с версии Windows 2000.

Для работы программы желательно поддержка режима экрана 1920 на 1480.

6. Заключение

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

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

7. Список литературы

М. Эллис, Б. Строуструп. Справочное руководство по языку C++ с комментариями: Пер. с англ. - Москва: Мир, 1992. 445с.

Стенли Б. Липпман. C++ для  начинающих: Пер. с англ. 2тт. - Москва: Унитех; Рязань: Гэлион, 1992, 304-345сс.