Як згенерувати сканворд із зашифрованим словом

Сканворд (шведський кросворд) із зашифрованим словом можна згенерувати у дві фази: спершу локальним пошуком знайдіть маску, тобто розташування клітинок із питаннями і клітинок для літер, а потім заповніть її словами зі словника як задачу з обмеженнями (CSP) за допомогою backtracking. Не ставте зашифроване слово в сітку заздалегідь. Лише коли кросворд готовий, шукайте жарт, чию пуанту можна прочитати в ньому зліва направо і згори донизу.

Так створюються сканворди в нашому застосунку з кросвордами та пошуком слів (App Store, Google Play). Одна сітка коштує від кількох до кількох десятків секунд процесорного часу, тому ми генеруємо їх заздалегідь на потужнішому комп'ютері і додаємо до застосунку. Пошук слів генерується зовсім інакше і простіше, про це стаття Як згенерувати пошук слів із зашифрованим словом.

#Яким вимогам має відповідати сканворд

У сканворді немає чорних клітинок. Кожна клітинка є або літерою, або питанням зі стрілкою праворуч чи вниз. Звідси жорсткі умови:

• Кожна літера належить і горизонтальному, і вертикальному слову. Літеру, яку перетинає лише одне слово, неможливо перевірити, і в кросворді вона виглядає як помилка.
• Кожне слово має щонайменше дві літери, а перед ним стоїть питання. Тому перший рядок і перший стовпець завжди складаються лише з питань.
• Літери утворюють одну суцільну область без відірваних острівців.
• Кожне слово має бути у словнику і мати щонайменше одне визначення. Жодне слово в сітці не повторюється.

До цього додаються м'які критерії якості: мало двобуквених слів, жодних питань, що нікуди не вказують, і якомога менше дуже довгих слів, які важко заповнити. Задача обчислювально складна. Engel та ін. (2012) показали, що вже саме заповнення маски словами є NP-повною задачею.

#Чому не вистачить заповнювати сітку слово за словом

Перша ідея: діяти як людина з олівцем. Поділити зашифроване слово на слова, покласти їх у рядок, як у газеті, провести через кожну його літеру слово, що перетинає, а решту сітки заповнити за допомогою greedy algorithm. Greedy algorithm на кожному кроці бере варіант, який виглядає найкращим саме зараз, і ніколи не переглядає рішення. Де нічого не підходить, лишається дірка. А оскільки greedy-заповнення не вміє повертатися, погані перші десять слів решта сітки вже не виправить.

Краща евристика вибору слів допомагає лише трохи. Можна пробувати довжини слів, що перетинають, від середніх, близько п'яти літер, до крайніх. Або піти еволюційним шляхом: популяція недороблених кросвордів, від кожного п'ять нащадків з одним словом більше, оцінка за кількістю заповнених клітинок, кількістю голосних і рівномірністю літер, і до наступного покоління переходять лише найкращі. Результати стають трохи щільнішими, але дірки лишаються, бо евристика бачить лише найближчий крок.

Вихід дає бакалаврська робота Якоба Енгеля з Технічного університету Мюнхена (2009); він також перший автор згаданої статті. Розділіть задачу на дві незалежні фази: спершу знайдіть добру маску, не зважаючи на слова, потім заповніть її. Енгель для маски використав еволюційний алгоритм. Ми використовуємо простіший локальний пошук із випадковими струсами, описаний у наступному кроці.

#Крок 1: маска через hill climbing

Маскою називаємо сітку, в якій кожна клітинка або питання, або літера. Щоб її знайти, достатньо hill climbing: локального пошуку, який робить малі зміни і зберігає ті, що не погіршують результат.

Почніть випадково, з питаннями приблизно на 22 % внутрішніх клітинок. Кожній масці призначте штрафну оцінку. Жорсткі порушення (закоротке слово, літера без слова, що перетинає, відірваний острівець) нехай здебільшого коштують 1 000 балів, м'які недоліки (двобуквені слова понад ліміт, питання, що не вказує на жодне слово, скупчення питань) від 50 до 500.

