Algoritmo para gerar palavras cruzadas

Dada uma lista de palavras, como você as organizaria em uma grade de palavras cruzadas?

Não teria que ser como um jogo de palavras cruzadas "apropriado" que seja simétrico ou algo assim: basicamente apenas produza uma posição inicial e direção para cada palavra.

Eu vim com uma solução que provavelmente não é a mais eficiente, mas funciona bem o suficiente. Basicamente:

1. Classifique todas as palavras por comprimento, descendente.
2. Pegue a primeira palavra e coloque-a no quadro.
3. Pegue a próxima palavra.
4. Pesquise todas as palavras que já estão no quadro e veja se existem interseções possíveis (letras comuns) com essa palavra.
5. Se houver um local possível para essa palavra, percorra todas as palavras que estão no quadro e verifique se a nova palavra interfere.
6. Se essa palavra não quebrar o quadro, coloque-o ali e vá para a etapa 3; caso contrário, continue procurando por uma área (etapa 4).
7. Continue esse loop até que todas as palavras sejam colocadas ou impossibilitadas de serem colocadas.

Isso faz com que as palavras cruzadas funcionem, mas muitas vezes sejam muito pobres. Houve várias alterações que fiz na receita básica acima para obter um melhor resultado.

• Ao final da geração de palavras cruzadas, faça uma pontuação com base em quantas palavras foram colocadas (quanto mais melhor), qual o tamanho do quadro (quanto menor, melhor) e a proporção entre altura e largura (quanto mais próximo 1 para melhor). Gere várias palavras cruzadas, compare suas pontuações e escolha a melhor.
  • Em vez de executar um número arbitrário de iterações, decidi criar o maior número possível de palavras cruzadas em um período arbitrário. Se você tiver apenas uma pequena lista de palavras, obterá dezenas de palavras cruzadas possíveis em 5 segundos. Palavras-chave maiores só podem ser escolhidas de 5 a 6 possibilidades.
• Ao colocar uma nova palavra, em vez de colocá-la imediatamente após encontrar um local aceitável, atribua uma pontuação a esse local com base em quanto ela aumenta o tamanho da grade e quantas interseções existem (o ideal é que você queira que cada palavra seja cruzado por 2-3 outras palavras). Acompanhe todas as posições e suas pontuações e escolha a melhor.

Eu escrevi recentemente recentemente em Python. Você pode encontrá-lo aqui: http://bryanhelmig.com/python-crossword-puzzle-generator/ . Não cria as palavras cruzadas densas no estilo NYT, mas o estilo das palavras cruzadas que você pode encontrar no livro de quebra-cabeças de uma criança.

Ao contrário de alguns algoritmos que descobri que implementavam um método aleatório de força bruta para colocar palavras como algumas sugeriram, tentei implementar uma abordagem de força bruta um pouco mais inteligente no posicionamento das palavras. Aqui está o meu processo:

1. Crie uma grade de qualquer tamanho e uma lista de palavras.
2. Embaralhe a lista de palavras e classifique as palavras da maior para a menor.
3. Coloque a primeira e a palavra mais longa na posição superior esquerda, 1,1 (vertical ou horizontal).
4. Vá para a próxima palavra, faça um loop sobre cada letra da palavra e cada célula da grade, procurando correspondências de letra a letra.
5. Quando uma correspondência for encontrada, basta adicionar essa posição a uma lista de coordenadas sugerida para essa palavra.
6. Passe o mouse sobre a lista de coordenadas sugerida e "marque" o posicionamento da palavra com base em quantas outras palavras ela cruza. Pontuações 0 indicam posicionamento incorreto (adjacente às palavras existentes) ou que não houve cruzamentos de palavras.
7. Volte para a etapa 4 até que a lista de palavras esteja esgotada. Segunda passagem opcional.
8. Agora devemos ter palavras cruzadas, mas a qualidade pode ser um sucesso ou um erro devido a algumas veiculações aleatórias. Então, armazenamos em buffer essas palavras cruzadas e voltamos à etapa 2. Se as próximas palavras cruzadas tiverem mais palavras colocadas no quadro, as palavras cruzadas serão substituídas no buffer. O tempo é limitado (encontre as melhores palavras cruzadas em x segundos).

No final, você tem um jogo decente de palavras cruzadas ou de busca de palavras, já que eles são iguais. Ele tende a funcionar bastante bem, mas deixe-me saber se você tem alguma sugestão de melhoria. Grades maiores são exponencialmente mais lentas; listas de palavras maiores linearmente. Listas de palavras maiores também têm uma chance muito maior de obter números melhores de colocação de palavras.

Na verdade, escrevi um programa de geração de palavras cruzadas há cerca de dez anos (era enigmático, mas as mesmas regras se aplicavam a palavras cruzadas normais).

