Кроссворд алгоритмизация и программирование

От: https://github.com/vpelss/crosswords/blob/master/README.md

Алгоритм генерации кроссвордов Emogic Мой веб-генератор кроссвордов работает по адресу http://www.emogic.com/cgi/crosswords/ Он предназначен скорее как инструмент для изучения различных способов. Которыми алгоритмы могут генерировать кроссворды. И различий между ними. Он не предназначен для создания качественных головоломок New York Times. См.: Если вы хотите создать свой собственный сценарий генератора кроссвордов,это отличное место для начала. Он может быть неясен во многих областях. Но все же имеет много хороших идей. На этом сайте есть пример кода на языке C. 

На его сайте есть несколько логических ошибок. Основанных на предположениях. одна большая проблема заключается в том. Что поиск букв так же хорош (или эквивалентен) поиску слов. В некотором смысле это так. Но не тогда. Когда речь идет о времени. Необходимом для создания кроссворда. Пожалуйста. Используйте ссылку Почему PERL? PERL не известен своей скоростью. Он также имеет более высокую нагрузку на память для управления переменными. Но у него есть несколько преимуществ. Регулярные выражения являются мощными и быстрыми. Хэш-переменные (ассоциативный массив) позволяют легко устранить повторяющиеся значения и упростить поиск и поиск значений.

PERL вездесущ. PERL элегантен. PERL, на мой взгляд, органичен. Мне просто нравится PERL. Мой новый исходный код кроссворда находится по адресу: https://github.com/vpelss/crosswords Списки слов не включены. Замечательный человек находится в www.otsys.com/clue но он должен быть изменен. Чтобы работать с моим кодом. Мой код прокомментирован. Но я не приношу извинений. Если это не имеет для вас никакого смысла. Он постоянно видоизменяется и обновляется. Если я нахожусь в середине большого обновления. Код может не работать.

Никакой бесплатной поддержки не будет. Если у вас есть предложения, пожалуйста. Используйте ссылку Вы можете скачать код для моего старого генератора кроссвордов в британском стиле по адресу https://www.emogic.com/store/free_crossword_script. Никакой бесплатной поддержки не будет. Кое-чему я научился. 1. Чем больше база данных слов, тем лучше. 2. Поиск по одной букве не является ответом. Так как существует слишком много комбинаций. Для каждого слоя буквы вы проверяете не более двух слов с общей буквой. Таким образом. Даже при быстром вычислении времени для каждой буквы вся рекурсия складывается.

Полный поиск слов (Укладка слова и одновременная проверка того. Что все пересекающиеся слова будут иметь возможное слово). Хотя и намного медленнее. Имеет меньше рекурсивных вызовов. В большинстве моих тестовых сценариев закладка слов была быстрее. Еще один способ заявить о преимуществе укладки слов заключается в том. Что одна случайная замена слова быстрее ищет пространство головоломки. Например, при закладке первой буквы. Если эта буква никогда не приведет к правильной головоломке. Мы можем не знать. Пока не пройдут миллионы рекурсий. Мы быстрее обнаруживаем ошибки. Закладывая целые слова.

3. Каждый раз. Когда вы кладете слово. Вы должны убедиться. Что все его пересекающиеся позиции слов будут соответствовать слову. Если нет, вы подготовите слишком много рекурсий. Код более сложный. Но он того стоит. 4. Ваш алгоритм пути для укладки слов (порядок. В котором вы кладете слова) должен гарантировать. Что каждое следующее слово в вашем пути пересекает предыдущее. Это помогает уменьшить количество потраченных впустую рекурсий. Случай неэффективного пути рекурсии будет заключаться в попытке проложить все слова поперек. А затем проверить. Являются ли нижние слова допустимыми.

5. Оптимальные (оптимизированные). А не наивные (см. CCP) откаты очень помогают (в некоторых случаях скорость x100 увеличивается или даже больше). 6. Рекурсивно разработанные процедуры. Хотя и не являются обязательными. Кажутся более подходящими (логичными) для такого рода программ. Пространство головоломки огромно. Пространство решения головоломки ничтожно мало Поэтому простые рекурсивные и случайные попытки вряд ли будут работать своевременно сами по себе. Нам нужно сократить пространство поиска. Используя выбор прямых путей оптимальных обратных путей. Дизайн Шаблона Сетки Кроссворда (пустой)

