Генерация кроссвордов — NP-полная задача. Каждая ячейка, в которой пересекаются два слова, создаёт ограничение, которому должны удовлетворять оба слова, и эти ограничения перемножаются в сетке, приводя к комбинаторному взрыву. Эффективного алгоритма, гарантирующего решение, не существует, но вооружившись подходящими эвристиками, можно создать нечто, работающее на удивление хорошо.

В конце 2021 года, уже сильно после начала локдауна, моя одержимость кроссвордом газеты The New York Times превратилась в хобби-проект. Я хотел написать приложение с кроссвордами, понял, что мне нужны сами кроссворды, попробовал сочинять их вручную, осознал унылость этого процесса и задался вопросом: можно ли генерировать их алгоритмически? В этом году я наконец-то выпустил Crosswarped для iOS и Android — игру в кроссворды, созданную на основе генератора, описываемого в этой статье.

Как оказалось, примерно в то же время Отис Питерсон работал над той же задачей в Свортморском колледже, представив свои результаты в 2021 году. Исходники были опубликованы в декабре 2024 года. Я обнаружил их в процессе написания статьи, когда искал удобное доказательство того, что генерация кроссвордов NP-полная. Оказалось, вполне можно цитировать эту работу!

Алгоритмы генерации кроссвордов, в том числе и алгоритм Питерсона, обычно решают ограниченную версию общей задачи, которая остаётся NP-полной: пусть у нас есть паттерн из блоков и белых клеток; нужно заполнить белые клетки словарными словами так, чтобы все слова по горизонтали и вертикали были реальными. Эта задача, называемая «заполнением кроссворда», тоже NP-полная.

Мне же хотелось решить другую задачу: одновременной генерации и паттерна, и слов. Мой алгоритм не начинает с фиксированной сетки, а сам в процессе своей работы решает, куда помещать чёрные клетки.

Может показаться, что такая свобода всё упрощает: если слово слишком короткое, можно просто добавить чёрную клетку! Но я думаю, что при этом происходит и резкое увеличение пространства решений.

Огромные пространства решений для кроссвордов

Возьмём одну строку из  клеток. Обозначим всё множество способов заполнения этой строки ​. Это множество включает в себя:

• Слова на всю длину: все ​ словарных слов ровно из  букв (в том числе фразы наподобие «BADIDEA», которые считаются допустимыми элементами словарей кроссвордов).

• Короткие слова с блоками по краям: любая валидная строка длины  (то есть ​) с чёрной ячейкой в начале или конце.

• Разделённые слова: два коротких слова, разделённые чёрной клеткой — все комбинации, длины которых суммарно равны  (с учётом блока).

Код

Если вы хотите изучить реализацию:

Версия на Go (рекомендуемая): в основной ветви Eyas/xwgen содержится почищенная реализация. В ней задействуется GCP Cloud Function, которую я применяю для генерации кроссвордов из веб-инструмента администрирования. Код собирается автономно, но вам придётся реализовать загрузчик списка слов (мой выполняет запросы к таблице BigQuery).

Версия на C# (предыдущая): в ветви csharp находится моя исходная реализация, интегрированная с редактором Windows UI. Я извлёк её из большой кодовой базы прототипирования при помощи git filter-repo. Сразу она не соберётся (в ней указаны несуществующие пути к спискам слов), зато демонстрирует эволюцию алгоритма.

Подход к решению задачи

При попытке решения NP-полной задачи необходимо для начала уяснить, что лучшее — враг хорошего. Это освободит вам руки, мотивирует начать с простейшего решения, а потом итеративно улучшать его.

Моей первой попыткой был абсолютно жадный алгоритм: выбираем случайное слово, умещающееся в первую строку, затем находим перпендикулярное ему слово, и так далее, с возвратом назад, если зайдём в тупик.

Я попробовал его на сетке размером 5x5. Совершенно ничего не получилось, программа просто минутами работала в цикле. Я начал визуализировать происходящее, чтобы понять, как скоро она терпит неудачу; оказалось, что очень быстро. Если мы выбираем случайные слова просто потому, что они умещаются в строки, то спустя 3-4 слова исчерпаем все варианты следующего слова.

