Алгоритм создания кроссворда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот алгоритм создает 50 плотных 6×9 стрелочных кроссвордов за 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 

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


Пример:

Предварительно настроенная доска 6×9:

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

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

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

 # C # # P % # O # SATELLITE # NINES # TA % AB # A # GAS % DENSE % WECATHEDRAL 

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

 [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) 

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

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

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

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

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

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

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

Требования были для более или менее полного компилятора кроссвордов и (визуального WYSIWYG) -строителя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Затем просто зайдите в список. Если слово не пересекается с существующим словом (проверяйте каждое слово по их длине и оценка Scrabble, соответственно), затем помещайте его в очередь и проверяйте следующее слово.

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

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

Вот несколько javascript-кода, основанных на ответе nickf и на коде 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 += "" + grid[x][y].targetChar + ""; } $('#tempTable').append("" + rowStr + ""); 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(); } времени 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 += "" + grid[x][y].targetChar + ""; } $('#tempTable').append("" + rowStr + ""); 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(); } 

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

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:][:]

… и снова повторите новый кроссворд.

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

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

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

Я бы получил индекс каждой буквы, используемой каждым словом, чтобы знать возможные кресты. Тогда я бы выбрал самое большое слово и использовал его в качестве базы. Выберите следующий большой и перекрестите его. Промыть и повторить. Вероятно, это проблема NP.

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

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

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

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

Если кто-то другой воспринял такой подход, сообщите мне.

Ниже приведен пример Swift-версии генератора кроссвордов на основе кода Python от Bryan.

Просто поделитесь им, если кому-то это понадобится.

Я исправил 100% -ное решение jQuery для этой проблемы.

Демо-версия: http://www.earthfluent.com/crossword-puzzle-demo.html

Исходный код: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

objective алгоритма, который я использовал:

  1. Минимизируйте количество неиспользуемых квадратов в сетке как можно больше.
  2. Как можно больше смешанных слов.
  3. Вычислить в чрезвычайно быстрое время.

Я опишу алгоритм, который я использовал:

  1. Сгруппируйте слова вместе в соответствии с теми, которые имеют общее письмо.

  2. Из этих групп создавайте наборы новой структуры данных («блоки слов»), которая является основным словом (которое проходит через все другие слова), а затем другими словами (которые проходят через основное слово).

  3. Запустите кроссворд с самым первым из этих блоков слов в самом верхнем левом положении кроссворда.

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

  • Шаблоны проектирования: абстрактный завод по сравнению с заводским методом
  • Полезно ли использовать «goto» на языке, который поддерживает циклы и функции? Если да, то почему?
  • Почему NaN не равен NaN?
  • Буферизованный и небуферизованный IO
  • Генерация перетасованного диапазона с использованием PRNG, а не перетасовка
  • Какой смысл ООП?
  • GOTO по-прежнему считается вредным?
  • Почему бы не использовать исключения как регулярный stream контроля?
  • Понимание «случайности»
  • Синглтоны: хороший дизайн или костыль?
  • Аллен Голуб писал: «Вы никогда не должны использовать функции get / set», правильно ли он?
  • Interesting Posts

    В чем разница между командами find и findstr в Windows?

    Экранная видеозапись текущей активности Android

    Как выбрать ВСЕ УДАЛЕННЫЙ (или ВСЕ ДОБАВЛЕННЫЙ) текст (изменение дорожки) в MS Word 2016

    Пространства имен XML и атрибуты

    Периодическая текстовая печать – струйная или лазерная?

    Отправка клавиши F1 – F12 с внешней клавиатурой с отсутствующими клавишами на iPad Pro с использованием программного обеспечения эмуляции SSH

    Сокращение времени ожидания доступа к памяти в Windows (особенно для съемных носителей)?

    Запретить добавление приложений для запуска экрана при установке

    Как передать аргумент unique_ptr конструктору или функции?

    Простой пример использования и в XML-макетах Android

    Установите фокус на текстовое поле в WPF из модели просмотра (C #)

    Excel VBA: Parsed JSON Object Loop

    Как регулярные выражения работают в htaccess для перенаправления диапазона IP

    Как загрузить несколько файлов с помощью Wget из Cygwin для Windows

    ipad safari: отключить прокрутку и эффект отскока?

    Давайте будем гением компьютера.