Алгоритм генерации кроссворда

Question

Учитывая список слов, как бы вы организовали их в сетку кроссвордов?

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

Будут ли доступны какие-либо примеры Java?

Answer 1

Я придумал решение, которое, вероятно, не самое эффективное, но оно работает достаточно хорошо. В основном:

1. Сортировка всех слов по длине по убыванию.
2. Возьмите первое слово и поместите его на доску.
3. Возьми следующее слово.
4. Просмотрите все слова, которые уже есть на доске, и посмотрите, есть ли какие-либо возможные пересечения (какие-либо общие буквы) с этим словом.
5. Если для этого слова есть возможное местоположение, прокрутите все слова на доске и проверьте, не мешает ли новое слово.
6. Если это слово не разбивает доску, поместите его туда и перейдите к шагу 3, в противном случае продолжайте поиск места (шаг 4).
7. Продолжайте этот цикл, пока все слова не будут помещены или не будут помещены.

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

• В конце генерации кроссворда присвойте ему оценку, исходя из того, сколько слов было размещено (чем больше, тем лучше), насколько велика доска (чем меньше, тем лучше) и соотношением высоты и ширины. (чем ближе к 1, тем лучше). Создайте несколько кроссвордов, а затем сравните их оценки и выберите лучший.
  • Вместо того, чтобы выполнять произвольное количество итераций, я решил создать как можно больше кроссвордов за произвольное количество времени. Если у вас есть только небольшой список слов, то вы получите десятки возможных кроссвордов за 5 секунд. Кроссворд большего размера можно выбрать только из 5-6 вариантов.
• При размещении нового слова вместо того, чтобы размещать его сразу после нахождения приемлемого местоположения, дайте этому местоположению слова оценку, основанную на том, насколько оно увеличивает размер сетки и сколько существует пересечений (в идеале вы хотите слово, которое нужно пересечь 2-3 другими словами). Отслеживайте все позиции и их оценки, а затем выберите лучшую.

Answer 2

Я только недавно написал свой собственный на Python. Вы можете найти его здесь: http://bryanhelmig.com/python-crossword-puzzle-generator/. Он не создает плотные кроссворды в стиле NYT, но стиль кроссвордов, который вы можете найти в детской книге головоломок.

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

1. Создайте сетку любого размера и список слов.
2. Перемешать список слов, а затем отсортировать слова по длинному и короткому.
3. Поместите первое и самое длинное слово в крайнее левое положение, 1,1 (по вертикали или горизонтали).
4. Переходите к следующему слову, циклически перебирайте каждую букву в слове и каждую ячейку в таблице, ища совпадения букв в букве.
5. Когда совпадение найдено, просто добавьте эту позицию в список предлагаемых координат для этого слова.
6. Переберите предложенный список координат и «оцените» расположение слов на основе количества других слов, которые оно пересекает. Оценки 0 указывают либо на неправильное размещение (рядом с существующими словами), либо на отсутствие пересечений слов.
7. Вернуться к шагу # 4, пока список слов не будет исчерпан. Дополнительный второй проход.
8. Теперь у нас должен быть кроссворд, но качество можно ударить или пропустить из-за некоторых случайных размещений. Итак, мы буферизируем этот кроссворд и вернемся к шагу # 2. Если у следующего кроссворда есть больше слов, помещенных на доску, он заменяет кроссворд в буфере. Время ограничено (найдите лучший кроссворд за x секунд).

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

Answer 3

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

У него был список слов (и связанных подсказок), сохраненных в файле, отсортированном по убыванию по времени (так, чтобы менее используемые слова были в верхней части файла). Шаблон, в основном битовая маска, представляющая черные и свободные квадраты, был выбран случайным образом из пула, предоставленного клиентом.

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

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

Как только файл слова / подсказки достигал определенного размера (и он добавлял 50-100 подсказок в день для этого клиента), редко случалось более двух или трех ручных исправлений, которые нужно было сделать за каждый кроссворд.

Answer 4

Этот алгоритм создает 50 плотных 6x9 стрелок кроссвордов за 60 секунд. Он использует базу данных слов (со словом + подсказки) и базу данных досок (с предварительно сконфигурированными досками).