Думаем строками

Первое наблюдение: вместо выбора отдельных слов нужно думать о целом множестве валидных строк для каждой горизонтали и вертикали.

Я рекурсивно определял множество возможных строк и использовал его для построения сетки по одной горизонтали/вертикали за раз.

В момент сетка пуста, и у каждой горизонтали и вертикали есть множество возможных сочетаний слов, равное ​ (где  — длина стороны кроссворда).

Затем я выбираю одно значение для случайной горизонтали или вертикали с последующей фильтрацией до совместимого множества возможных слов и продолжаю уже с ним.

Это было очень медленно, но иногда срабатывало для сеток 5x5. Однако программа требовала кучу памяти, и на моей машине она закачивалась, когда я пытался заполнять сетки 7x7.

Ленивая оценка вариантов

Множество всех возможных строк огромно, однако мы не обязаны материализовать его. Можно представить его в виде дерева вариантов, которые мы будем лениво фильтровать.

Иными словами, «множество возможных строк» — это лениво фильтруемое описание огромного множества. Оно поддерживает операции типа «отфильтровать по букве-ограничению в позиции (i)» и «пустое ли это множество?» без перечисления всех комбинаций.

Возможные комбинации строки из пяти букв хранятся не в виде плоского списка, а в виде дерева: узел Words (пятибуквенные словарные слова) в сочетании со структурными вариантами (BlockBefore, BlockAfter и так далее).

Рекурсивная грамматика определяется интерфейсом, позволяющим одинаково обрабатывать «список слов» и «сложную структуру из слов и блоков»:

type PossibleLines interface {
    FilterAny(constraint rune, index int) PossibleLines
}

Базовый случай — это простой список слов Words из словаря. Далее мы рекурсивно надстраиваем сложность:

• BlockBefore: строка, начинающаяся с чёрной клетки, за которой идёт валидная строка длины .

• BlockAfter: строка, которая заканчивается чёрной клеткой.

• BlockBetween: строка, образованная из Line(A) + Block + Line(B), где .

В реализации на Go BlockBetween — это struct, содержащая два дочерних дерева PossibleLines. В ней не хранятся конечные слова, это просто рецепт для их комбинирования:

type BlockBetween struct {
    first  PossibleLines
    second PossibleLines
}

Эта структура позволяет нам представить комбинаторные взрывы в компактном виде. BlockBetween не хранит все комбинации first и second; в нём содержатся только ссылки на них, и он может выразить декартово произведение двух множеств. На практике ему никогда не требуется итеративно обходить всё множество.

Например, для пятибуквенной строки множество возможных строк будет выглядеть так:

AllPossibleLines[5] =
    Compound(
        Words(WordsByLength[5]...),
        BlockBefore(AllPossibleLines[4]),
        BlockAfter(AllPossibleLines[4]),
    )

Типы наподобие Compound, BlockBefore, BlockAfter и BlockBetween реализуют примитивы, например итерации по всем возможным ответам, вычисление (приблизительного) размера множества и фильтрацию множества на основании ограничений; всё это происходит без материализации всего множества.

Это уже коренным образом поменяло ситуацию, и теперь, заручившись удачей, я мог заполнять сетки размером до 10x10, только требовались на это часы.

Распространение ограничений

Реализовав ленивые структуры данных, мы можем эффективно распространять ограничения при помощи алгоритма в стиле AC-3.

Когда мы выбрали слово в одной горизонтали, каждая пересекающая вертикаль даёт нам какую-то новую информацию. Если в клетке 3 по горизонтали, 4 по вертикали должна быть буква E (из-за пересекающего её вертикального слова), можно приказать PossibleLines 3 по горизонтали выполнить Filter('E', 4).

Метод Filter спускается вниз по дереву. Например, для BlockBetween он делает следующее:

1. BlockBetween: «Часть first, ты соответствуешь индексу 4? Да? Хорошо, отфильтруй себя. Нет? Тогда часть second, отфильтруй себя».

2. Words: «Отфильтруй все слова, в индексе которых нет буквы E».

Разбиение области: двоичный поиск по пространству решений