Далі в циклі змінюйте одну клітинку з питання на літеру або навпаки, або зсувайте питання на клітинку по діагоналі. Залиште зміну, якщо штраф не зріс, інакше скасуйте її. Спрямуйте половину змін на клітинки з найбільшим штрафом, і грубі помилки зникнуть швидко:

Hill climbing легко застрягає в локальному мінімумі. Коли 2 000 кроків нічого не покращують, «струсніть» сітку: у найкращій досі знайденій масці перемкніть п'ять випадкових клітинок і шукайте далі. На графіку це піки. Якщо й після трьох струсів кращої маски немає, а поточна не має жорстких порушень, зупиніться.

Готова маска має залишковий штраф 200 за м'які недоліки, але жодного жорсткого порушення:

Штрафи за питання без слова і за відірваний острівець варто мати в масці від самого початку. На великому наборі готових кросвордів без них 13,2 % питань не вказували на жодне слово, а 23,5 % сіток мали відірваний острівець літер. З ними це 5,0 % і 0 %.

#Крок 2: заповнення словами як CSP

З маски виходить список слотів, тобто місць для слів із відомою довжиною і перетинами. Заповнення є класичною задачею задоволення обмежень (constraint satisfaction problem, CSP): кожен слот є змінною, його домен складають слова, які в нього вміщуються, а обмеження є однаковими літерами на перетинах. Розв'язується вона за допомогою backtracking, тобто пошуку, який у глухій гілці повертається на крок назад і пробує інший варіант:

для кожного слота: домен = усі слова цієї довжини
поки не всі слоти заповнені:
    вибери слот із найменшим доменом (за рівності той, що має найбільше перетинів)
    для кожного слова з домену, від найкращого:
        постав слово
        звузь домени слотів, що перетинають, до слів із тією самою літерою
        якщо якийсь домен спорожнів: скасуй, спробуй наступне слово
        інакше переходь до наступного слота
    якщо жодне слово не підходить: повернися на слот назад
після 50 000 кроків здайся

У літературі ці евристики називаються MRV (minimum remaining values, спершу слот із найменшою кількістю варіантів) і forward checking (після кожного кроку звужувати домени сусідів, щоб глуха гілка виявлялася одразу, а не на десять слів пізніше). Заздалегідь проіндексуйте словник за довжиною, позицією і літерою. Тоді «слова з Щ на третьому місці» є одним перетином множин, а не проходом усім словником.

Важливий і порядок слів. Надавайте перевагу словам, які мають у словнику більше різних визначень. Це простий сигнал поширеного кросвордного слова. Без нього сітка заповнюється маловідомими абревіатурами.

#Крок 3: зашифроване слово в готовій сітці

Під час заповнення ви ще не знаєте, яким буде зашифроване слово. Прочитайте літери готової сітки зліва направо і згори донизу і шукайте жарт, чия пуанта є підпослідовністю цього рядка. Тобто літери йдуть у правильному порядку, але не обов'язково поруч. Якщо такий жарт знайдено, розподіліть його літери по сітці якомога рівномірніше, щоб пуанту не можна було вгадати з одного слова.

Такий порядок (спершу сітка, потім жарт) суттєво збільшує кількість готових кросвордів. За нашими вимірюваннями одна сітка 12×12 у середньому підходить для 86 жартів зі словацького списку (5 960 жартів). Тож завжди знайдеться такий, що ще не використовувався в цьому розмірі.

#Чому не ставити зашифроване слово заздалегідь, як у газеті

У газетах зашифроване слово зазвичай стоїть в одному місці, в рядку і розділене на слова. Досягти цього можна двома способами, і обидва дають дуже мало результатів.

Перший спосіб: поставити зашифроване слово в сітку заздалегідь. Тоді воно має вміститися. Наші пуанти мають у середньому 10,3 літери і 2 слова. Ось частка жартів зі словацького списку, які взагалі можна покласти в сітку даного розміру:

Із заздалегідь поставленим зашифрованим словом заповнення малих сіток вдається приблизно так само часто, як без нього. Для 15×15 це було 5 із 60 спроб проти 8 без нього, для 18×18 жодної з 60. До того ж кожна така сітка слугує лише одному жарту, а в малих розмірах більшість жартів навіть не вдається покласти.

Другий спосіб: дати сітці утворитися вільно і шукати в ній пуанту як суцільний відрізок. На вибірці з 2 200 готових словацьких кросвордів (по 200 кожного розміру від 8×8 до 18×18) уся пуанта як суцільний відрізок в одному рядку чи стовпці знайшлася лише в 81 сітці (3,7 %). Якщо кожне слово пуанти може лежати деінде, таких сіток 443 (20 %), і це ще без умови, що слова стоять поруч. Якщо читати літери по порядку, жарт знайшовся в кожній із них. Ціною зашифрованого слова, розкиданого по сітці, ви отримуєте на порядки більше кросвордів.

#Продуктивність генератора і чому він не працює на телефоні

Генератор виконав по 60 спроб для кожного розміру зі словацьким словником, в одному потоці (JavaScript на Node 22, серверний процесор Intel Xeon 2,8 ГГц у хмарі). Спроба складається з однієї маски й одного заповнення. «Успішне заповнення» означає, що CSP знайшов розв'язок за 50 000 кроків.

Що показують вимірювання:

• Мала сітка не є легкою. У сітці 8×8 багато коротких слотів із великою кількістю перетинів і мало свободи, заповнення вдається лише в 5 % спроб. Одна заповнена сітка в середньому коштує близько 10 секунд процесорного часу для 8×8, 4 секунди для 12×12 і 18 секунд для 18×18.
• Більшість спроб закінчується невдачею. Тому запускайте спроби паралельно на всіх ядрах і беріть перший достатньо добрий результат.
• На телефоні це не має сенсу. Гравець не хоче чекати десятки секунд, відкриваючи екран, а застосунок мусив би містити весь словник із визначеннями. До того ж генератор у застосунку мусить постійно віддавати керування інтерфейсу, інакше застосунок зависає.

#Генерація у великих обсягах

Тому генератор має працювати на комп'ютері з багатоядерним процесором. У нас кожне ядро має власний потік зі словником, завантаженим один раз під час запуску. Сітка готова, щойно один із потоків поверне результат із достатньо малою кількістю невикористаних клітинок. У безперервному режимі генератор по колу створює один кросворд кожного розміру кожною мовою. Так з'явилося понад 14 000 кросвордів чотирма мовами (словацька, чеська, англійська, німецька) в одинадцяти розмірах від 8×8 до 18×18. Кожен жарт використовується не більше одного разу на розмір і мову.

За такого обсягу важать дві речі:

• Формат. Повний запис займає близько 28 кБ на кросворд і 390 МБ на весь корпус. Більшу частину можна обчислити (координати, типи клітинок, номери питань). Компактний формат, у якому сітка зберігається одним рядком, займає близько 2 кБ, 15 МБ на корпус і приблизно 7 МБ в інсталяційному пакеті застосунку.
• Вимірювання якості. Після кожної генерації вимірюйте частку питань без слова і сіток з острівцями, і нехай перевірка не проходить, якщо показники погіршуються.

#Чого цей підхід не охоплює

• Питання без слів. Середній кросворд досі має 2,7 питання, що нікуди не вказують. Лівий верхній кут завжди такий.
• Словники без частотності. Німецький словник із Вікісловника має для більшості слів одне визначення, тож сортування за кількістю визначень майже нічого не розрізняє, і в сітку потрапляють рідкісні слова. Допоміг би частотний словник, поки що його немає.
• Зашифроване слово не стоїть в одному місці. Хто звик до газет, може шукати його в рядку. Це компроміс, а не ідеал.

Якщо ви розв'язуєте схожу задачу з генерацією контенту або вам потрібен мобільний застосунок, напишіть нам.