1) Search for all starting cells (the ones with an arrow), store their size and directions
2) Loop through all starting cells
2.1) Search a word
2.1.1) Check if it was not already used
2.1.2) Check if it fits
2.2) Add the word to the board
3) Check if all cells were filled

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

---

Пример:

Предварительно настроенная плата 6x9:

(# означает один наконечник в одной ячейке,% означает два наконечника в одной ячейке, стрелки не показаны)

# - # # - % # - # 
- - - - - - - - - 
# - - - - - # - - 
% - - # - # - - - 
% - - - - - % - - 
- - - - - - - - - 

Сгенерированная доска 6x9:

# C # # P % # O # 
S A T E L L I T E 
# N I N E S # T A 
% A B # A # G A S 
% D E N S E % W E 
C A T H E D R A L 

Советы [строка, столбец]:

[1,0] SATELLITE: Used for weather forecast
[5,0] CATHEDRAL: The principal church of a city
[0,1] CANADA: Country on USA's northern border
[0,4] PLEASE: A polite way to ask things
[0,7] OTTAWA: Canada's capital
[1,2] TIBET: Dalai Lama's region
[1,8] EASEL: A tripod used to put a painting
[2,1] NINES: Dressed up to (?)
[4,1] DENSE: Thick; impenetrable
[3,6] GAS: Type of fuel
[1,5] LS: Lori Singer, american actress
[2,7] TA: Teaching assistant (abbr.)
[3,1] AB: A blood type
[4,3] NH: New Hampshire (abbr.)
[4,5] ED: (?) Harris, american actor
[4,7] WE: The first person of plural (Grammar)

Answer 5

Хотя это более старый вопрос, я попытаюсь ответить на основе аналогичной работы, которую я проделал.

Существует много подходов к решению проблем с ограничениями (в основном это класс сложности NPC).

Это связано с комбинаторной оптимизацией и программированием ограничений. В этом случае ограничения - это геометрия сетки и требование, чтобы слова были уникальными и т. Д.

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

Эффективная простота может быть просто высшей мудростью!

Требования предъявлялись к более или менее полному компилятору кроссвордов и компоновщику (visual WYSIWYG).

Оставляя в стороне конструктор WYSIWYG, схема компилятора была такой:

1. Загрузить доступные списки слов (отсортированные по длине слова, т.е. 2,3, .., 20)

2. Найдите слова (то есть слова сетки) на сетке, созданной пользователем (например, слово в точке x, y длиной L, горизонтальной или вертикальной) (сложность O (N))

3. Вычислить точки пересечения слов сетки (которые необходимо заполнить) (сложность O (N ^ 2))

4. Вычислить пересечения слов в списках слов с различными буквами алфавита (это позволяет искать подходящие слова с помощью шаблона, например. Тезис Sik Cambon, используемый cwc ) (сложность O (WL * AL))

Шаги .3 и .4 позволяют выполнить эту задачу:

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

б. Пересечение слов в списке слов с алфавитом позволяет найти подходящие (подходящие) слова, которые соответствуют данному «шаблону» (например, «A» на 1-м месте и «B» на 3-м месте и т. Д.)

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

ПРИМЕЧАНИЕ: если сетка и база данных слов постоянны, предыдущие шаги можно выполнить один раз.

1. Первым шагом алгоритма является случайное выделение пустого словосочетания (слова сетки) и заполнение его словом-кандидатом из связанного с ним списка слов (рандомизация позволяет создавать различные солютоны в последовательных выполнениях алгоритма) (сложность O (1) или O (N))

2. Для каждого еще пустого слота слов (у которого есть пересечения с уже заполненными слотами слов), вычислите отношение ограничений (это может варьироваться, просто число доступных решений на этом шаге) и отсортируйте пустые слоты слов по этому коэффициент (сложность O (NlogN) или O (N))

3. Переберите пустые слова, вычисленные на предыдущем шаге, и для каждого попробуйте несколько решений cancdidate (убедившись, что «согласованность дуги сохраняется», т. Е. У сетки есть решение после этого шага, если используется это слово ) и отсортировать их в соответствии с максимальной доступностью для следующего шага (т. е. следующий шаг имеет максимально возможные решения, если это слово используется в то время в этом месте и т. д.) (сложность O (N * MaxCandidatesUsed))

4. Заполните это слово (отметьте его как заполненное и перейдите к шагу 2)

5. Если не найдено ни одного слова, удовлетворяющего критериям шага .3, попробуйте вернуться к другому подходящему решению некоторого предыдущего шага (здесь критерии могут отличаться) (сложность O (N))

6. Если найден возврат, используйте альтернативу и при необходимости сбросьте все уже заполненные слова, которые, возможно, потребуется сбросить (пометьте их как незаполненные снова) (сложность O (N))

7. Если откат не найден, решение не может быть найдено (по крайней мере, с этой конфигурацией, начальным начальным числом и т. Д.)

8. В противном случае, когда все слова заполнены, у вас есть одно решение

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

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

PS. все это (и другие) были реализованы в чистом JavaScript (с параллельной обработкой и WYSIWYG) возможностью

PS2. Алгоритм может быть легко распараллелен для получения более одного (другого) решения одновременно

Надеюсь, это поможет

Answer 6

Почему бы просто не использовать случайный вероятностный подход для начала. Начните со слова, а затем несколько раз выберите случайное слово и попробуйте вписать его в текущее состояние головоломки, не нарушая ограничения по размеру и т. Д. Если вы не справитесь, просто начните все сначала.

Вы будете удивлены, как часто работает такой подход Монте-Карло.

Answer 7

Вот некоторый код javascript, основанный на ответе Никфа и коде Питона Брайана. Просто опубликовать его на случай, если кому-то еще это понадобится в js.

function board(cols, rows) { //instantiator object for making gameboards
this.cols = cols;
this.rows = rows;
var activeWordList = []; //keeps array of words actually placed in board
var acrossCount = 0;
var downCount = 0;

var grid = new Array(cols); //create 2 dimensional array for letter grid
for (var i = 0; i < rows; i++) {
    grid[i] = new Array(rows);
}

for (var x = 0; x < cols; x++) {
    for (var y = 0; y < rows; y++) {
        grid[x][y] = {};
        grid[x][y].targetChar = EMPTYCHAR; //target character, hidden
        grid[x][y].indexDisplay = ''; //used to display index number of word start
        grid[x][y].value = '-'; //actual current letter shown on board
    }
}

function suggestCoords(word) { //search for potential cross placement locations
    var c = '';
    coordCount = [];
    coordCount = 0;
    for (i = 0; i < word.length; i++) { //cycle through each character of the word
        for (x = 0; x < GRID_HEIGHT; x++) {
            for (y = 0; y < GRID_WIDTH; y++) {
                c = word[i];
                if (grid[x][y].targetChar == c) { //check for letter match in cell
                    if (x - i + 1> 0 && x - i + word.length-1 < GRID_HEIGHT) { //would fit vertically?
                        coordList[coordCount] = {};
                        coordList[coordCount].x = x - i;
                        coordList[coordCount].y = y;
                        coordList[coordCount].score = 0;
                        coordList[coordCount].vertical = true;
                        coordCount++;
                    }

                    if (y - i + 1 > 0 && y - i + word.length-1 < GRID_WIDTH) { //would fit horizontally?
                        coordList[coordCount] = {};
                        coordList[coordCount].x = x;
                        coordList[coordCount].y = y - i;
                        coordList[coordCount].score = 0;
                        coordList[coordCount].vertical = false;
                        coordCount++;
                    }
                }
            }
        }
    }
}

function checkFitScore(word, x, y, vertical) {
    var fitScore = 1; //default is 1, 2+ has crosses, 0 is invalid due to collision

    if (vertical) { //vertical checking
        for (i = 0; i < word.length; i++) {
            if (i == 0 && x > 0) { //check for empty space preceeding first character of word if not on edge
                if (grid[x - 1][y].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            } else if (i == word.length && x < GRID_HEIGHT) { //check for empty space after last character of word if not on edge
                 if (grid[x+i+1][y].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            }
            if (x + i < GRID_HEIGHT) {
                if (grid[x + i][y].targetChar == word[i]) { //letter match - aka cross point
                    fitScore += 1;
                } else if (grid[x + i][y].targetChar != EMPTYCHAR) { //letter doesn't match and it isn't empty so there is a collision
                    fitScore = 0;
                    break;
                } else { //verify that there aren't letters on either side of placement if it isn't a crosspoint
                    if (y < GRID_WIDTH - 1) { //check right side if it isn't on the edge
                        if (grid[x + i][y + 1].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                    if (y > 0) { //check left side if it isn't on the edge
                        if (grid[x + i][y - 1].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                }
            }

        }

    } else { //horizontal checking
        for (i = 0; i < word.length; i++) {
            if (i == 0 && y > 0) { //check for empty space preceeding first character of word if not on edge
                if (grid[x][y-1].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            } else if (i == word.length - 1 && y + i < GRID_WIDTH -1) { //check for empty space after last character of word if not on edge
                if (grid[x][y + i + 1].targetChar != EMPTYCHAR) { //adjacent letter collision
                    fitScore = 0;
                    break;
                }
            }
            if (y + i < GRID_WIDTH) {
                if (grid[x][y + i].targetChar == word[i]) { //letter match - aka cross point
                    fitScore += 1;
                } else if (grid[x][y + i].targetChar != EMPTYCHAR) { //letter doesn't match and it isn't empty so there is a collision
                    fitScore = 0;
                    break;
                } else { //verify that there aren't letters on either side of placement if it isn't a crosspoint
                    if (x < GRID_HEIGHT) { //check top side if it isn't on the edge
                        if (grid[x + 1][y + i].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                    if (x > 0) { //check bottom side if it isn't on the edge
                        if (grid[x - 1][y + i].targetChar != EMPTYCHAR) { //adjacent letter collision
                            fitScore = 0;
                            break;
                        }
                    }
                }
            }

        }
    }

    return fitScore;
}

function placeWord(word, clue, x, y, vertical) { //places a new active word on the board

    var wordPlaced = false;

    if (vertical) {
        if (word.length + x < GRID_HEIGHT) {
            for (i = 0; i < word.length; i++) {
                grid[x + i][y].targetChar = word[i];
            }
            wordPlaced = true;
        }
    } else {
        if (word.length + y < GRID_WIDTH) {
            for (i = 0; i < word.length; i++) {
                grid[x][y + i].targetChar = word[i];
            }
            wordPlaced = true;
        }
    }

    if (wordPlaced) {
        var currentIndex = activeWordList.length;
        activeWordList[currentIndex] = {};
        activeWordList[currentIndex].word = word;
        activeWordList[currentIndex].clue = clue;
        activeWordList[currentIndex].x = x;
        activeWordList[currentIndex].y = y;
        activeWordList[currentIndex].vertical = vertical;

        if (activeWordList[currentIndex].vertical) {
            downCount++;
            activeWordList[currentIndex].number = downCount;
        } else {
            acrossCount++;
            activeWordList[currentIndex].number = acrossCount;
        }
    }

}

function isActiveWord(word) {
    if (activeWordList.length > 0) {
        for (var w = 0; w < activeWordList.length; w++) {
            if (word == activeWordList[w].word) {
                //console.log(word + ' in activeWordList');
                return true;
            }
        }
    }
    return false;
}

this.displayGrid = function displayGrid() {

    var rowStr = "";
    for (var x = 0; x < cols; x++) {

        for (var y = 0; y < rows; y++) {
            rowStr += "<td>" + grid[x][y].targetChar + "</td>";
        }
        $('#tempTable').append("<tr>" + rowStr + "</tr>");
        rowStr = "";

    }
    console.log('across ' + acrossCount);
    console.log('down ' + downCount);
}

//for each word in the source array we test where it can fit on the board and then test those locations for validity against other already placed words
this.generateBoard = function generateBoard(seed = 0) {

    var bestScoreIndex = 0;
    var top = 0;
    var fitScore = 0;
    var startTime;

    //manually place the longest word horizontally at 0,0, try others if the generated board is too weak
    placeWord(wordArray[seed].word, wordArray[seed].displayWord, wordArray[seed].clue, 0, 0, false);

    //attempt to fill the rest of the board 
    for (var iy = 0; iy < FIT_ATTEMPTS; iy++) { //usually 2 times is enough for max fill potential
        for (var ix = 1; ix < wordArray.length; ix++) {
            if (!isActiveWord(wordArray[ix].word)) { //only add if not already in the active word list
                topScore = 0;
                bestScoreIndex = 0;

                suggestCoords(wordArray[ix].word); //fills coordList and coordCount
                coordList = shuffleArray(coordList); //adds some randomization

                if (coordList[0]) {
                    for (c = 0; c < coordList.length; c++) { //get the best fit score from the list of possible valid coordinates
                        fitScore = checkFitScore(wordArray[ix].word, coordList[c].x, coordList[c].y, coordList[c].vertical);
                        if (fitScore > topScore) {
                            topScore = fitScore;
                            bestScoreIndex = c;
                        }
                    }
                }

                if (topScore > 1) { //only place a word if it has a fitscore of 2 or higher

                    placeWord(wordArray[ix].word, wordArray[ix].clue, coordList[bestScoreIndex].x, coordList[bestScoreIndex].y, coordList[bestScoreIndex].vertical);
                }
            }

        }
    }
    if(activeWordList.length < wordArray.length/2) { //regenerate board if if less than half the words were placed
        seed++;
        generateBoard(seed);
    }
}
}
function seedBoard() {
    gameboard = new board(GRID_WIDTH, GRID_HEIGHT);
    gameboard.generateBoard();
    gameboard.displayGrid();
}

Answer 8

Я бы сгенерировал два числа: длина и оценка скрэббл. Предположим, что низкий балл Scrabble означает, что к нему легче присоединиться (низкие баллы = много общих букв). Сортировать список по убыванию по длине и возрастанию по шкале Эрудита.

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

Ополосните и повторите, и это должно генерировать кроссворд.

Конечно, я почти уверен, что это O (n!), И не обязательно завершить кроссворд для вас, но, возможно, кто-то сможет его улучшить.

Answer 9

Я играл с генератором кроссвордов и нашел это самым важным:

0. !/usr/bin/python

1. а. allwords.sort(key=len, reverse=True)

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

2. первая, возьмите первую пару и разместите их поперек и вниз от 0,0; сохраните первый как наш текущий кроссворд «лидер».

3. переместить курсор по диагонали или случайному порядку с большей вероятностью диагонали в следующую пустую ячейку

4. перебираем слова как и используем длину свободного места для определения максимальной длины слова: temp=[] for w_size in range( len( w_space ), 2, -1 ) : # t for w in [ word for word in allwords if len(word) == w_size ] : # if w not in temp and putTheWord( w, w_space ) : # temp.append( w )

5. для сравнения слова со свободным пространством, которое я использовал, т.е.:

   w_space=['c','.','a','.','.','.'] # whereas dots are blank cells
   
   # CONVERT MULTIPLE '.' INTO '.*' FOR REGEX
   
   pattern = r''.join( [ x.letter for x in w_space ] )
   pattern = pattern.strip('.') +'.*' if pattern[-1] == '.' else pattern
   
   prog = re.compile( pattern, re.U | re.I )
   
   if prog.match( w ) :
       #
       if prog.match( w ).group() == w :
           #
           return True
   

6. после каждого успешно используемого слова, изменить направление. Цикл пока все ячейки заполнены ИЛИ у вас заканчиваются слова ИЛИ по пределу итераций, тогда:

# CHANGE ALL WORDS LIST inexOf1stWord = allwords.index( leading_w ) allwords = allwords[:inexOf1stWord+1][:] + allwords[inexOf1stWord+1:][:]

... и еще раз повторим новый кроссворд.

7. Составьте систему подсчета по легкости заполнения и некоторым расчетным калькам. Оцените текущий кроссворд и сузьте выбор, добавив его в список составленных кроссвордов, если ваша система подсчёта очков удовлетворяет.

8. После первого сеанса итерации повторите итерацию из списка сделанных кроссвордов, чтобы завершить задание.

При использовании большего количества параметров скорость может быть улучшена огромным фактором.

Answer 10

Я думал об этой проблеме. Я чувствую, что для создания действительно плотного кроссворда вы не можете надеяться, что вашего ограниченного списка слов будет достаточно. Поэтому вы можете взять словарь и поместить его в структуру данных «trie». Это позволит вам легко найти слова, которые заполняют оставленные пробелы. На самом деле, довольно эффективно реализовать обход, который, скажем, дает вам все слова вида "c? T".

Итак, мое общее мышление таково: создать какой-то подход относительно грубой силы, как описано здесь, чтобы создать крест низкой плотности, и заполнить пробелы словарными словами.

Если кто-то еще воспользовался этим подходом, пожалуйста, дайте мне знать.