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

Ця історія починається з цієї статті на Хабре. У ній наведено один з найскладніших кросвордів, складених програмою (див. нижче).



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


Для заповнення кросворду завжди використовується перебір. Ми ставимо перше слово, потім всі наступні, перевіряючи, щоб букви на перетинах збігалися з буквами в словах, поставлених раніше. І так, поки всі слова не будуть поставлені. Здавалося б, немає нічого простіше. Однак простий підрахунок кількості ітерацій підбору слів для кросворду середньої довжини на 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 одиниць. Все що вище — на удачу.
Нижче показано середнє час успішної генерації для декількох сіток, розташованих у порядку зростання складності генерації.

Сітка № 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…

Сподіваюся, Вам було цікаво, і Ви дочитали до кінця. це сайті Ви можете завантажити програму і спробувати самостійно згенерувати кросворди. На цьому все, всім добра…

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.