Генерация кроссвордов с помощью SAT солвера
На Хабре было несколько статей про генерацию кроссвордов. В одной из них «Самый сложный кроссворд, составленный компьютером» говорилось про очень сложный кроссворд, составленный компьютером, которому «пришлось немного помочь» вручную. Во второй статье «Алгоритм формирования кроссвордов» рассказывается про алгоритм, созданный автором для составления кроссвордов, и отмечается, что этот «самый сложный кроссворд» остался непокоренным и говорится, что «может быть эта непокоренная вершина вдохновит кого-нибудь на новый штурм!». Что же, можно принять вызов. Что из этого получилось, смотрите под катом.
В начале приведу этот самый сложный кроссворд:
Первое, что необходимо найти — это список слов, которые используются при составлении данного кроссворда. В качестве такого списка были взяты два файла из вышеупомянутых статей — один файл с русскими словами, один файл с английскими. Затем необходимо было решить главный вопрос — какой алгоритм использовать для составления этого кроссворда. Собственно «сложным» этот кроссворд делает не количество слов, а количество их пересечений. Понятно, что перебор «в лоб» (brute-force attack) здесь не подходит, поскольку перебор всех вариантов занял бы слишком много времени. В вышеупомянутой статье было рассмотрено много эвристик для ускорения процесса перебора, однако, данный кроссворд так и не был составлен ни в русском ни в английском варианте. Можно продолжать придумывать другие эвристики для ускорения решения, однако большинство из них уже придумано и реализовано в SAT солверах. Поэтому, можно перевести задачу в форму, понятную SAT солверам и воспользоваться одним из них.
Что такое SAT солвер и какую информацию он ожидает на входе я рассматривал в статье «Решение задачи замощения с помощью SAT солвера на примере пентамино». В случае генерации кроссворда необходим немного другой подход для формулировки задачи в конъюнктивно-нормальной форме, который я сейчас изложу.
Первое, что необходимо сделать — это рассортировать все слова из списка по группам. В каждой группе будут находиться слова одинаковой длины. Очевидно, что для каждого слова в сетке кроссворда можно выбрать какое-либо слово из группы с соответствующей длиной. Сопоставим каждому слову из группы которое может быть записано в одном слове из сетки булеву переменную. Эта переменная будет равна true, если данное слово из группы будет записано в этом слове из сетки и false в противном случае.
Теперь составим формулу, описывающую нашу задачу, то есть фактически наложим ограничения на наши переменные. Найдем все пересечения слов по вертикали со словами по горизонтали. Для каждого пересечения определим, какие пары слов сочетаются друг с другом, а какие нет. Однако, здесь возникает проблема, поскольку количество таких пар может превышать миллион для одного пересечения. Поэтому, воспользуемся другим подходом. Отсортируем слова в группе, которая соответствует слову по горизонтали по букве, которая стоит на позиции пересечения этих двух слов. Сделаем то же самое и для слова по вертикали. Очевидно, что подходящие слова будут иметь одинаковую букву на пересечении. Введем дополнительную переменную для каждой буквы, которая встречается хотя бы в одном слове по горизонтали и по вертикали. Теперь условием того, что два слова сочетаются друг с другом будет то, что хотя бы одна такая переменная будет true. Таким образом, для каждого пересечения будет добавлен один клоз состоящий из переменных, соответствующим буквам. Теперь необходимо связать переменные, соответствующие конкретной буквой со словами, содержащими эту букву в позиции пересечения слов. Это делается набором клозов, которые гарантируют, что две булевы переменые будут иметь одинаковые значения. И, наконец, необходимо гарантировать, что в кроссворде не будет одинаковых слов. Для этого для каждого слова из базы данных добавляем клозы вида (not x_i V not x_j), где x_i — переменная, соответствующая его экземпляру в одном слове из сетки кроссворда, а x_j — переменная, соответствующая его экземпляру в другом слове из сетки кроссворда.
Генерация этого «самого сложного кроссворда» с использованием русских слов занимает несколько минут на Intel 2600K 3.5 Ггц с 16 гигабайтами памяти. Создание кроссворда с использованием английских слов заняло порядка двадцати минут.
После этого я пробовал и другие сетки кроссвордов. Например, мне удалось составить кроссворд из английских и русских слов в виде квадрата 6 на 6, где все слова пересекаются.
Далее я привожу получившиеся кроссворды. Желающие могут их решить.
1 Horizontal Замедленое движение самолета с задираным носом
6 Horizontal Японский струнный щипковый музыкальный инструмент
10 Horizontal В скандинавской мифологии великан, возникший из довременного хаоса мировой бездны
14 Horizontal Изгнанник из рода
15 Horizontal Минерал
16 Horizontal Чешский поэт (20 в.)
17 Horizontal Остров в Гвинейском заливе (территория Экваториальной Гвинеи)
18 Horizontal Рот, губы (устар.)
19 Horizontal Негодование, ярость
20 Horizontal Наличие только одной политической партии
23 Horizontal Самая большая река Ирландии
24 Horizontal Одежда священнослужителя
25 Horizontal Река в Анголе и Заире, левый приток реки Кванго
27 Horizontal Марка венгерского автобуса
32 Horizontal Город и порт в КНДР
35 Horizontal Теща или свекровь
37 Horizontal Растение семейства паслёновых
38 Horizontal Тот, кто занимается чесанием шерсти
41 Horizontal Женское имя (греч. хорошая, добрая)
42 Horizontal Канадский искусственный спутник
43 Horizontal Персонаж оперы Вебера ''Вольный стрелок''
44 Horizontal Город в Cловакии
46 Horizontal Расходование средств
48 Horizontal Разводимая рыба семейства карповых
50 Horizontal В японской мифологии божество изобилия рисовых колосьев
54 Horizontal Неорганический кристаллический люминофор
59 Horizontal Иранский пророк, основатель манихейства (3 в.)
60 Horizontal Крестьянское жилище на островах Вест-Индии
61 Horizontal Пастушечья порода собак (похожа на лису)
62 Horizontal (перен.) тупой упрямец, глупец
63 Horizontal Город в Оренбургской обл. на реке Урал
64 Horizontal В греческой мифологии великан-охотник, убитый Артемидой
65 Horizontal Чилийский певец и поэт
66 Horizontal Персонаж индийского народного театра, образ разорившегося прожигателя жизни, нахлебника при богатом покровителе
67 Horizontal У чеченцев и ингушей мать-земля
1 Vertical Прозвище одного из вождей народного восстания 1413 г. в Париже
2 Vertical Неудовлетворенное чувство
3 Vertical Немецкий палеонтолог (1800–1862)
4 Vertical Отвоевание коренным населением Пиренейского п-ова территорий, захваченных маврами
5 Vertical Российский гитарный мастер
6 Vertical Шведский и российский военачальник, генерал, сподвижник Петра I (1667–1717)
7 Vertical Музыкант, играющий на каком-либо музыкальном инструменте
8 Vertical Оратор, красноречивый человек
9 Vertical Хребет в Японии, на острове Хонсю
10 Vertical Корейский ударный музыкальный инструмент, восьмигранный барабан
11 Vertical Латышский дирижёр (1917–1967)
12 Vertical Радушие, ласка
13 Vertical В славянской мифологии дух, воплощение смерти
21 Vertical Жанр анимации, возникший в Японии
22 Vertical Нить разогрева котода лампы
26 Vertical Озеро в Архангельской области
28 Vertical Река в Испании
29 Vertical Небольшой лесной массив лиственных деревьев
30 Vertical Редчайший предмет
31 Vertical Бельгийский мастер духовых инструментов, изобретатель саксофона
32 Vertical Небольшая кадка
33 Vertical Представитель черной расы
34 Vertical Старая мера аптекарского веса = 62,21 мг
36 Vertical Провинция в Саудовской Аравии
39 Vertical Антифрикционная смазка
40 Vertical Скульптурное украшение капители, карниза и т. п. в виде стилизованных стеблей и листьев такого растения
45 Vertical Русский писатель, поэт, кинодраматург, автор сценариев к фильмам А. Сокурова (''Молох'', ''Телец'')
47 Vertical Полисульфидный каучук, разновидность синтетического каучука
49 Vertical Английский патолог (Нобелевская премия 1945)
51 Vertical В мусульманской мифологии джинн, обладающий особой силой
52 Vertical Гусиный крик
53 Vertical Женское имя (греч. имя богини мирной жизни; мир)
54 Vertical Шахматный гроссмейстер
55 Vertical Исторически сложившаяся группа человечества, объединённая общностью происхождения
56 Vertical Гибрид от скрещивания одногорбого верблюда (дромедара) с двугорбым (бактрианом), нар
57 Vertical Механическая величина, вызывающая ускорение
58 Vertical Японский писатель (1909–1989, ''Записки пленного'', ''Огни в поле'', ''Сражение на Лейте'')
1 Horizontal A place that attracts many visitors
6 Horizontal Any of a number of fishes of the family Carangidae
10 Horizontal A collection of facts from which conclusions may be drawn
14 Horizontal Nintu)
15 Horizontal Body covering of a living animal
16 Horizontal A dull persistent (usually moderately intense) pain
17 Horizontal A response of body tissues to injury or irritation
18 Horizontal Type genus of the Anatidae freshwater ducks
19 Horizontal The dynasty that ruled much of Manchuria and northeastern China from 947 to 1125
20 Horizontal A white crystalline compound used as an analgesic and also as an antipyretic
23 Horizontal A city in central Tanzania
24 Horizontal God of death
25 Horizontal Shaped and dried dough made from flour and water and sometimes egg
27 Horizontal A member of the Siouan people of Virginia and North Carolina
32 Horizontal A strong restless desire
35 Horizontal South African prelate and leader of the antiapartheid struggle (born in 1931)
37 Horizontal A commercial document used to request someone to supply something in return for payment
38 Horizontal Biting midges
41 Horizontal An ancient city in northern Portugal
42 Horizontal An Eskimo hut
43 Horizontal Rotating mechanism in the form of a universally mounted spinning wheel that offers resistance to turns in any direction
44 Horizontal The capital of Bahrain
46 Horizontal The act of giving a light tint to the hair
48 Horizontal Type genus of the Majidae
50 Horizontal Any of several plants of the genus Camassia
54 Horizontal Flying gurnards
59 Horizontal Entire crop can be harvested at one time
60 Horizontal A law passed by US Congress to prevent employees from being injured or contracting diseases in the course of their employment
61 Horizontal A heavy block of iron or steel on which hot metals are shaped by hammering
62 Horizontal English statesman who opposed Henry VIII’s divorce from Catherine of Aragon and was imprisoned and beheaded
63 Horizontal A man who courts a woman
64 Horizontal United States baseball player
65 Horizontal A secret look
66 Horizontal Small slender gull having narrow wings and a forked tail
67 Horizontal Known for grapes and olives and olive oil
1 Vertical French revolutionary leader (born in Switzerland) who was a leader in overthrowing the Girondists and was stabbed to death in his bath by Charlotte Corday (1743–1793)
2 Vertical Annual to perennial herbs of the Mediterranean region
3 Vertical Tropical southeast Asian shrubby vine bearing spicy berrylike fruits
4 Vertical Ani
5 Vertical The first light of day
6 Vertical Title for the former hereditary monarch of Iran
7 Vertical A photographer who operates a movie camera
8 Vertical A city in southern Turkey on the Seyhan River
9 Vertical An arid region with little or no vegetation
10 Vertical Surrealist Spanish painter (1904–1989)
11 Vertical Any of various water-soluble compounds having a sour taste and capable of turning litmus red and reacting with a base to form a salt
12 Vertical A native or inhabitant of Thailand
13 Vertical (in Gnosticism) a divine power or nature emanating from the Supreme Being and playing various roles in the operation of the universe
21 Vertical An active volcano in southeastern Colombia in the Andes
22 Vertical A lepton of very great mass
26 Vertical A member of the South American Indian people living in Brazil and Paraguay
28 Vertical The main sensory nerve of the face and motor nerve for the muscles of mastication
29 Vertical A miniature whirlpool or whirlwind resulting when the current of a fluid doubles back on itself
30 Vertical British artist and writer of nonsense verse (1812–1888)
31 Vertical Chocolate cookie with white cream filling
32 Vertical A ballistic missile that is capable of traveling from one continent to another
33 Vertical A three-tone Chadic language
34 Vertical A capacity unit used for measuring fresh herring
36 Vertical Large sweet juicy hybrid between tangerine and grapefruit having a thick wrinkled skin
39 Vertical Plain-woven (often glazed) fabric of wool or wool and cotton used especially formerly for linings and garments and curtains
40 Vertical A unit of apothecary weight equal to 480 grains or one twelfth of a pound
45 Vertical A town in central Belgium
47 Vertical A long brightly colored shawl
49 Vertical A book in the Old Testament describing how Joshua led the Israelites into Canaan (the Promised Land) after the death of Moses
51 Vertical A nonsteroidal anti-inflammatory medicine (trade names Advil and Motrin and Nuprin) used to relieve the pain of arthritis and as an analgesic and antipyretic
52 Vertical Goat-like antelope of central Eurasia having a stubby nose like a proboscis
53 Vertical United States tennis player (born in Yugoslavia in 1973)
54 Vertical A slight wetness
55 Vertical Succulent plants having rosettes of leaves usually with fiber like hemp and spikes of showy flowers
56 Vertical Activity involved in maintaining something in good working order
57 Vertical (South African) a journey by ox wagon (especially an organized migration by a group of settlers)
58 Vertical A mountain lake (especially one formed by glaciers)
1 Horizontal Советский летчик-испытатель, Герой Советского Союза, один из участников беспосадочного перелета Москва — Северный полюс — Ванкувер
2 Horizontal Уха
3 Horizontal Прорицатель
4 Horizontal Город в Италии, на острове Сицилия
5 Horizontal Извитая текстурированная нить, получаемая гофрированием в обогреваемых камерах
6 Horizontal Французский кинорежиссёр, сценарист (''Дурная кровь'', ''Парень встречает девушку'')
7 Vertical Серебряная монета Великого княжества Литовского 16 в.
8 Vertical Американский биохимик, впервые синтезировал ген тРНК (Нобелевская премия 1968)
9 Vertical Город в Российской Федерации, Северная Осетия, на река Ардон, на Военно-Осетинской дороге
10 Vertical Горизонтальная ниша в стене погребальной камеры, куда клали покойного и замуровывали или завешивали пологом
11 Vertical Бедренная часть туши
12 Vertical Город на юго-востоке Франции
1 Horizontal A member of the Indian people of northern California and southern Oregon
2 Horizontal A member of one of the four divisions of the prehistoric Greeks
3 Horizontal Can become addictive
4 Horizontal Greek god of light
5 Horizontal Small personal or clothing or sewing items
6 Horizontal Valuable timber tree of New Zealand yielding hard reddish wood used for furniture and bridges and wharves
7 Vertical A straight line that intersects a curve at two or more points
8 Vertical Any of several crested Old World birds with a slender down-curving bill
9 Vertical American novelist noted for children’s books (1832–1888)
10 Vertical North American bluebirds
11 Vertical A person whose occupation is making and altering garments
12 Vertical Type genus of the Annonaceae
Заключение:
Применение SAT солвера поднимает рамку сложности кроссвордов, которые можно сгенерировать. Как и в прошлой статье, я хочу задать следующую непокоренную вершину — составить кроссворд из русских или английских слов в виде квадрата 7 на 7. Кто примет вызов?
