Алгоритм генерации кроссворда
Учитывая список слов, как бы вы организовали их в сетку кроссвордов?
Это не должно быть похоже на "правильную" кроссворд, которая симметрична или что-то в этом роде: просто выведите начальную позицию и направление для каждого слова.
Будут ли доступны какие-либо примеры Java?
13 ответов
Я придумал решение, которое, вероятно, не самое эффективное, но оно работает достаточно хорошо. В принципе:
- Сортировать все слова по длине по убыванию.
- Возьмите первое слово и поместите его на доску.
- Возьми следующее слово.
- Просмотрите все слова, которые уже есть на доске, и посмотрите, есть ли какие-либо возможные пересечения (какие-либо общие буквы) с этим словом.
- Если для этого слова есть возможное местоположение, прокрутите все слова на доске и проверьте, не мешает ли новое слово.
- Если это слово не сломает доску, поместите его туда и перейдите к шагу 3, в противном случае продолжайте поиск места (шаг 4).
- Продолжайте этот цикл, пока все слова не будут помещены или не будут помещены.
Это делает рабочий, но часто довольно плохой кроссворд. Я внес ряд изменений в основной рецепт, приведенный выше, чтобы добиться лучшего результата.
- В конце генерации кроссворда присвойте ему оценку на основе количества слов (чем больше, тем лучше), размера доски (чем меньше, тем лучше) и соотношения высоты и ширины (чем ближе до 1, тем лучше). Создайте несколько кроссвордов, а затем сравните их оценки и выберите лучший.
- Вместо того, чтобы выполнять произвольное количество итераций, я решил создать как можно больше кроссвордов за произвольное количество времени. Если у вас есть только небольшой список слов, то вы получите десятки возможных кроссвордов за 5 секунд. Кроссворд большего размера можно выбрать только из 5-6 вариантов.
- При размещении нового слова вместо того, чтобы размещать его сразу же после нахождения приемлемого местоположения, присвойте этому местоположению слово оценку в зависимости от того, насколько оно увеличивает размер сетки и сколько пересечений существует (в идеале вы хотите, чтобы каждое слово было пересечено 2-3 другими словами). Отслеживайте все позиции и их оценки, а затем выберите лучшую.
Я только недавно написал свой собственный на Python. Вы можете найти его здесь: http://bryanhelmig.com/python-crossword-puzzle-generator/. Это не создает плотные кроссворды в стиле Нью-Йорк Таймс, но стиль кроссвордов вы можете найти в детской книге головоломки.
В отличие от нескольких алгоритмов, которые я обнаружил там, которые реализовали случайный метод грубой силы размещения слов, как предложили некоторые, я попытался реализовать немного более умный подход грубой силы при размещении слов. Вот мой процесс:
- Создайте сетку любого размера и список слов.
- Перемешайте список слов, а затем сортируйте слова по длине и длине.
- Поместите первое и самое длинное слово в крайнее левое положение, 1,1 (вертикально или горизонтально).
- Перейдите к следующему слову, переберите каждую букву в слове и каждую ячейку в таблице, ища совпадения букв в букве.
- Когда совпадение найдено, просто добавьте эту позицию в предложенный список координат для этого слова.
- Зациклите предложенный список координат и "оцените" расположение слов на основе количества других слов, которые оно пересекает. Оценки 0 указывают либо на неправильное размещение (рядом с существующими словами), либо на отсутствие перекрестных слов.
- Вернуться к шагу № 4, пока список слов не исчерпан. Дополнительный второй проход.
- Теперь у нас должен быть кроссворд, но из-за некоторых случайных размещений качество можно ударить или пропустить. Итак, мы буферизируем этот кроссворд и вернемся к шагу #2. Если в следующем кроссворде на доске размещено больше слов, он заменяет кроссворд в буфере. Это время ограничено (найти лучший кроссворд в х секунд).
К концу у вас есть приличная кроссворд или поиск слова, так как они примерно одинаковы. Он работает довольно хорошо, но дайте мне знать, если у вас есть предложения по улучшению. Большие сетки работают экспоненциально медленнее; большие списки слов линейно. Большие списки слов также имеют гораздо больше шансов на лучшее размещение слов.
Я действительно написал программу генерации кроссвордов около десяти лет назад (она была загадочной, но те же правила применимы и к обычным кроссвордам).
У него был список слов (и связанных подсказок), сохраненных в файле, отсортированном по убыванию до настоящего времени (так, чтобы менее используемые слова были в верхней части файла). Шаблон, в основном битовая маска, представляющая черные и свободные квадраты, был выбран случайным образом из пула, предоставленного клиентом.
Затем для каждого неполного слова в загадке (в основном найдите первый пустой квадрат и посмотрите, является ли поле справа (поперечное слово) или нижнее (нижнее слово) также пустым), был выполнен поиск файл ищет первое подходящее слово, учитывая буквы уже в этом слове. Если не было подходящего слова, вы просто отметили все слово как неполное и пошли дальше.
В конце будут некоторые незавершенные слова, которые компилятор должен будет заполнить (и при желании добавить слово и ключ к файлу). Если они не могли придумать какие-либо идеи, они могли бы отредактировать кроссворд вручную, чтобы изменить ограничения или просто запросить полное повторное создание.
Как только файл слова / подсказки достигал определенного размера (и он добавлял 50-100 подсказок в день для этого клиента), редко случалось более двух или трех ручных исправлений, которые нужно было делать для каждого кроссворда.,
Этот алгоритм создает 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)
Хотя это более старый вопрос, я попытаюсь ответить на основе аналогичной работы, которую я проделал.
Есть много подходов к решению проблем ограничений (которые вообще находятся в классе сложности NPC).
Это связано с комбинаторной оптимизацией и программированием ограничений. В этом случае ограничения - это геометрия сетки и требование, чтобы слова были уникальными и т. Д.
Подходы рандомизации / отжига также могут работать (хотя и в правильной настройке).
Эффективная простота может быть просто высшей мудростью!
Требования предъявлялись к более или менее полному компилятору кроссвордов и (визуальному WYSIWYG) компоновщику.
Оставляя в стороне конструктор WYSIWYG, схема компилятора была такой:
Загрузить доступные списки слов (отсортированные по длине слова, т.е. 2,3,..,20)
Найти слова (то есть слова сетки) в сетке, созданной пользователем (например, слово в точке x,y длиной L, горизонтальной или вертикальной) (сложность O(N))
Вычислить точки пересечения слов сетки (которые необходимо заполнить) (сложность O(N^2))
Вычислить пересечения слов в списках слов с различными буквами алфавита (это позволяет искать подходящие слова, используя шаблон, например, тезис Sik Cambon, используемый cwc) (сложность O(WL*AL))
Шаги.3 и.4 позволяют выполнить эту задачу:
а. Пересечения слов сетки с самим собой позволяют создать "шаблон" для попытки найти совпадения в соответствующем списке слов доступных слов для этого слова сетки (используя буквы других пересекающихся слов с этим словом, которые уже заполнены на определенном уровне. шаг алгоритма)
б. Пересечение слов в списке слов с алфавитом позволяет найти подходящие (подходящие) слова, которые соответствуют данному "шаблону" (например, "A" на 1-м месте и "B" на 3-м месте и т. Д.)
Таким образом, с этими реализованными структурами данных использовался следующий алгоритм:
ПРИМЕЧАНИЕ: если сетка и база данных слов постоянны, предыдущие шаги можно выполнить один раз.
Первым шагом алгоритма является случайное выделение пустого словосочетания (сеточного слова) и заполнение его словом-кандидатом из связанного с ним словарного списка (рандомизация позволяет создавать различные солютоны в последовательных выполнениях алгоритма) (сложность O (1) или O(N))
Для каждого еще пустого слота слов (у которого есть пересечения с уже заполненными слотами слов), вычислите отношение ограничений (это может варьироваться, просто число доступных решений на этом шаге) и отсортируйте пустые слоты слов по этому соотношению (сложность O (NlogN)) или O(N))
Переберите пустые слова, вычисленные на предыдущем шаге, и для каждого попробуйте несколько решений cancdidate (убедившись, что "согласованность дуги сохраняется", то есть у сетки есть решение после этого шага, если используется это слово), и отсортируйте их в соответствии с максимальная доступность для следующего шага (т.е. следующий шаг имеет максимально возможные решения, если это слово используется в то время в этом месте и т. д.) (сложность O(N*MaxCandidatesUsed))
Заполните это слово (пометьте его как заполненное и перейдите к шагу 2)
Если не найдено ни одного слова, удовлетворяющего критериям шага.3, попробуйте вернуться к другому подходящему решению некоторого предыдущего шага (критерии могут варьироваться здесь) (сложность O(N))
Если откат найден, используйте альтернативу и при необходимости сбросьте все уже заполненные слова, которые могут нуждаться в сбросе (пометьте их как незаполненные снова) (сложность O(N))
Если возврат не найден, решение не может быть найдено (по крайней мере, с этой конфигурацией, начальным начальным числом и т. Д.)
Иначе, когда все слова заполнены, у вас есть одно решение
Этот алгоритм выполняет случайное последовательное блуждание дерева решений задачи. Если в какой-то момент существует тупик, он выполняет возврат к предыдущему узлу и следует по другому маршруту. До тех пор, пока не будет найдено решение или количество кандидатов на различные узлы исчерпаны.
Часть согласованности гарантирует, что найденное решение действительно является решением, а случайная часть позволяет создавать разные решения в разных исполнениях, а также в среднем иметь лучшую производительность.
PS. все это (и другие) были реализованы в чистом JavaScript (с параллельной обработкой и WYSIWYG) возможностью
PS2. Алгоритм можно легко распараллелить, чтобы получить более одного (другого) решения одновременно
Надеюсь это поможет
Почему бы просто не использовать случайный вероятностный подход для начала. Начните со слова, а затем несколько раз выберите случайное слово и попробуйте вписать его в текущее состояние головоломки, не нарушая ограничений по размеру и т. Д. Если вы не справитесь, просто начните все сначала.
Вы будете удивлены, как часто работает такой подход Монте-Карло.
Вот код javascript, основанный на ответе Никфа и коде Брайана на Python. Просто опубликовать его на случай, если кому-то еще это понадобится в 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();
}
Я бы сгенерировал два числа: Длина и Скраббл. Предположим, что низкий балл Scrabble означает, что к нему легче присоединиться (низкие баллы = много общих букв). Сортируйте список по убыванию по длине и по возрастанию.
Далее просто идите вниз по списку. Если слово не пересекается с существующим словом (сверьтесь с каждым словом по его длине и количеству скрэббл соответственно), поместите его в очередь и проверьте следующее слово.
Промыть и повторить, и это должно генерировать кроссворд.
Конечно, я уверен, что это O(n!), И кроссворд для вас не гарантированно, но, возможно, кто-то сможет его улучшить.
Он появляется как проект в курсе AI CS50 из Гарварда. Идея состоит в том, чтобы сформулировать проблему генерации кроссворда как проблему удовлетворения ограничений и решить ее с помощью обратного отслеживания с различными эвристиками, чтобы уменьшить пространство поиска.
Для начала нам понадобится пара входных файлов:
- Структура кроссворда (которая выглядит как следующая, например, где '#' представляет символы, которые не следует заполнять, а '_' представляет символы, которые необходимо заполнить)
`
###_####_#
____####_#
_##_#_____
_##_#_##_#
______####
#_###_####
#_##______
#_###_##_#
_____###_#
#_######_#
##_______#
`
Входной словарь (список слов / словарь), из которого будут выбраны слова-кандидаты (как показано ниже).
a abandon ability able abortion about above abroad absence absolute absolutely ...
Теперь CSP определен и должен быть решен следующим образом:
- Переменные определяются как имеющие значения (т. Е. Их домены) из списка слов (словаря), предоставленного в качестве входных данных.
- Каждая переменная представлена тремя кортежами: (координата сетки, направление, длина), где координата представляет начало соответствующего слова, направление может быть горизонтальным или вертикальным, а длина определяется как длина слова, которое будет назначен.
- Ограничения определяются предоставленной структурой: например, если горизонтальная и вертикальная переменные имеют общий символ, это будет представлено как ограничение перекрытия (дуги).
- Теперь можно использовать алгоритмы согласованности узлов и согласованности дуги AC3 для уменьшения количества доменов.
- Затем для получения решения (если оно существует) для CSP с помощью MRV (минимальное оставшееся значение), степени и т. Д. Эвристика может использоваться для выбора следующей неназначенной переменной, а эвристика, такая как LCV (наименьшее ограничивающее значение), может использоваться для домена: упорядочивание, чтобы алгоритм поиска работал быстрее.
Ниже показан результат, который был получен с использованием реализации алгоритма решения CSP:
`
███S████D█
MUCH████E█
E██A█AGENT
S██R█N██Y█
SUPPLY████
█N███O████
█I██INSIDE
█Q███E██A█
SUGAR███N█
█E██████C█
██OFFENSE█
`
Следующая анимация показывает шаги возврата:
Вот еще один со списком слов на языке бангла (бенгали):
Я думал об этой проблеме. Я чувствую, что для создания действительно плотного кроссворда вы не можете надеяться, что вашего ограниченного списка слов будет достаточно. Следовательно, вы можете взять словарь и поместить его в структуру данных "trie". Это позволит вам легко найти слова, которые заполняют оставленные пробелы. На самом деле довольно эффективно реализовать обход, который, скажем, дает вам все слова вида "c? T".
Итак, мое общее мышление таково: создать какой-то подход относительно грубой силы, как описано здесь, чтобы создать крест с низкой плотностью, и заполнить пробелы словарными словами.
Если кто-то еще воспользовался этим подходом, пожалуйста, дайте мне знать.
Я играл с генератором кроссвордов и нашел это самым важным:
0.!/usr/bin/python
а.
allwords.sort(key=len, reverse=True)б. создайте некоторый элемент / объект, такой как курсор, который будет обходить матрицу для легкой ориентации, если вы не захотите выполнить итерацию по случайному выбору позже.
во-первых, возьмите первую пару и разместите их поперек и вниз от 0,0; сохраните первый как наш текущий кроссворд "лидер".
переместить курсор по диагонали или случайному порядку с большей вероятностью диагонали в следующую пустую ячейку
переберите слова "как" и используйте длину свободного места, чтобы определить максимальную длину слова:
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 )сравнить слово со свободным пространством, которое я использовал, т.е.
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после каждого успешно используемого слова меняйте направление. Цикл пока все ячейки заполнены ИЛИ у вас заканчиваются слова ИЛИ по пределу итераций:
# CHANGE ALL WORDS LIST
inexOf1stWord = allwords.index( leading_w )
allwords = allwords[:inexOf1stWord+1][:] + allwords[inexOf1stWord+1:][:]
... и еще раз повторим новый кроссворд.
Составьте систему начисления баллов по легкости заполнения и некоторым оценкам кальки. Дайте оценку за текущий кроссворд и сузьте выбор позже, добавив его в список сделанных кроссвордов, если оценка удовлетворена вашей системой подсчета очков.
После первого сеанса итерации повторите итерацию из списка составленных кроссвордов, чтобы завершить работу.
При использовании большего количества параметров скорость может быть улучшена огромным фактором.
Я закодировал 100% jQuery Решение этой проблемы.
Пример демонстрации: http://www.earthfluent.com/crossword-puzzle-demo.html
Исходный код: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator
Цель алгоритма, который я использовал:
- Минимизируйте количество неиспользуемых квадратов в сетке, насколько это возможно.
- Иметь как можно больше смешанных слов.
- Вычислить в чрезвычайно быстрое время.
Я опишу алгоритм, который я использовал:
Сгруппируйте слова в соответствии с общими буквами.
Из этих групп создайте наборы новой структуры данных ("блоки слов"), которая является основным словом (которое проходит через все другие слова), а затем другими словами (которые проходят через основное слово).
Начните кроссворд с самого первого из этих блоков слов в самой верхней левой части кроссворда.
Для остальных блоков слов, начиная с правой нижней части позиции кроссворда, двигайтесь вверх и влево до тех пор, пока не останется больше свободных мест для заполнения. Если пустых столбцов больше, чем влево, двигайтесь вверх и наоборот.
Я бы получил индекс каждой буквы, используемой каждым словом, чтобы узнать возможные крестики. Тогда я бы выбрал самое большое слово и использовал его в качестве основы. Выберите следующий большой и пересечь его. Промыть и повторить. Это, вероятно, проблема NP.
Другая идея заключается в создании генетического алгоритма, в котором метрикой силы является количество слов, которое вы можете поместить в таблицу.
Трудная часть, которую я нахожу, - это когда невозможно узнать определенный список.
Вот некоторая Swift-версия генератора кроссвордов, основанная на коде Bryan's python.
Просто делюсь этим, если кому-то это нужно.