Даже при ленивой оценке и распространении ограничений процесс шёл слишком медленно: из списка вариантов выбиралось случайное слово и сетка фильтровалась на основании этого выбора.

Важное наблюдение: вместо выбора конкретных слов мы можем разбить пространство вариантов пополам. Если для горизонтали есть 10 тысяч вариантов строк, то мы не выбираем одно, а разбиваем это множество пополам и задаём вопрос: «Можно ли решить сетку, если в этой горизонтали использовать слово из первой половины словаря (A-M)?»

И вот что крайне важно: мы не проверяем каждое слово в этой половине. Мы просто решаем ограничить эту горизонталь словами из списка A-M, а затем распространить последствия по сетке при помощи распространения ограничений. Теперь горизонталь будет принимать только слова, начинающиеся с букв A до M, что ограничивает первую вертикаль буквами, которые могут стоять в начале слов из части A-M словаря, и так далее.

После распространения происходит одно из трёх событий:

1. Противоречие: для какой-то горизонтали или вертикали обнаруживается ноль валидных вариантов. Мы доказали, что ни одно слово в интервале A-M здесь не подойдёт, поэтому сразу же отсекаем пять тысяч слов и пробуем N-Z.

2. Найдено решение: мы сузили решение до конкретных слов — задача выполнена!

3. Остаётся неоднозначность: остаётся несколько вариантов. Мы выбираем горизонталь/вертикаль с наибольшим количеством ограничений и разделяем пополам количество её вариантов, рекурсивно опускаясь глубже.

Благодаря этому, если описывать «отфильтрованные варианты» достаточно эффективно (и лениво), то каждый этап такого разделения будет относительно малозатратным, потому что всю основную работу уже выполнило распространение ограничений. Чтобы PossibleLines был эффективным:

1. это должна быть неизменяемая структура, чтобы нам не приходилось выполнять клонирование при каждом разбиении;

2. концептуальные списки (то есть списки слов или составных вариантов) должны поддерживать эффективные срезы без копирования данных (например, срезы Go, span в C++ и так далее).

Благодаря этому каждое разбиение сохраняет неизменившиеся варианты и очень малозатратно заменяет те, которые мы разбиваем пополам.

Распространение ограничений на строку часто приводит к дополнительному распределению, например, к удалению всех слов, не соответствующих ограничению по конкретному индексу. Но обычно мы делаем это только тогда, когда собираемся погрузиться рекурсией глубже в пространство поиска.

Достаточно медленным оставался процесс выбора одной горизонтали или вертикали, а также выбор «случайного» значения во множестве их вариантов строк с последующей фильтрацией по нему остальной сетки.

Так как теперь у нас есть ленивые множества, не может ли каждый совершаемый нами «выбор» быть делением этого множества пополам?

Попросим объект PossibleLines выполнять MakeChoice().

• Если это список Words, делим его пополам.

• Если это BlockBetween, он делится на основании вариантов с одной стороны.

// Из generator.go
func (g *Generator) PossibleGrids(ctx context.Context) iter.Seq[Grid] {
    // ...
    // Находим "последнюю неопределённую" строку
    undecidedDown := root.getUndecidedIndexDown()

    // Разбиваем варианты на два множества
    // ...
}

По сути, так происходит двоичный поиск по пространству решений. Если утверждение «1 по горизонтали использует слово из A-M» приводит к противоречию, мы мгновенно отсекаем половину словаря для этой горизонтали.

Теперь наши типы вариантов строк должны поддерживать новые операции: получение множества символов, которые они могут содержать по конкретному индексу, и фильтрацию всех вариантов, не содержащих ни одного множества символов по указанному индексу.

После реализации такой системы сетки 10x10 решаются за секунды.

Дисквалификация выбора

Соответствия ограничению слов недостаточно: сетка может содержать валидные слова и всё равно оставаться бесполезной. Недопустимые сетки могут содержать:

• Повторяющиеся слова: одно и то же слово встречается в кроссворде дважды.

• Несвязанные области: чёрные клетки, которые делят сетку на изолированные «острова».

• Слишком большое количество блоков: сетки, в которых преобладают чёрные клетки, с малым количеством слов.