Ele tinha uma lista de palavras (e dicas associadas) armazenadas em um arquivo classificado por uso decrescente até a data (para que as palavras menos usadas estivessem na parte superior do arquivo). Um modelo, basicamente uma máscara de bits representando os quadrados pretos e livres, foi escolhido aleatoriamente em um pool que foi fornecido pelo cliente.

Então, para cada palavra não completa no quebra-cabeça (encontre o primeiro quadrado em branco e veja se o da direita (em toda a palavra) ou o abaixo (em baixo da palavra) também está em branco), foi feita uma pesquisa de o arquivo procurando a primeira palavra que couber, levando em conta as letras que já estão nessa palavra. Se não houvesse uma palavra adequada, basta marcar a palavra inteira como incompleta e seguir em frente.

No final, haveria algumas palavras incompletas que o compilador teria que preencher (e adicionar a palavra e uma pista ao arquivo, se desejado). Se eles não pudessem ter nenhuma idéia, eles poderiam editar as palavras cruzadas manualmente para alterar as restrições ou apenas solicitar uma re-geração total.

Depois que o arquivo de palavras / pistas chegava a um determinado tamanho (e adicionava de 50 a 100 pistas por dia para esse cliente), raramente havia um caso de mais de duas ou três correções manuais que precisavam ser feitas para cada palavra cruzada. .

Esse algoritmo cria 50 palavras cruzadas de seta 6x9 densas em 60 segundos. Ele usa um banco de dados de palavras (com palavras + dicas) e um banco de dados de placas (com placas pré-configuradas).

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

Um banco de dados de palavras maior diminui consideravelmente o tempo de geração e é mais difícil preencher algum tipo de placa! Placas maiores requerem mais tempo para serem preenchidas corretamente!

Exemplo:

Placa 6x9 pré-configurada:

(# significa uma dica em uma célula,% significa duas dicas em uma célula, setas não mostradas)

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

Placa 6x9 gerada:

# 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 

Dicas [linha, coluna]:

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

Embora essa seja uma pergunta antiga, tentarei uma resposta com base em trabalho semelhante que fiz.

Existem muitas abordagens para resolver problemas de restrição (que geralmente estão na classe de complexidade do NPC).

Isso está relacionado à otimização combinatória e à programação de restrições. Nesse caso, as restrições são a geometria da grade e a exigência de que as palavras sejam únicas etc.

As abordagens de randomização / recozimento também podem funcionar (embora dentro da configuração adequada).

Simplicidade eficiente pode ser apenas a sabedoria suprema!

Os requisitos eram para um compilador de palavras cruzadas mais ou menos completo e um construtor (visual WYSIWYG).

Deixando de lado a parte do construtor WYSIWYG, o esboço do compilador era o seguinte:

1. Carregue as listas de palavras disponíveis (classificadas por tamanho da palavra, ou seja, 2,3, .., 20)

2. Encontre os lotes de palavras (ou seja, palavras de grade) na grade criada pelo usuário (por exemplo, palavra em x, y com comprimento L, horizontal ou vertical) (complexidade O (N))

3. Calcular os pontos de interseção das palavras da grade (que precisam ser preenchidas) (complexidade O (N ^ 2))

4. Calcule as interseções das palavras nas listas de palavras com as várias letras do alfabeto usadas (isso permite procurar palavras correspondentes usando um modelo, por exemplo, tese de Sik Cambon conforme usada pelo cwc ) (complexidade O (WL * AL))

As etapas .3 e .4 permitem executar esta tarefa:

uma. As interseções das palavras da grade consigo permitem criar um "modelo" para tentar encontrar correspondências na lista de palavras associada de palavras disponíveis para essa palavra da grade (usando as letras de outras palavras que se cruzam com essa palavra que já estão preenchidas em um determinado etapa do algoritmo)

b. As interseções das palavras em uma lista de palavras com o alfabeto permitem encontrar palavras (candidatas) correspondentes que correspondam a um determinado "modelo" (por exemplo, 'A' em 1º lugar e 'B' em 3º lugar etc.)

Portanto, com essas estruturas de dados implementadas, o algoritmo usado ficou assim:

NOTA: se a grade e o banco de dados de palavras forem constantes, as etapas anteriores podem ser feitas apenas uma vez.

1. A primeira etapa do algoritmo é selecionar um lote de palavras vazio (palavra da grade) aleatoriamente e preenchê-lo com uma palavra candidata da lista de palavras associada (a randomização permite produzir diferentes soluções em execuções consecutivas do algoritmo) (complexidade O (1) ou O ( N))

2. Para cada slot de palavras ainda vazio (que possui interseções com lotes de palavras já preenchidos), calcule uma taxa de restrição (isso pode variar, simples é o número de soluções disponíveis nessa etapa) e classifique os lotes de palavras vazios por essa taxa (complexidade O (NlogN ) ou O (N))

3. Percorra os lotes de palavras vazios calculados na etapa anterior e, para cada um, tente várias soluções canceladas (certificando-se de que "a consistência do arco seja mantida", ou seja, a grade tenha uma solução após esta etapa, se essa palavra for usada) e classifique-as de acordo com disponibilidade máxima para o próximo passo (ou seja, o próximo passo tem o máximo de soluções possíveis se essa palavra for usada naquele momento naquele local, etc.) (complexidade O (N * MaxCandidatesUsed))

4. Preencha essa palavra (marque-a como preenchida e vá para a etapa 2)

5. Se nenhuma palavra encontrada satisfizer os critérios da etapa .3, tente voltar para outra solução candidata da etapa anterior (os critérios podem variar aqui) (complexidade O (N))

6. Se for encontrado um retorno, use a alternativa e redefina opcionalmente as palavras já preenchidas que possam precisar ser redefinidas (marque-as como preenchidas novamente) (complexidade O (N))

7. Se nenhum retorno for encontrado, a solução no poderá ser encontrada (pelo menos com esta configuração, semente inicial etc.)

8. Caso contrário, quando todos os lotes de palavras forem preenchidos, você terá uma solução

Esse algoritmo faz uma caminhada aleatória consistente da árvore de soluções do problema. Se, em algum momento, houver um beco sem saída, ele retornará a um nó anterior e seguirá outra rota. Até que uma solução encontrada ou o número de candidatos para os vários nós esteja esgotado.

A parte de consistência garante que uma solução encontrada seja realmente uma solução e a parte aleatória permite produzir soluções diferentes em diferentes execuções e, em média, também ter melhor desempenho.

PS. tudo isso (e outros) foram implementados em JavaScript puro (com processamento paralelo e capacidade WYSIWYG)

PS2. O algoritmo pode ser facilmente paralelizado para produzir mais de uma solução (diferente) ao mesmo tempo

Espero que isto ajude

Por que não usar apenas uma abordagem probabilística aleatória para começar. Comece com uma palavra e, em seguida, escolha repetidamente uma palavra aleatória e tente encaixá-la no estado atual do quebra-cabeça sem quebrar as restrições de tamanho, etc. Se você falhar, comece tudo de novo.

Você ficará surpreso com a frequência com que uma abordagem de Monte Carlo como essa funciona.

Aqui está um código JavaScript baseado na resposta do nickf e no código Python do Bryan. Apenas publicá-lo no caso de alguém precisar dele em 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();
}

