L'algoritmo per generare un cruciverba.
https://stackoverflow.com/questions/943113
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Dato un elenco di parole, come si va su, disponendoli in una griglia del cruciverba?
Non sarebbe essere come un "vero" cruciverba che è simmetrica o qualcosa di simile:praticamente appena uscita una posizione di partenza e di direzione per ogni parola.
Ci sarebbe esempi Java disponibili?
Soluzione
mi si avvicinò con una soluzione che probabilmente non è il più efficiente, ma funziona abbastanza bene. In sostanza:
- Ordina tutte le parole per lunghezza, decrescente.
- Prendere la prima parola e metterla sul tavolo.
- Prendere la parola successiva.
- una ricerca tra tutte le parole che sono già sul tavolo e vedere se ci sono eventuali incroci possibili (eventuali lettere comuni) con questa parola.
- Se c'è una posizione possibile per questa parola, ciclo attraverso tutte le parole che sono sul tavolo e controllare per vedere se la nuova parola interferisce.
- Se questa parola non si rompe la linea, poi metterlo lì e passare al punto 3, in caso contrario, continuare a cercare un posto (punto 4).
- Continuare questo ciclo fino a quando tutte le parole sono state poste o in grado di essere collocato.
Questo fa un lavoro, ma spesso piuttosto scarsa cruciverba. Ci sono stati un certo numero di modifiche che ho fatto alla ricetta di base sopra a venire con un risultato migliore.
- Alla fine di generare un cruciverba, attribuiscono un punteggio in base a quante delle parole sono stati collocati (più il migliore), quanto è grande la scheda è (più piccola è la migliore), e il rapporto tra altezza e larghezza (il più vicino a 1 il migliore). Generare un certo numero di parole crociate e quindi confrontare i loro punteggi e scegliere il migliore.
- Invece di eseguire un numero arbitrario di iterazioni, ho deciso di creare il maggior numero di parole crociate possibili in una quantità arbitraria di tempo. Se avete solo un piccolo elenco di parole, allora avrai decine di possibili cruciverba in 5 secondi. Un cruciverba più grande potrebbe essere scelto soltanto da 5-6 possibilità.
- Quando si effettua una nuova parola, invece di mettere immediatamente su di trovare una posizione accettabile, dato che posizione parola un punteggio in base a quanto si aumenta la dimensione della griglia e quanti incroci ci sono (in teoria che ci si vuole ogni parola da attraversato da 2-3 altre parole). Tenere traccia di tutte le posizioni e le loro punteggi e quindi scegliere il migliore.
Altri suggerimenti
Ho da poco scritto il mio in Python. Lo si può trovare qui: http://bryanhelmig.com/python-crossword-puzzle-generator/ . Non crea le fitte cruciverba stile NYT, ma lo stile di cruciverba si potrebbe trovare nel libro di puzzle di un bambino.
A differenza di alcuni algoritmi che ho trovato là fuori che ha implementato un metodo di forza bruta casuale di mettere parole come alcuni hanno suggerito, ho cercato di attuare un approccio leggermente più intelligente a forza bruta al posizionamento parola. Ecco il mio processo:
- Creare una griglia di qualsiasi dimensione e una lista di parole.
- Mescolate l'elenco delle parole, e quindi ordinare le parole da più lungo al più breve.
- Posizionare la prima e più lunga parola alla posizione più in alto a sinistra, 1,1 (verticale o orizzontale).
- Sposta su parola successiva, un ciclo su ogni lettera della parola ed ogni cella della griglia in cerca di una lettera all'altra partite.
- Quando viene trovata una corrispondenza, è sufficiente aggiungere quella posizione a un listino consigliato di coordinate per quella parola.
- Loop sul suggerito lista coordinare e "segnare" il posizionamento di parola in base a quanti altre parole esso attraversa. Decine di 0 indicano sia cattivo posizionamento (adiacente a parole già esistenti) o che non c'erano croci di parola.
- Torna al passaggio 4 # fino elenco di parole è esaurita. Opzionale secondo passaggio.
- Dovremmo ora hanno un cruciverba, ma la qualità può essere colpito o perdere a causa di alcuni dei collocamenti casuali. Così, abbiamo BUFFER questo cruciverba e tornare al passo # 2. Se il prossimo cruciverba ha più parole posti sulla scheda, esso sostituisce il cruciverba nel buffer. Questo è il tempo limitato (il miglior cruciverba x secondi).
Alla fine, si dispone di una discreta cruciverba o parola puzzle di ricerca, dal momento che sono circa lo stesso. Esso tende a funzionare piuttosto bene, ma fatemi sapere se avete qualche suggerimento su miglioramento. griglie più grandi funzionano in modo esponenziale più lento; elenchi di parole più grandi in modo lineare. Bigger elenchi di parole hanno anche una probabilità molto più alta al meglio i numeri di collocamento di parola.
In realtà ho scritto un programma di generazione cruciverba circa dieci anni fa (era criptico, ma le stesse regole si applicherebbe per cruciverba normali).
Si aveva una lista di parole (e indizi associati) memorizzati in un file ordinato scendendo uso fino ad oggi (in modo che le parole meno diffuse erano nella parte superiore del file). Un modello, in pratica una maschera di bit che rappresenta i quadrati bianchi e liberi, è stato scelto a caso da un pool che è stato fornito dal cliente.
Quindi, per ogni parola non completa nel puzzle (in pratica trovare la prima piazza vuota e vedere se quello a destra (di fronte-Word) o quello sottostante (down-word) è anche in bianco), una ricerca è stato fatto del file cercando la prima parola che equipaggiata, tenendo conto delle lettere già in quella parola. Se non ci fosse nessuna parola che potesse andare bene, basta segnato l'intera parola come incompleto e spostato su.
Alla fine sarebbero alcune parole incompiute che il compilatore avrebbe dovuto compilare (e aggiungere la parola e un indizio per il file se lo si desidera). Se non potevano venire con qualsiasi idee, potrebbero modificare il cruciverba manualmente per modificare i vincoli o semplicemente chiedere per un totale ri-generazione.
Una volta che il file / indizio parola si alzò per una certa dimensione (ed è stata aggiunta 50-100 indizi al giorno per questo client), c'era raramente un caso di più di due o tre fix up manuali che doveva essere fatto per ogni cruciverba.
Questo algoritmo produce il 50 densa 6x9 cruciverba freccia in 60 secondi. Esso utilizza un database di parole (con la parola + punte) e un database di bordo (con schede pre-configurato).
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
Un database parola più grande riduce considerevolmente il tempo di generazione e un qualche tipo di schede sono più difficili da riempire! tavole più grandi richiedono più tempo per essere riempito correttamente!
Esempio:
Pre-configurato 6x9 consiglio:
(# significa una punta in una cella,% significa due punte in una cella, le frecce non mostrati)
# - # # - % # - #
- - - - - - - - -
# - - - - - # - -
% - - # - # - - -
% - - - - - % - -
- - - - - - - - -
Generated 6x9 consiglio:
# 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
Consigli [riga, colonna]:
[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)
Perché non usare un approccio probabilistico casuale per iniziare. Inizia con una parola, e poi ripetutamente scegliere una parola a caso e cercare di inserirlo nel lo stato attuale del puzzle senza rompere i vincoli della dimensione ecc .. Se non si riesce, basta iniziare tutto da capo.
Sarete sorpresi di quanto spesso un approccio Monte Carlo come questo funziona.
Anche se questa è una vecchia questione, tenta una risposta sulla base di analoghe lavoro che ho fatto.
Ci sono molti approcci per la soluzione di vincolo problemi (che generallay sono in NPC complessità di classe).
Questo è legato all'ottimizzazione combinatoria e programmazione a vincoli.In questo caso i vincoli sono la geometria della griglia e il requisito che le parole sono uniche, ecc..
Randomizzazione/Ricottura approcci può anche funzionare (anche se all'interno di una corretta impostazione).
Efficiente semplicità potrebbe essere proprio il massimo della saggezza !
I requisiti erano per una più o meno completa di crossword compiler e (visual WYSIWYG) generatore.
Lasciando da parte l'editor WYSIWYG di generatore di parte, il compilatore schema era questo:
Di carico disponibili i dizionari (ordinati per lunghezza della parola, vale a dire 2,3,..,20)
Trovare il wordslots (ie griglia di parole) per l'utente-costruito in griglia (per esempio word x,y con lunghezza L, orizzontale o verticale) ( complessità O(N) )
Calcolare i punti di intersezione della griglia di parole (che devono essere compilati) ( complessità O(N^2) )
Calcolare le intersezioni delle parole nei dizionari con le varie lettere dell'alfabeto (questo permette la ricerca per parole corrispondenti utilizzando un modello ad esempio. Sik Cambon tesi utilizzato da cwc ) ( complessità O(WL*AL) )
I passaggi 3 e 4 permettono di fare questa operazione:
un.L'intersezione della griglia di parole con se stessi consentono di creare un "modello" per cercare di trovare le corrispondenze associati in dizionario di parole disponibili per questa griglia parola (usando le lettere di altre parole che si intersecano con questa parola, che sono già inseriti in una certa fase dell'algoritmo)
b.Le intersezioni delle parole in un dizionario con l'alfabeto permettono di trovare la corrispondenza (candidato) parole che corrispondono a un dato "modello" (ad esempio 'A' al 1 ° posto e " B " al 3 ° posto, ecc..)
Così, con queste strutture di dati implementato l'algoritmo utilizzato è stato qualcosa di simile a questo:
NOTA:se la griglia e il database di parole, che sono una costante passaggi precedenti può solo essere fatto una volta.
Primo passo dell'algoritmo è selezionare un vuoto wordslot (griglia parola) in modo casuale e riempirlo con un candidato parola associata dizionario (randomizzazione consente di produrre diversi solutons consecutivi di esecuzioni dell'algoritmo) ( complessità O(1) o O(N) )
Per ogni parola vuota slot (che sono le intersezioni con già riempito wordslots), calcolare un vincolo di rapporto (questo può variare, sth semplice è il numero di soluzioni al passo) e ordinare il vuoto wordslots da questo rapporto ( complessità O(NlogN) o O(N) )
Loop attraverso il vuoto wordslots calcolata al passo precedente e per ciascuno provare un certo numero di cancdidate soluzioni (facendo attenzione che "arc-consistenza è mantenuto", vale a dire la griglia ha una soluzione dopo questo passaggio se questa parola è usata) e li ordina secondo la massima disponibilità per il passo successivo (cioè il prossimo passo, ha un massimo di possibili soluzioni se questa parola è usata in quel momento, in quel luogo, ecc..) ( complessità O(N*MaxCandidatesUsed) )
Riempire quella parola (contrassegnare come pieno e andare al passaggio 2)
Se non parola che soddisfa i criteri di passaggio .3 tenta di tornare indietro a un altro candidato soluzione di qualche passo precedente (criteri possono variare qui) ( complessità O(N) )
Se backtrack trovato, utilizzare l'alternativa e, facoltativamente, reset già riempito di parole che potrebbe essere necessario reimpostare (contrassegnare come vacanti di nuovo) ( complessità O(N) )
Se non backtrack trovato, nessuna soluzione può essere trovata (almeno con questa configurazione iniziale di semi ecc..)
Altrimenti, se tutti wordlots sono pieni avete una soluzione
Questo algoritmo non casuale coerente piedi dell'albero delle soluzioni del problema.Se ad un certo punto c'è un vicolo cieco, si fa una marcia indietro per un nodo precedente e seguire un altro percorso.Fino a risultare una soluzione o il numero dei candidati per i vari nodi sono esaurite.
La consistenza parte fa in modo che una soluzione è una soluzione e la parte casuale consente di produrre soluzioni diverse, in diverse esecuzioni e anche i media hanno prestazioni migliori.
PS.tutto questo (e altri) sono stati implementati in puro JavaScript (con l'elaborazione parallela e WYSIWYG) capacità
PS2.L'algoritmo può essere facilmente eseguito in parallelo al fine di produrre più di un (diverso) soluzione allo stesso tempo
Spero che questo aiuta
Ecco il codice JavaScript in base alla risposta del nickf e il codice python di Bryan. Basta postarlo nel caso in cui qualcun altro ne ha bisogno in 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();
}
Mi piacerebbe generare due numeri: Lunghezza e punteggio Scarabeo. Si supponga che un basso punteggio di Scrabble significa che è più facile unirsi a punteggi bassi (= un sacco di lettere comuni). Ordinare l'elenco per la lunghezza discendente e ascendente Scarabeo punteggio.
Avanti, basta andare in fondo alla lista. Se la parola non attraversa con una parola esistente (controllo contro ogni parola per la loro lunghezza e il punteggio Scrabble, rispettivamente), poi metterlo in coda, e verificare la parola successiva.
sciacquare e ripetere, e questo dovrebbe generare un cruciverba.
Naturalmente, sono abbastanza sicuro che questo è O (n!) E non è garantito per completare il cruciverba per voi, ma forse qualcuno può migliorarlo.
Ho riflettuto su questo problema. La mia sensazione è che per creare un cruciverba veramente denso, non si può sperare che il vostro elenco di parole limitata sta per essere sufficiente. Pertanto, si potrebbe desiderare di prendere un dizionario e metterlo in una struttura dati "trie". Questo vi permetterà di trovare facilmente le parole che riempiono il sinistro su spazi. In un trie, è abbastanza efficace per attuare un attraversamento che, per esempio, ti dà tutte le parole della forma "c? T".
Quindi, il mio pensiero generale è: creare una sorta di approccio forza relativamente bruta come alcuni descritto qui per creare una croce a bassa densità, e riempire gli spazi vuoti con le parole del dizionario
.Se qualcun altro ha preso questo approccio, per favore fatemelo sapere.
stavo giocando attorno al motore generatore di parole crociate, e ho trovato questo il più importante:
0.!/usr/bin/python
-
a.
allwords.sort(key=len, reverse=True)b. fare qualche elemento / oggetto come cursore che camminare matrice per un facile orientamento a meno che non si desidera iterare per scelta casuale in seguito.
-
il primo, raccogliere prima coppia e metterli di fronte e giù da 0,0; memorizzare il primo come il nostro attuale cruciverba 'leader'.
-
sposta il cursore per ordine diagonale o casuale con maggiore probabilità diagonale di cella vuota successiva
-
iterate sulle parole come e l'uso gratuito di lunghezza spazio per definire massima lunghezza della parola:
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 ) -
per confrontare parola contro lo spazio libero che ho usato vale a dire:
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 -
dopo ogni parola con successo usata, cambio di direzione. Loop mentre tutte le cellule sono riempite o si corre fuori di parole o dal limite di iterazioni poi:
# CHANGE ALL WORDS LIST
inexOf1stWord = allwords.index( leading_w )
allwords = allwords[:inexOf1stWord+1][:] + allwords[inexOf1stWord+1:][:]
... e iterare nuovo nuovo cruciverba.
-
Rendere il sistema di punteggio per la facilità di riempimento, e alcune Calcoli di stima. Dare punteggio per il cruciverba corrente e stretta scelta poi da aggiungere in elenco di parole crociate fatte se il punteggio è soddisfatta dal sistema di punteggio.
-
Dopo la prima iterazione sessione iterate di nuovo dalla lista delle parole crociate fatte per finire il lavoro.
Utilizzando più velocità parametri può essere migliorata di un fattore enorme.
Vorrei avere un indice di ogni lettera utilizzata da ogni parola di conoscere i possibili incroci. Poi vorrei scegliere la parola più grande e usarlo come base. Selezionare il prossimo grande e attraversarlo. Risciacqua e ripeti. E 'probabilmente un problema NP.
Un'altra idea è la creazione di un algoritmo genetico in cui la metrica forza è quante parole si può mettere nella griglia.
La parte difficile che trovo è quando a conoscere una certa lista non può assolutamente essere attraversata.
Ho codificato una soluzione jQuery 100% a questo problema.
Demo Esempio: http://www.earthfluent.com/crossword-puzzle- demo.html
Codice Sorgente: https://github.com/HoldOffHunger/jquery-crossword- puzzle-generatore
L'intento dell'algoritmo che ho usato:
- Minimizzare il numero dei quadrati inutilizzabili nella griglia più possibile.
- avere come molte parole tra misti possibili.
- Compute in un tempo estremamente veloce.
mi limiterò a descrivere l'algoritmo che ho usato:
-
Gruppo insieme le parole in base a quelli che condividono una lettera comune.
-
Da questi gruppi, costruire set di una nuova struttura di dati ( "blocchi di parole"), che è una parola primaria (che attraversa tutte le altre parole) e poi le altre parole (che attraversano la parola primario) .
-
Inizia il cruciverba con il primo di questi blocchi di parole in posizione molto in alto a sinistra del cruciverba.
-
Per il resto dei blocchi di parole, a partire dalla posizione più in basso a destra del cruciverba, muoversi verso l'alto e verso sinistra, fino a quando non ci sono slot più a disposizione per riempire. Se ci sono più colonne vuote verso l'alto rispetto verso sinistra, muoversi verso l'alto e viceversa.