Я выбрал простой текстовый дизайн. Шаблоны сетки представляют собой текстовые файлы. Содержащие строки. Состоящие из букв 'x' = черные квадраты 'o' = пустые квадраты X и o были выбраны так. Как они имеют одинаковый размер. И это дает легко визуальное представление фактической сетки в блокноте. В сценарии они сохраняются как таковые и не конфликтуют. Так как вставленные буквы всегда будут заглавными. Все эти альтернативные модели хранения должны быть обновлены одновременно. например: xooooo oooooxo oooooxo Поиски Есть много видов поиска. Которые мы можем выполнить. Чтобы попытаться определить. Какое слово или буква будет соответствовать нашему кроссворду.

Префиксный / Линейный поиск : Возвращает следующие потенциальные буквы после заданной серии букв Примечание: Это для буквенного поиска. Учитывая префиксные буквы для слова. Верните следующие возможные буквы. например: учитывая 'boa--'. Найденное в пространстве для 5-буквенного слова. Следующая буква может быть t или r. Это полезно только в том случае. Если вы планируете строить слова от начала до конца. Это не позволит заполнять случайные позиции букв. Способ 1. Для каждой длины слова я построил цепочку хэш-ссылок. Это требовало. Чтобы мы следовали цепочке хэш-ссылок.

Это было сложнее. Но быстро. $nextLetter[numberOfLettersInWord] указывал бы на список хэшей. Где ключи были возможными первыми буквами. Таким образом. *Метод 2. Тогда я решил. Что проще реализовать и почти так же быстро просто использовать маски с префиксами. Это избавило бы от необходимости указывать длину слова (так как маска имеет правильную длину). И никакого кода для навигации по цепочке хэшей не требовалось. Список писем я не вернул. Я возвращаю список ключей. В котором были буквы. Это упростило создание списка. Гарантируя отсутствие дубликатов букв

Примечание: маска должна быть только префиксной маской. ie: HIGoooooo Это в 1,5 раза медленнее. Чем старый способ. Хранение в памяти примерно то же самое. Поиск по маске : @words = &WordsFromMask($mask) $mask = ‘GOoD’ : Возвращает список потенциальных слов для данной маски Способ 1. Для данной маски (например. Хорошей) циклически перебирайте все заданные буквы. Для каждой заданной буквы верните список (построенный ранее) всех слов той же длины. Что и маска. В которых эта буква находится в этой позиции. Сделайте это для всех всех букв. Которые у нас есть в маске. Затем мы сравниваем все списки и сохраняем слова. Которые существуют во всех списках.

Это было сложно и не очень быстро. Так как нам приходилось многократно сравнивать потенциально большие списки слов. Его использование памяти было средним или высоким. Поскольку строка слова хранилась несколько раз. По крайней мере столько же раз. Сколько букв в слове. Например: СОБАКА хранилась 3 раза. По одному разу за каждую букву. *Метод 2. Слова длины строки. Для каждой длины слова мы создали предварительно скомпилированную большую строку. Разделенную запятыми. Состоящую из всех слов этой длины. Мы используем регулярные выражения для поиска маски в этой строке и возвращаем список слов.

Хранение памяти настолько эффективно, насколько можно было бы надеяться. например, СОБАКА хранится только один раз в словах, разделенных запятыми, 3-буквенной строки. Эта скорость удивительно быстра для поиска длинных строк. ПЕРЛ рокс! моя $tempMask = $mask; $tempMask =~ s/$unoccupied/\./g; #сделайте маску 'GO$UNOCCUPIED' в 'GO.T' для регулярного выражения (в моем коде $unoccupied is = o) my $wordLength = length($tempMask); @word_list = ($WordsOfLengthString[$wordLength] =~ /($tempMask),/g); Способ 3. Бинарная маска. Для каждого слова мы строим бинарную маску.

Затем для каждой маски мы создаем список слов. Принадлежащих этой маске. Теоретически это должно быть очень быстро. Но в некоторых случаях это лишь немного быстрее. Чем поиск слов по длине строки. Копирование или доступ к списку занимает большую часть времени и поэтому не намного быстрее в тех случаях. Когда возвращаемый список будет большим. Небольшие возвращаемые списки работают быстрее. Так как метод 2 все еще нуждается в поиске полной строки. Разделенной запятыми. Таким образом. Меньшие возвращаемые списки слов покажут улучшение скорости с помощью этого метода.

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