(В традиционных кроссвордах также требуется симметрия относительно вертикальной оси, но я намеренно отказался от этого ограничения — это эстетика, а не структура.)

Наивным решением было бы проверять эти условия только тогда, когда мы целиком заполним сетку (достигнем листа в дереве поиска). Но вы уже наверно поняли, что это будет слишком медленно.

Мы будем проверять точную невалидность как можно раньше. Так как каждый PossibleLines отслеживает не только возможные символы, но и те, которые есть точно, мы можем обнаруживать проблемы в процессе поиска. Если текущее состояние точно размещает блоки, которые приведут к появлению островов, то мы сразу отсекаем всё поддерево, его больше нет смысла исследовать дальше.

Быстрые операции со множествами символов

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

Моя первая реализация этого CharSet в буквальном смысле была множеством символов. Копирование его каждый раз, когда появлялось новое ограничение, было очень медленной процедурой.

Второй попыткой стал плотный список булевых значений по одному на символ моего алфавита и символ блока. Я решил использовать символы с a по z плюс ` в качестве символа блока, потому что в ASCII он находится непосредственно перед a, чтобы можно было полностью использовать массив без пробелов, который легко проверить за время .

Последняя итерация решила эти проблемы: битовая маска uint32. Нам нужно только 27 символов (a-z плюс символ блока `, удобно соседствующие в ASCII), что идеально подходит для такой маски. Для нахождения пересечения множеств при этом достаточно простого побитового AND.

// CharSet оптимально описывает множество символов при помощи манипуляций с битами.
// Он поддерживает символы от '`' (96) до 'z' (122), всего 27 символов.
// Это идеально умещается в uint32.
type CharSet struct {
	bits uint32
}

const (
	minChar  = '`'                   // 96
	maxChar  = 'z'                   // 122
	numChars = maxChar - minChar + 1 // 27 символов
	fullBits = 0x7ffffff
)

func (c *CharSet) Add(r rune) error { /*...*/ }
func (c *CharSet) AddAll(other *CharSet) { /*...*/ }
func (c *CharSet) Contains(r rune) bool { /*...*/ }
func (c  CharSet) IsFull() bool { /*...*/ }
func (c  CharSet) Count() int { /*...*/ }
func (c *CharSet) Clear() { /*...*/ }
func (c *CharSet) Clone() *CharSet { /*...*/ }
func (c *CharSet) ContainsAll(other *CharSet) bool { /*...*/ }
func (c *CharSet) Intersect(other *CharSet) { /*...*/ }
func (c  CharSet) Intersects(other CharSet) bool { /*...*/ }

Большинство операций представляет из себя одиночные побитовые команды. При фильтрации мы можем сразу же определить, что поддерево не подходит (пустое пересечение), совершенно не ограничено (все биты заданы) или частично ограничено (требует дополнительной фильтрации). Неподходящие или неограниченные поддеревья можно отбрасывать или использовать повторно без копирования.

А что насчёт описаний слов?

Когда начинаешь генерировать кроссворды, то понимаешь, что описания — это совершенно отдельная сложная тема. Когда я начинал этот проект, генерацию описаний вряд ли можно было автоматизировать. Ситуацию поменяли LLM, но возник риск, что моя идея приложения превратится в фабрику нейрослопа.

Изначально для превращения сгенерированных сеток в кроссворды я составлял описания слов сам. Возможно, в следующем посте стоит написать о том, как в эту часть процесса неминуемо залезли ИИ и LLM.

В заключение

Этим проектом я не стремился что-то доказать, а лишь искал прагматичный способ решения сложностей NP-полной задачи. Ленивые множества, быстрые фильтры на основе битовых масок и разбиение областей оказались достаточными для того, чтобы сделать генерацию маленьких кроссвордов лёгким и удобным процессом. Он не идеален, но позволяет быстро создавать кроссворды.

Результаты генерации всё равно кажутся искусственными: в создаваемых живыми людьми кроссвордах есть красота, которую сложно воссоздать алгоритмически. Но если вы уже решили на сегодня все придуманные людьми кроссворды и хотите ещё, то для этого вполне подойдут сгенерированные!