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

Щоб згенерувати пошук слів із зашифрованим словом, кладіть у порожню сітку випадкові слова зі словника, доки не залишиться рівно стільки вільних клітинок, скільки літер у зашифрованому слові. Потім заповніть ці клітинки зашифрованим словом зліва направо і згори вниз. На телефоні це займає кілька мілісекунд і не потребує backtracking, тобто повернення до попередніх рішень, коли генератор застрягає.

Пошук слів (у Словаччині цю головоломку називають osemsmerovka, «восьминапрямка») це сітка літер, у якій гравець шукає і викреслює слова зі списку. Зашифроване слово складається з літер, що залишаються невикресленими. Тож генератор мусить побудувати повністю заповнену сітку, у якій після викреслення слів залишиться рівно зашифроване слово. Описаним нижче способом генерується пошук слів у нашому застосунку з кросвордами та пошуком слів (App Store, Google Play).

#Правила сітки

Перш ніж почати, визначте, яким умовам має відповідати готова сітка. У нашому застосунку:

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

#Крок 1: Підготуйте словник

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

Наш словацький словник містить 16 713 слів довжиною від 3 до 21 літери, найбільше семи- і восьмилітерних. Кілька практичних порад:

• Залиште у словнику власні назви та абревіатури. Тоді в сітці з'являться слова на кшталт HOUSTON чи MAINE. Без коротких і «дивних» слів сітку не вдасться заповнити достатньо щільно.
• Фільтруйте лайку окремим списком, який можна вимкнути, якщо гравець хоче вміст для дорослих.
• Якщо мов кілька, завантажуйте лише ту, якою зараз грають. Англійський словник має понад 414 000 слів. Якщо під час запуску застосунку завантажити всі чотири мови одразу, слабший телефон зависне аж на 11 секунд.

#Крок 2: Виберіть зашифроване слово

Зашифроване слово має містити щонайменше стільки літер, скільки клітинок у стороні сітки, і щонайбільше на чотири більше. Коротше загубиться в сітці, довше потребуватиме забагато дірок.

У нашому застосунку зашифроване слово це кінцівка жарту. Гравець викреслює слова і з решти літер читає, чим закінчується жарт. Ми складаємо його з кінця жарту: додаємо цілі слова з кінця, доки довжина не потрапить у цей діапазон.

На зображеннях нижче англійський жарт «Two snakes walk into a bar. Turns out they were lizards.» (Дві змії заходять у бар. Виявляється, це були ящірки.) на сітці 10×10. Зашифроване слово WERELIZARDS, 11 літер. Слова на зображеннях узято з англійського словника, звуженого до поширених слів, щоб їх можна було прочитати.

#Чому не варто починати із зашифрованого слова

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

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

На вибірці з 200 сіток 10×10 цей підхід давав повну сітку лише у 28 % випадків, у середньому залишалося 1-2 дірки. Латати їх потім складно. Тому не ставте зашифроване слово в сітку, доки не готові слова.

#Крок 3: Заповнюйте сітку, доки не залишиться рівно N дірок

Заповнення це простий greedy algorithm: кожне слово кладеться, щойно вміщається, і більше не прибирається. Генератор пам'ятає лише одне число: скільки клітинок ще порожні. Слово кладеться тільки тоді, коли після нього не залишиться менше порожніх клітинок, ніж літер у зашифрованому слові (N).

порожні = рядки × стовпці
поки порожні > N і спроб < 2000:
    слово = випадкове слово вибраної довжини
    повторити щонайбільше 50 разів:
        початок = випадкова клітинка, напрямок = випадковий з 8
        якщо слово вміщається за правилами сітки:
            нові = кількість порожніх клітинок, які слово заповнить
            якщо порожні - нові >= N:
                покласти слово
                порожні = порожні - нові
                перейти до наступного слова
якщо порожні != N: викинути сітку й почати знову

Перші слова лягають у порожню сітку вільно:

Що щільніша сітка, то частіше слова ділять літери. Це добре, бо кожна спільна літера означає на одну клітинку менше для заповнення:

Коли кількість порожніх клітинок падає до N, заповнення закінчується. Де саме ці дірки, неважливо. Вони можуть бути розкидані будь-де, бо зашифроване слово не мусить утворювати через них жодного шляху:

#Крок 4: Вибирайте довжину слова з розумом

Довгі слова роблять головоломку цікавою, короткі допомагають її завершити. Тому вибирайте довжину з двох нормальних розподілів (нормально розподілені випадкові числа дає, наприклад, перетворення Бокса-Мюллера):

Довжина завжди щонайменше 3 і щонайбільше сторона сітки. Додайте два правила, без яких генератор наприкінці застрягає:

• Наприкінці задавайте точну довжину. Коли до цілі бракує 5 клітинок або менше, шукайте слово рівно такої довжини, якої бракує (щонайменше 3). Інакше генератор безкінечно пробуватиме шестилітерні слова, які вже не вміщаються.
• Видавайте трилітерні слова за нормою. Перші три спроби сітки не можуть містити жодного, спроби 4-6 одне, наступні три два і так далі. Трилітерні слова у словнику часто є абревіатурами на кшталт DNA чи CPU і в головоломці виглядають дешево. Дозволяйте їх, лише коли інакше не виходить.

#Крок 5: Залийте зашифроване слово в дірки

Пройдіть сітку зліва направо і згори вниз і в кожну порожню клітинку запишіть наступну літеру зашифрованого слова. Оскільки дірок рівно N, слово вміщається без залишку.

Гравець бачить лише це:

#Коли сітка не вдалася

Якщо генератор за 2 000 спроб не досягає рівно N порожніх клітинок, викиньте всю сітку і почніть заново, щонайбільше 100 разів. Жодного латання дірок. Це грубо, але для сіток до 12×12 цього вистачає із запасом. Більші сітки потребують більше спроб, як показує таблиця нижче.

#Успішність і швидкість залежно від розміру сітки

Генератор працював на 300 сітках для кожного розміру, зі справжніми жартами і словацьким словником (Node.js 22 на серверному процесорі, телефон буде повільнішим; зображення зроблено з англійським словником, цифри зі словацьким, бо він менший, а отже це суворіший тест). «З першої спроби» означає, що перше коло заповнення завершилося повною сіткою.

Що це означає для власного генератора:

• Середнє слово має 4,7 літери, хоча ціль близько 6. Довгі слова просто частіше не вміщаються в щільну сітку.
• Приблизно 9-10 % клітинок спільні для двох слів. Налаштовувати це не потрібно, це наслідок правила «щонайбільше одна спільна літера».
• Діагоналей буде менше, ніж ви очікуєте. Напрямок вибирається рівномірно з восьми, тож діагоналі мали б становити половину слів. Але в малій сітці діагональне слово значно частіше виходить за край. На 8×8 діагоналі становлять 24 % слів, на 15×15 уже 33 %. Якщо хочете більше діагоналей, дайте їм більшу вагу під час вибору напрямку.

#Порада: та сама сітка при кожному запуску

Для скриншотів у магазинах вам потрібна щоразу та сама сітка. У такому режимі замініть звичайний генератор випадкових чисел простим лінійним конгруентним генератором із фіксованим seed (наприклад, похідним від мови). Якщо вся арифметика залишається в діапазоні, який числа в JavaScript представляють точно, результат однаковий на будь-якому пристрої. Тим самим трюком згенеровано й зображення в цій статті.

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