Как сделать кроссворд в делфи

Обновлено: 02.07.2024

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

. У меня курсовая работа в 10 классе - кроссворд на англ. языке для 3-4 классов. Как делать - не знаю.
Может кто подскажет где можно достать готовый.

Репутация: 0

Репутация: 1

Я делал подобные попытки на Паскале. Не смог разобраться с процедурой заполнения сетки кроссворда словами из словаря. Она работала очень медленно, но сетку - заполняла. Алгоритм не эффективный был. Зато сохранилась огромная база русских слов.
Наверное тебе надо начать с составления подобной базы. Поищи в инете словари для подбора паролей - замечательная вещь.
Программы для составления кроссвордов существуют, без исходников разумеется, могу поделиться.

На дорожку…

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

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

Начало пути

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

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

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

Фрагменты

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

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

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

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

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

Шаблоны

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По горизонтали
1. Отображения текста в форме
6. Переводит число в строку
7. Многострочный текст можно разместить на форме с помощью объекта
9. Для задания промежутка времени в объекте Timer используется свойство
11. При одинарном щелчке мыши на объекте присходит событие
12. Возможность изменения ширины объекта

По вертикали
2. Какое свойство объекта Label автоматически определяет размеры, для размещения своего содержимого
3. Для редактирования и ввода текста можно использовать объект
4. Список с прокруткой в Delphi можно организовать с помощью объекта
5. Закрывает активную форму
8. Переводит целое число в строку
10. Видимость объекта на экране определяет

Обучение мобильной разработке на Delphi [2015] Леонов

Программирование на языке Pascal [2004] Рапаков

Учебное пособие ориентировано на широкий круг читателей, как начинающих знакомство с программированием, так и имеющих в нем достаточный опыт. Необходимое для новичков изложение азов предмета сочетается в книге с подробным и глубоким описанием тонкостей языка Pascal. Издание насыщено примерами и содержит множество полезных рекомендаций. Особое внимание уделено вопросам стиля в программировании, как линейном, так и объектно-ориентированном. Каждую главу завершают контрольные вопросы и задания, сложность которых дозированно возрастает от начальных глав к конечным. Эти материалы могут быть рекомендованы преподавателям информатики средней и высшей школ в качестве методических.

Теория и практика программирования на языке Pascal [2015] Расолько

Паскаль. Программирование на языке высокого уровня [2007] Павловская

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

Читайте также: