Учитывая список слов, как бы вы могли организовать их в кроссворд?
Это не должно быть похоже на "правильную" кроссворд, которая симметрична или что-то в этом роде: в основном просто выводит начальное положение и направление для каждого слова.
Будут ли доступны Java-примеры?
Я придумал решение, которое, вероятно, не является самым эффективным, но оно работает достаточно хорошо. В основном:
Это делает рабочий, но все же довольно бедный кроссворд. Был внесен ряд изменений, которые я сделал в основной рецепт выше, чтобы придумать лучший результат.
Недавно я написал свой собственный в Python. Вы можете найти его здесь: http://bryanhelmig.com/python-crossword-puzzle-generator/. Он не создает плотные кроссворды стиля NYT, но стиль кроссвордов, которые вы можете найти в детской головоломке.
В отличие от нескольких алгоритмов, которые я обнаружил там, где реализован случайный метод грубой силы размещения слов, подобных некоторым, я попытался реализовать немного более умный подход грубой силы при размещении слов. Здесь мой процесс:
В конце концов, у вас есть подходящая головоломка с кроссвордом или головоломкой для поиска слов, так как они примерно одинаковы. Он имеет тенденцию работать довольно хорошо, но дайте мне знать, если у вас есть предложения по улучшению. Большие сетки работают экспоненциально медленнее; Линейные списки слов линейно. Большие списки слов также имеют гораздо более высокий шанс на лучшие номера размещения слов.
На самом деле я написал программу генерации кроссвордов около десяти лет назад (она была загадочной, но те же правила применимы и к нормальным кроссвордам).
У него был список слов (и связанных ключей), хранящихся в файле, отсортированном по нисходящему использованию до даты (так что слова с меньшим использованием были в верхней части файла). Шаблон, в основном битовая маска, представляющая черные и свободные квадраты, выбирался случайным образом из пула, который был предоставлен клиентом.
Затем для каждого неполного слова в головоломке (в основном найдите первый пустой квадрат и посмотрите, находится ли один справа (поперечное слово) или под ним (вниз)), поиск было сделано из файла, ищущего первое слово, которое было укомплектовано, с учетом букв уже в этом слове. Если бы не было слов, которые могли бы поместиться, вы просто отметили, что все слово было неполным и движется дальше.
В конце были бы некоторые незавершенные слова, которые компилятор должен был бы заполнить (и при желании добавить слово и ключ к файлу). Если бы они не могли придумать какие-либо идеи, они могли бы вручную отредактировать кроссворд, чтобы изменить ограничения или просто потребовать полного повторного генерации.
После того, как файл word/clue дошел до определенного размера (и это добавило 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 northern border
[0,4] PLEASE: A polite way to ask things
[0,7] OTTAWA: Canada capital
[1,2] TIBET: Dalai Lama 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))
Вычислить пересечения слов в списках слов с различными буквами используемого алфавита (это позволяет искать совпадающие слова с использованием шаблона, например Тезис Сика Камбона как используется cwc) (сложность O (WL * AL))
Шаги .3 и .4 позволяют выполнить эту задачу:
а. Пересечения слов сетки сами по себе позволяют создать "шаблон" для поиска совпадений в соответствующем списке слов доступных слов для этого слова сетки (используя буквы других пересекающихся слов с этим словом, которые уже заполнены определенным шаг алгоритма)
б. Пересечения слов в списке слов с алфавитом позволяют найти совпадающие (кандидатные) слова, которые соответствуют заданному "шаблону" (например, "А" на 1-м месте и "В" на 3-м месте и т.д.).
Таким образом, при реализации этих структур данных применяемый алгоритм был следующим:
ПРИМЕЧАНИЕ. Если сетка и база данных слов являются постоянными, предыдущие шаги можно выполнить только один раз.
Первым шагом алгоритма является случайный выбор словарного слова (сетчатое слово) и заполнение его кандидатным словом из связанного списка слов (рандомизация позволяет производить разные решения в последовательных реализациях алгоритма) (сложность O (1) или O (N))
Для каждого еще незаполненного слота слота (который имеет пересечения с уже заполненными слотами слов) вычисляет коэффициент ограничения (это может варьироваться, простое количество доступных решений на этом этапе) и сортировать пустое словослоты с помощью этого (сложность O (NlogN) или O (N))
Прокрутите пустые словарные строки, вычисленные на предыдущем шаге, и для каждого из них попробуйте несколько решений cancdidate (убедитесь, что "согласованность дуги сохраняется", т.е. сетка имеет решение после этого шага, если это слово используется ) и сортировать их в соответствии с максимальной доступностью для следующего шага (т.е. следующий шаг имеет максимально возможные решения, если это слово используется в то время в этом месте и т.д.) (сложность O (N * MaxCandidatesUsed))
/li >Заполните это слово (отметьте его как заполненное и перейдите к шагу 2)
Если не найдено ни одного слова, удовлетворяющего критериям шага .3, попробуйте вернуться к другому кандидатскому решению какого-либо предыдущего шага (критерии могут варьироваться здесь) (сложность O (N))
Если найден найденный backtrack, используйте альтернативу и необязательно reset любые уже заполненные слова, которые могут потребоваться reset (пометьте их как незаполненные снова) (сложность O (N))
Если никакого возврата нет, решение не может быть найдено (по крайней мере, с этой конфигурацией, начальное семя и т.д.)
Если все слоты заполнены, у вас есть одно решение
Этот алгоритм выполняет случайное согласованное движение дерева решений проблемы. Если в какой-то момент есть тупик, он возвращается к предыдущему node и следуют по другому маршруту. До тех пор, пока не будет найдено ни найденное решение, ни количество кандидатов на различные узлы.
Часть согласованности гарантирует, что найденное решение действительно является решением, а случайная часть позволяет создавать различные решения в разных исполнениях, а также в среднем иметь лучшую производительность.
PS. все это (и другие) были реализованы в режиме чистого JavaScript (с параллельной обработкой и WYSIWYG)
PS2. Алгоритм может быть легко распараллелен, чтобы одновременно создавать более одного (другого) решения
Надеюсь, что это поможет
Я бы сгенерировал два числа: Length и Scrabble score. Предположим, что низкий балл 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 += "<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();
}
Я играл с генератором кроссвордов, и я нашел это самым важным:
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 )
для сравнения слова с свободным пространством Я использовал i.e.:
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:][:]
... и снова повторите новый кроссворд.
Сделайте систему подсчета по легкости заполнения, и некоторые оценочные расчеты. Дайте оценку для текущего кроссворда и узкий выбор позже, добавив его в список сделанных кроссвордов, если оценка удовлетворена вашей системой подсчета очков.
После первого итерационного сеанса снова сверьтесь из списка сделанных кроссвордов, чтобы закончить задание.
При использовании большего количества параметров скорость может быть улучшена огромным фактором.
Я бы получил индекс каждой буквы, используемой каждым словом, чтобы знать возможные кресты. Тогда я бы выбрал самое большое слово и использовал его в качестве базы. Выберите следующий большой и перекрестите его. Промыть и повторить. Вероятно, это проблема NP.
Другая идея - создать генетический алгоритм, в котором показатель силы - сколько слов, которые вы можете положить в сетку.
Жесткая часть, которую я нахожу, - это когда узнать, что определенный список не может быть пересечен.
Я думал об этой проблеме. Я считаю, что для создания действительно плотного кроссворда вы не можете надеяться, что вашего ограниченного списка слов будет достаточно. Поэтому вы можете захотеть взять словарь и поместить его в структуру данных "trie". Это позволит вам легко находить слова, заполняющие пробелы слева. В trie довольно эффективно реализовать обход, который, скажем, дает вам все слова формы "c? T".
Итак, мое общее мнение: создайте какой-то подход относительно грубой силы, как описано здесь, чтобы создать крест с низкой плотностью и заполнить пробелы словарем.
Если кто-либо другой взял такой подход, пожалуйста, дайте мне знать.
Здесь - это небольшая версия генератора кроссвордов, основанная на коде Bryan python.
Просто поделитесь им, если кому-то это понадобится.