Генерация кроссвордов с помощью SAT солвера

    На Хабре было несколько статей про генерацию кроссвордов. В одной из них «Самый сложный кроссворд, составленный компьютером» говорилось про очень сложный кроссворд, составленный компьютером, которому «пришлось немного помочь» вручную. Во второй статье «Алгоритм формирования кроссвордов» рассказывается про алгоритм, созданный автором для составления кроссвордов, и отмечается, что этот «самый сложный кроссворд» остался непокоренным и говорится, что «может быть эта непокоренная вершина вдохновит кого-нибудь на новый штурм!». Что же, можно принять вызов. Что из этого получилось, смотрите под катом.

    В начале приведу этот самый сложный кроссворд:

    image

    Первое, что необходимо найти — это список слов, которые используются при составлении данного кроссворда. В качестве такого списка были взяты два файла из вышеупомянутых статей — один файл с русскими словами, один файл с английскими. Затем необходимо было решить главный вопрос — какой алгоритм использовать для составления этого кроссворда. Собственно «сложным» этот кроссворд делает не количество слов, а количество их пересечений. Понятно, что перебор «в лоб» (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)

    Кроссворд 6 на 6 на русском языке:
    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 Город на юго-востоке Франции

    Кроссворд 6 на 6 на английском языке:
    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. Кто примет вызов?
    • +10
    • 5,7k
    • 2
    Поделиться публикацией
    Похожие публикации
    Никаких подозрительных скриптов, только релевантные баннеры. Не релевантные? Пиши на: adv@tmtm.ru с темой «Полундра»

    Зачем оно вам?
    Реклама
    Комментарии 2
    • 0
      Интересовала эта задача в студенческие годы (лет 25 назад), но запнулся на поиске базы слов с расшифровками — интернета тогда не было… :(
      • 0
        Выложите код пожалуйста, заранее спасибо.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.