@words = &WordsFromLetterLists(['C','D','F','T','Z'] . ['E','R','T','Y','O'] . ['T','R','E','W','Q','Z']); Используется. Если мы проверяем все возможные буквы в одной и той же позиции слова пересечения слов. Тогда мы можем найти возможные перпендикулярные слова которые возможны для этого места Очевидно. Что это занимает много времени обработки. Сначала мы должны искать возможные буквы в нашем слове для всех пересекающихся слов. ----o--- ----o--- ----o--- Несмотря на то. Что это может занять до 250 раз больше времени. Чем простой поиск слов маски (позволяя простой рекурсивной рутине вычислять ошибки). И в 833 раза медленнее. Чем поиск букв. Он быстрее на многих типах сеток. Когда он смотрит на блоки букв. А не только на пересекающиеся слова. Поэтому он быстрее замечает ошибки и избегает множества неэффективных слепых рекурсий. Примечание: Это действительно сияет. Если ваш путь ходьбы/поиска гарантирует. Что каждое следующее слово пересекает предыдущее(ы). Оптимальный обратный путь для построения Слово в слово Добавив оптимальную проверку обратного хода и процедуру для этого поиска. Я улучшил время генерации в 2500 раз или более в Если попытка слова терпит неудачу. Я составляю список пересекающихся позиций слов и смежных позиций слов (выше. Ниже или слева/справа). Это слова. Которые влияют на позиции слов. Которые потерпели неудачу. Затем я возвращаюсь назад. Пока не попадаю в одну из позиций слова в этом списке. Вы должны остановиться на первом попавшемся или вы рискуете потерять возможные решения головоломки. Сетки, которые. По-видимому. Не приносят пользы. - это сетки с двойным словом со 100% блокировкой. Это имеет смысл. Поскольку все или большинство пересекающихся слов влияют на слово. Которое вы пытаетесь разгадать. напр.: Поиск писем - процедура Но большинство рекурсий Маска поиска слов: 0,0002 секунды на вызов. Много рекурсий. Мета-поиск слов : 0,05 секунды на вызов. Меньше рекурсий. Мета-поиск слов с оптимальным обратным отслеживанием: 0,09 секунды на вызов. Потенциально наименьшее количество рекурсий. Структуры данных %WordListBy_WordLength_Letter_LetterPosition Больше не используется: Я использую @WordsOfLengthString. Маски и регулярные выражения вместо списка используется хэш. Чтобы у нас не было повторяющихся слов %linearWordSearch Больше не используется: буква за буквой очень быстро для поиска следующих возможных букв в слове маска должна быть префиксной маской ie: TOOLooooo @WordsOfLengthString $WordsOfLengthString[$wordLength] = @WordsFromLetters = split (',' . $WordsOfLengthString[$wordLength]); $tempMask = $маска; $tempMask =~ s/$unoccupied/\./g; #make a mask of 'GO$unoccupedt' into 'GO.T' для регулярного выражения $wordLength = длина($tempMask); @word_list = ($WordsOfLengthString[$wordLength] =~ /($tempMask),/g); Наши логические структуры данных используют как структуры хранения слов. Так и структуры хранения букв. Оба используются одновременно. Поскольку оба могут быть полезны в разных ситуациях. @puzzle : letter centric the puzzle with the words inserted. array[][] возвращает хэш. Поскольку в будущем мы можем захотеть хранить больше данных. Чем просто букву ячейки. @allMasksOnBoard – word centric все слова на борту. Будь то полные или нет $allMasksOnBoard[word number][dir 0=across 1=down] многие будут undef 1 - это первое слово номер @LetterPositionsOfWord и @ThisSquareBelongsTowordNumber сопоставляют номера слов с позициями ячеек и наоборот. @LetterPositionsOfWord $LetterPositions[word #][dir] массив всех буквенных позиций слова [[x,y],[x,y]....] $LetterPositions[$numberCount][$Dir] = [@TempLetterPositions]; #анонимная ссылка на массив из пар $x,$y всех букв в слове Может использоваться для быстрого поиска всех пересекающихся слов с @ThisSquareBelongsTowordNumber и с помощью другого $dir @ThisSquareBelongsToWordNumber $ThisSquareBelongsToWordNumber[x][y][dir] возвращает номер слова. Которому принадлежит этот квадрат Он может быть использован. Чтобы найти номер слова пересечения $wordNumber = $ThisSquareBelongsToWordNumber[$x][$y][$dir] $crossingwordNumber = $ThisSquareBelongsToWordNumber[$x][$y][не $dir] @PositionInWord $PositionInWord[x][y][dir] возвращает pos буквы в слове. Которому принадлежит этот квадрат. Начиная с 0 $NthLetterPosition = $PositionInWord[$x][$y][$dir] @NextWordPositionsOnBoard все слова положение на борту используется для езды по размещениям слов и т. Д рекомендуйте push и pop при использовании рекурсивных подпрограмм @nextLetterPositionsOnBoard Не используется: поиск по буквам поиск по всем позициям букв на борту используется для циклического перемещения по местам размещения букв и т. Д рекомендуйте push и pop при использовании рекурсивных подпрограмм %wordsThatAreInserted %mostFrequentLetters @letterFrequency = (E,T,A,O,I,N,S,R,H,D,L,U,C,M,F,Y,W,G,P,B,V,K,X,Q,J,Z) Не используется: поиск по буквам список наиболее распространенных букв от первого до последнего Не используется: буква за буквой поиск глобальной цели. Используемой для оптимального отслеживания. %длины слов Используется для определения возможных длин слов в сетке. Поэтому мы загружаем только нужные нам слова. Это экономит время и память. $padChar = 'x' $незанятые = 'o' %подсказок Примеры размеров списков слов Длина слова XW Express Дополнительные подсказки 2 27 30 85 3 640 788 4461 4 2273 2743 11652 5 3468 5045 20235 6 4465 6546 24496 7 4905 7129 28296 8 4730 6636 27650 9 4130 5366 24553 10 2681 3572 24344 11 1677 2221 19815 12 823 1061 13266 13 412 614 12613 15 135 185 9597 16 0 1 2697 17 0 0 1940 18 0 0 1018 19 0 0 930 20 0 0 3041 всего 30405 42034 251578 линии 30418 53899 4325826 Пройдитесь по дорожкам Слово за Словом Плоские: Горизонтальные слова. Он кажется самым быстрым в полностью связанном квадрате. Диагональ: Медленно. Switchback: Чередование горизонтальных и вертикальных частей слова и слова вдоль диагональной оси. Почти так же быстро, как флэт. Но никаких преимуществ. Моя перекрестная прогулка: я сгенерировал свою собственную прогулку. Которая бьет по основным при использовании рекурсивных алгоритмов поиска слов. Которые закладывают слово на основе всех возможных перекрестных слов для позиции этого слова. Я начинаю с самого первого слова в правом верхнем углу (хотя можно использовать любую стартовую позицию). Затем я добавляю все пересекающиеся слова к этому исходному слову. Затем я нахожу и добавляю к этим словам все пересекающиеся слова и т. Д. Я добавляю слово только один раз. Это имеет тенденцию очень эффективно отступать даже при наивном отступлении. Прогулки по букве за Буквой Эти прогулки должны гарантировать. Что мы всегда строим как горизонтальные. Так и вертикальные слова от первой буквы до последней буквы. Оптимальный Backtrack : для буквенных построений Это сложно. Так как оптимальный обратный путь зависит от выбранного нами пути и сеточных структур и площадок вокруг неудачной буквы. После долгих размышлений я упростил многие правила для выбора оптимизированной цели backtrack до двух простых правил. Которые работают со всеми прогулками и всеми сетками. Так как мы могли бы использовать любую прогулку (что позволяет нам закладывать слова от первой буквы до последней буквы): Правило: 1. Все буквы в горизонтальных и вертикальных словах (вплоть до неудачной буквы) могут повлиять на неудачу укладки буквы. Поэтому отметьте ее как оптимальную цель обратного хода 2. Все пересекающиеся слова как горизонтальных. Так и вертикальных слов неудачной буквы могут привести к неудаче укладки буквы. Поэтому отметьте ее как оптимальную цель обратного хода 3. Удалите Обратите внимание. Что # 2 может показаться не интуитивным. Но уверяю вас, они могут. Если мы отступили от центральной буквы (см. Если мы это делаем. То пропускаем такие слова. Как АВТОМОБИЛЬ. Которые могли бы позволить другое решение во втором ряду. Которое было бы пропущено. Правило 3 также нарушает определенные отступы сетки. Особенно кроссворды в британском стиле. Причина в том, что. Поскольку мы находимся на двойном расстоянии. Существует много теней (правило 3). Которые не должны быть тенями. Поэтому я считаю, что если мы оставим правило 3, то дополнительные оптимальные обратные пути, которые мы можем пропустить, стоят того. Чтобы сохранить наши оптимальные целевые правила простыми. В настоящее время есть несколько случаев. Когда комбинация ходьбы и сетки будет нарушена. Сценарии, в которых наивный обратный путь никогда не попадает в цель обратного пути, вызывают эти сбои. например: буква зигзаг и 13x13_56_144 КОТ ооо ооо Таким образом, в квадратном кроссворде нет оптимального обратного хода без черных квадратов в соответствии с правилом 1 и 2, поскольку все квадраты являются оптимальными обратными квадратами. Словарь и подсказки Для огромных списков слов (необходимых для больших сеток) объединенный список словаря и базы данных подсказок огромен. Единая база данных всех слов и подсказок очень велика и требует слишком много времени для загрузки и логической организации данных. Если мы хотим. Чтобы наш алгоритм кроссворда имел быстрый доступ. Он должен быть загружен в оперативную память. Но существует очень мало систем с таким объемом оперативной памяти. Я остановился на создании текстовых файлов на основе длины слов. 3.txt содержит все 3 буквенных слова в словаре. 7.txt содержит все 7 буквенных слов. После загрузки сетки кроссвордов в массив PERL $wordsOfLengthString[$wordLength] загружаются только необходимые текстовые файлы. Все слова в этом массиве разделены запятыми. Поскольку поиск регулярных выражений PERL происходит удивительно быстро. Мы можем быстро искать шаблоны слов. Чтобы получить нужные слова. Как только все слова будут помещены в головоломку. И нам понадобятся подсказки для этих слов. Быстрый способ загрузки подсказок состоял бы в том. Чтобы иметь word.txt файл для каждого слова. Содержащий все возможные подсказки. jude.txt будет содержать: Имя в песне Битлз Закон Книга Нового Завета Святой Фаддей ..... Это быстро заполнит все доступное дисковое пространство, поскольку более 250 000 небольших текстовых файлов занимают гораздо больше места на диске, чем данные. Которые они содержат. Чтобы сэкономить место на диске. Я создаю текстовые файлы подсказок на основе первых двух букв слов независимо от размера слова. Это занимает 250 000 файлов и преобразует их в 650 файлов. Загрузка подсказок занимает немного больше времени. Но это не заметно. _ae.txt содержит: AEA|Организация теспианцев. AEA|Организация теспианцев. AEA|Теспианс гп. ЭАК|Дед Ахилла ЭЭЭЭ|Остров Цирцеи ... Контрольные показатели Основываясь на разделе о двойных квадратах слов по адресу: http://en.wikipedia.org/wiki/Word_square Я чувствую. Что моя программа работает хорошо. В статье говорится. Что 8 x 8-это самый большой квадрат Двойного слова порядка. Который можно найти с помощью словарных слов. Учитывая мой ограниченный словарь. Моя программа может создавать и генерировать кроссворд размером 6 х 6 примерно за 3 секунды. Идеи/Вопросы Как мы можем создать эффективный генератор ходьбы и оптимальный обратный путь для любой сетки головоломок? Можем ли мы поместить задачи backtrack и walk в их собственные подпрограммы и при этом использовать рекурсию? Предполагая, что мы можем найти подходящие структуры данных, может быть. Накладные расходы замедлят его? Возможны ли динамические прогулки (где следующее место прогулки выбирается на основе текущей заливки головоломки/сетки) без пропуска допустимых комбинаций головоломок? Можем ли мы еще больше увеличить время генерации. Выбрав сначала более подходящие или вероятные слова? Мне нужно написать лучшую процедуру выбора подсказок. Чтобы учесть различные стили.