Eu geraria dois números: comprimento e pontuação de Scrabble. Suponha que uma pontuação baixa no Scrabble signifique que é mais fácil participar (pontuações baixas = muitas letras comuns). Classifique a lista por comprimento descendente e pontuação Scrabble ascendente.

Em seguida, basta descer a lista. Se a palavra não cruzar com uma palavra existente (verifique cada palavra pelo tamanho e pontuação do Scrabble, respectivamente), coloque-a na fila e verifique a próxima palavra.

Enxágue e repita, e isso deve gerar palavras cruzadas.

Claro, tenho certeza de que esse é O (n!) E não é garantido que você complete as palavras cruzadas para você, mas talvez alguém possa melhorá-lo.

Eu estive pensando sobre este problema. Meu senso é que, para criar palavras cruzadas verdadeiramente densas, você não pode esperar que sua lista limitada de palavras seja suficiente. Portanto, convém pegar um dicionário e colocá-lo em uma estrutura de dados "trie". Isso permitirá que você encontre facilmente palavras que preenchem os espaços restantes à esquerda. Em um experimento, é bastante eficiente implementar uma travessia que, digamos, fornece todas as palavras da forma "c? T".

Portanto, meu pensamento geral é: crie algum tipo de abordagem de força relativamente bruta, conforme descrito aqui para criar uma cruz de baixa densidade e preencha os espaços em branco com palavras do dicionário.

Se alguém tiver adotado essa abordagem, entre em contato.

Eu estava brincando com o mecanismo gerador de palavras cruzadas e achei isso o mais importante:

0!/usr/bin/python

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

   b. faça algum item / objeto como o cursor, que percorrerá a matriz para facilitar a orientação, a menos que você queira iterar por escolha aleatória mais tarde.

2. o primeiro, pegue o primeiro par e coloque-os em frente e abaixo de 0,0; armazene o primeiro como nosso atual 'líder' de palavras cruzadas.

3. mova o cursor por ordem diagonal ou aleatória, com maior probabilidade diagonal para a próxima célula vazia

4. itere sobre as palavras like e use o espaço livre para definir o comprimento máximo da palavra: 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. para comparar a palavra com o espaço livre, usei:

   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. após cada palavra usada com sucesso, mude de direção. Faça um loop enquanto todas as células estiverem preenchidas OU você ficará sem palavras OU pelo limite de iterações:

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

... e iterar novamente novas palavras cruzadas.

7. Faça o sistema de pontuação pela facilidade de preenchimento e alguns cálculos de estimativa. Dê pontuação para as palavras cruzadas atuais e restrinja a escolha posterior, acrescentando-a à lista de palavras cruzadas feitas, se a pontuação for atendida pelo seu sistema de pontuação.

8. Após a primeira sessão de iteração, itere novamente da lista de palavras cruzadas criadas para concluir o trabalho.

Ao usar mais parâmetros, a velocidade pode ser melhorada por um fator enorme.

Eu obteria um índice de cada letra usada por cada palavra para saber possíveis cruzamentos. Então eu escolheria a palavra maior e a usaria como base. Selecione o próximo grande e cruze-o. Enxague e repita. Provavelmente é um problema de NP.

Outra idéia é a criação de um algoritmo genético em que a métrica de força é quantas palavras você pode colocar na grade.

A parte difícil que acho é quando saber que uma determinada lista não pode ser atravessada.

Eu codifiquei uma solução JavaScript / jQuery para esse problema:

Exemplo de demonstração: http://www.earthfluent.com/crossword-puzzle-demo.html

Código fonte: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

A intenção do algoritmo que usei:

1. Minimize o número de quadrados inutilizáveis ​​na grade o máximo possível.
2. Tenha o máximo de palavras possíveis.
3. Calcule em um tempo extremamente rápido.

Vou descrever o algoritmo que usei:

1. Agrupe as palavras de acordo com as que compartilham uma carta comum.

2. A partir desses grupos, crie conjuntos de uma nova estrutura de dados ("blocos de palavras"), que é uma palavra principal (que percorre todas as outras palavras) e, em seguida, as outras palavras (que percorrem a palavra principal).

3. Comece o jogo de palavras cruzadas com o primeiro desses blocos de palavras na posição superior esquerda do jogo de palavras cruzadas.

4. Para o restante dos blocos de palavras, iniciando na posição mais à direita da parte inferior das palavras cruzadas, mova-se para cima e para a esquerda, até que não haja mais espaços disponíveis para preencher. Se houver mais colunas vazias para cima do que para a esquerda, mova-se para cima e vice-versa.

Este aparece como um projeto no curso AI CS50 de Harvard. A idéia é formular o problema de geração de palavras cruzadas como um problema de satisfação de restrições e resolvê-lo com retorno com diferentes heurísticas para reduzir o espaço de pesquisa.

Para começar, precisamos de dois arquivos de entrada:

1. A estrutura das palavras cruzadas (que se parece com a seguinte, por exemplo, onde o '#' representa os caracteres a não serem preenchidos e '_' representa os caracteres a serem preenchidos)

`

###_####_#
____####_#
_##_#_____
_##_#_##_#
______####
#_###_####
#_##______
#_###_##_#
_____###_#
#_######_#
##_______#    

`

2. Um vocabulário de entrada (lista de palavras / dicionário) a partir do qual as palavras candidatas serão escolhidas (como a mostrada a seguir).

   a abandon ability able abortion about above abroad absence absolute absolutely ...

Agora o CSP está definido e deve ser resolvido da seguinte maneira:

1. As variáveis ​​são definidas para ter valores (ou seja, seus domínios) da lista de palavras (vocabulário) fornecida como entrada.
2. Cada variável é representada por uma tupla de 3: (grid_coordinate, direction, length) onde a coordenada representa o início da palavra correspondente, a direção pode ser horizontal ou vertical e o comprimento é definido como o comprimento da palavra em que a variável será atribuído a.
3. As restrições são definidas pela entrada de estrutura fornecida: por exemplo, se uma variável horizontal e vertical tiver um caractere comum, ela será representada como uma restrição de sobreposição (arco).
4. Agora, a consistência do nó e os algoritmos de consistência do arco AC3 podem ser usados ​​para reduzir os domínios.
5. Em seguida, retorne para obter uma solução (se houver) para o CSP com MRV (valor mínimo restante), grau etc. heurísticas podem ser usadas para selecionar a próxima variável não atribuída e heurísticas como LCV (menor valor restritivo) podem ser usadas para domínio- para tornar o algoritmo de pesquisa mais rápido.

A seguir, é mostrada a saída obtida usando uma implementação do algoritmo de solução 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█

`

A animação a seguir mostra as etapas de retrocesso:

Aqui está outro com uma lista de palavras em idioma bengali (bengali):