Algorithmus zum Erzeugen eines Kreuzworträtsels

Wie würden Sie eine gegebene Wörterliste in ein Kreuzworträtselgitter einordnen?

Es muss nicht wie ein “richtiges” Kreuzworträtsel sein, das symmetrisch oder ähnlich ist: Im Grunde geben Sie nur eine Ausgangsposition und eine Richtung für jedes Wort aus.

Gibt es Java-Beispiele?

Ich habe eine Lösung gefunden, die wahrscheinlich nicht die effizienteste ist, aber es funktioniert gut genug. Grundsätzlich gilt:

  1. Sortiere alle Wörter nach Länge, absteigend.
  2. Nimm das erste Wort und lege es auf die Tafel.
  3. Nimm das nächste Wort.
  4. Durchsuche alle Wörter, die sich bereits auf der Tafel befinden, und überprüfe, ob es mögliche Überschneidungen (irgendwelche gewöhnlichen Buchstaben) mit diesem Wort gibt.
  5. Wenn es einen möglichen Ort für dieses Wort gibt, durchlaufen Sie alle Wörter auf der Tafel und überprüfen Sie, ob das neue Wort interferiert.
  6. Wenn dieses Wort die Tafel nicht durchbricht, lege es dort ab und gehe zu Schritt 3, andernfalls suche weiter nach einem Ort (Schritt 4).
  7. Setzen Sie diese Schleife fort, bis alle Wörter entweder platziert sind oder nicht platziert werden können.

Dies macht ein funktionierendes, aber oft recht armes Kreuzworträtsel. Es gab eine Reihe von Änderungen, die ich an dem obigen Basisrezept vorgenommen habe, um ein besseres Ergebnis zu erzielen.

  • Am Ende der Erstellung eines Kreuzworträtsels, geben Sie eine Punktzahl basierend auf wie viele der Wörter platziert wurden (je mehr, desto besser), wie groß das Brett ist (je kleiner, desto besser), und das Verhältnis zwischen Höhe und Breite (je näher zu 1 desto besser). Erzeugen Sie eine Anzahl von Kreuzworträtseln und vergleichen Sie dann ihre Punkte und wählen Sie das beste.
    • Anstatt eine beliebige Anzahl von Iterationen auszuführen, habe ich beschlossen, so viele Kreuzworträtsel wie möglich in beliebiger Zeit zu erstellen. Wenn Sie nur eine kleine Wortliste haben, erhalten Sie Dutzende möglicher Kreuzworträtsel in 5 Sekunden. Ein größeres Kreuzworträtsel kann nur aus 5-6 Möglichkeiten ausgewählt werden.
  • Wenn Sie ein neues Wort platzieren, anstatt es sofort auf die Suche nach einem akzeptablen Ort zu platzieren, geben Sie diesem Wortort eine Punktzahl basierend auf der Größe des Gitters und der Anzahl der Schnittpunkte (im Idealfall sollten Sie jedes Wort haben) gekreuzt von 2-3 anderen Wörtern). Verfolgen Sie alle Positionen und ihre Ergebnisse und wählen Sie dann die beste aus.

Ich habe gerade meine eigene in Python geschrieben. Sie können es hier finden: http://bryanhelmig.com/python-crossword-puzzle-generator/ . Es erstellt nicht die dichten NYT-Stil Kreuzworträtsel, aber die Art von Kreuzworträtseln, die Sie in einem Puzzlebuch eines Kindes finden könnten.

Im Gegensatz zu ein paar Algorithmen, die ich dort herausfand, die eine zufällige Brute-Force-Methode der Platzierung von Wörtern wie einige vorgeschlagen haben, habe ich versucht, eine etwas intelligentere Brute-Force-Ansatz bei der Wort-Platzierung zu implementieren. Hier ist mein process:

  1. Erstellen Sie ein Raster beliebiger Größe und eine Liste von Wörtern.
  2. Mischen Sie die Wortliste, und sortieren Sie die Wörter dann am längsten nach Kürzesten.
  3. Platziere das erste und längste Wort an der oberen linken Position, 1,1 (vertikal oder horizontal).
  4. Gehen Sie zum nächsten Wort über, und durchlaufen Sie jeden Buchstaben des Worts und jede Zelle im Gitter, um Buchstaben zu Buchstaben zu finden.
  5. Wenn eine Übereinstimmung gefunden wird, fügen Sie diese Position einfach zu einer vorgeschlagenen Koordinatenliste für dieses Wort hinzu.
  6. Überstreichen Sie die vorgeschlagene Koordinatenliste und “bewerten” Sie die Wortplatzierung anhand der Anzahl der Wörter, die sie kreuzt. Werte von 0 zeigen entweder eine schlechte Platzierung an (neben vorhandenen Wörtern) oder dass es keine Wortkreuze gab.
  7. Zurück zu Schritt # 4, bis die Wortliste erschöpft ist. Optionaler zweiter Durchgang
  8. Wir sollten jetzt ein Kreuzworträtsel haben, aber die Qualität kann aufgrund einiger zufälliger Placements getroffen werden. Also puffern wir dieses Kreuzworwort und gehen zurück zu Schritt 2. Wenn das nächste Kreuzworträtsel mehr Wörter auf der Tafel hat, ersetzt es das Kreuzworträtsel im Puffer. Dies ist zeitlich begrenzt (finde das beste Kreuzworträtsel in x Sekunden).

Am Ende haben Sie ein anständiges Kreuzworträtsel oder Wortsuchrätsel, da sie ungefähr gleich sind. Es läuft eher gut, aber lassen Sie es mich wissen, wenn Sie Verbesserungsvorschläge haben. Größere Raster laufen exponentiell langsamer; größeres Wort listet linear auf. Größere Wortlisten haben auch eine viel größere Chance auf bessere Wortplatzierungszahlen.

Ich habe vor etwa zehn Jahren ein Kreuzworträtsel-Programm geschrieben (es war kryptisch, aber die gleichen Regeln würden für normale Kreuzworträtsel gelten).

Es hatte eine Liste von Wörtern (und zugehörigen Hinweisen), die in einer Datei gespeichert waren, sortiert nach absteigender Nutzung bis Datum (so dass weniger benutzte Wörter an der Spitze der Datei standen). Eine Vorlage, im Grunde eine Bitmaske, die die schwarzen und freien Quadrate darstellt, wurde zufällig aus einem Pool ausgewählt, der vom Client bereitgestellt wurde.

Dann, für jedes nicht abgeschlossene Wort im Puzzle (im Grunde finden Sie das erste leere Quadrat und sehen, ob die eine nach rechts (über das Wort) oder die darunter (Wort nach unten) ist auch leer), wurde eine Suche durchgeführt die Datei, die nach dem ersten passenden Wort sucht, wobei die bereits in diesem Wort vorhandenen Buchstaben berücksichtigt werden. Wenn es kein passendes Wort gab, markierte man das ganze Wort als unvollständig und ging weiter.

Am Ende wären einige unvollständige Wörter, die der Compiler füllen müsste (und fügen Sie das Wort und einen Hinweis auf die Datei, falls gewünscht). Wenn sie keine Ideen hätten, könnten sie das Kreuzworträtsel manuell bearbeiten, um Einschränkungen zu ändern, oder einfach nach einer vollständigen Neugenerierung fragen.

Sobald die Wort- / Hinweisdatei eine bestimmte Größe erreicht hatte (und 50-100 Hinweise pro Tag für diesen Client hinzufügte), gab es selten einen Fall von mehr als zwei oder drei manuellen Korrekturen, die für jedes Kreuzworträtsel durchgeführt werden mussten .

Dieser Algorithmus erstellt 50 dichte 6×9 Pfeilkreuzworträtsel in 60 Sekunden. Es verwendet eine Wortdatenbank (mit Wort + Tipps) und eine Board-database (mit vorkonfigurierten Boards).

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 

Eine größere Wortdatenbank verringert die Generationszeit beträchtlich und einige Boards sind schwerer zu füllen! Größere Bretter benötigen mehr Zeit, um richtig gefüllt zu werden!


Beispiel:

Vorkonfiguriertes 6×9 Board:

(# bedeutet eine Spitze in einer Zelle,% bedeutet zwei Spitzen in einer Zelle, Pfeile nicht gezeigt)

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

Generierte 6×9-Karte:

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

Tipps [Zeile, Spalte]:

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

Warum nicht einfach einen zufälligen probabilistischen Ansatz verwenden? Beginnen Sie mit einem Wort und wählen Sie dann immer wieder ein zufälliges Wort und versuchen Sie, es in den aktuellen Zustand des Puzzles zu passen, ohne die Beschränkungen bezüglich der Größe usw. zu brechen. Wenn Sie scheitern, fangen Sie einfach von vorne an.

Sie werden überrascht sein, wie oft ein solcher Monte-Carlo-Ansatz funktioniert.

Obwohl dies eine ältere Frage ist, werde ich eine Antwort versuchen, die auf ähnlichen Arbeiten basiert, die ich gemacht habe.

Es gibt viele Ansätze zum Lösen von Abhängigkeitsproblemen (welche in der NPC-Komplexitätsklasse liegen).

Dies steht im Zusammenhang mit kombinatorischer Optimierung und Constraint-Programmierung. In diesem Fall sind die Einschränkungen die Geometrie des Rasters und die Anforderung, dass Wörter eindeutig usw. sind.

Randomisierungs- / Annealing-Ansätze können ebenfalls funktionieren (wenn auch in der richtigen Einstellung).

Effiziente Einfachheit könnte nur die ultimative Weisheit sein!

Die Anforderungen waren für einen mehr oder weniger vollständigen Kreuzworträtsel-Compiler und (visuellen WYSIWYG) Builder.

Abgesehen von dem WYSIWYG-Builder-Teil war der Compiler-Umriss dies:

  1. Laden Sie die verfügbaren Wortlisten (sortiert nach Wortlänge, zB 2,3, .., 20)

  2. Finde die Wortslots (dh Gitterwörter) auf dem vom Benutzer konstruierten Gitter (z. B. Wort bei x, y mit Länge L, horizontal oder vertikal) (Komplexität O (N))

  3. Berechnen Sie die Schnittpunkte der Rasterwörter (die ausgefüllt werden müssen) (Komplexität O (N ^ 2))

  4. Berechnen Sie die Schnittpunkte der Wörter in den Wortlisten mit den verschiedenen Buchstaben des verwendeten Alphabets (dies ermöglicht die Suche nach passenden Wörtern unter Verwendung einer Vorlage, z. B. Sik Cambon These wie von cwc verwendet ) (Komplexität O (WL * AL))

Die Schritte .3 und .4 ermöglichen diese Aufgabe:

ein. Die Schnittpunkte der Gitterwörter mit sich selbst ermöglichen es, eine “Vorlage” zu erstellen, um Übereinstimmungen in der zugehörigen Wortliste von verfügbaren Wörtern für dieses Gitterwort zu finden (indem die Buchstaben anderer sich schneidender Wörter mit diesem Wort verwendet werden, die bereits bei einem bestimmten Wort gefüllt sind) Schritt des Algorithmus)

b. Die Überschneidungen der Wörter in einer Wortliste mit dem Alphabet ermöglichen es, übereinstimmende (Kandidaten-) Wörter zu finden, die mit einer gegebenen “Vorlage” übereinstimmen (z. B. “A” an erster Stelle und “B” an dritter Stelle usw.).

Mit diesen implementierten Datenstrukturen war der verwendete Algorithmus also so:

HINWEIS: Wenn das Raster und die Wortdatenbank konstant sind, können die vorherigen Schritte nur einmal ausgeführt werden.

  1. Der erste Schritt des Algorithmus ist die zufällige Auswahl eines leeren Wortschlitzes (Gitterwort) und das Füllen mit einem Kandidatenwort aus der zugehörigen Wortliste (Randomisierung ermöglicht die Erzeugung verschiedener Lösungen in aufeinanderfolgenden Ausführungen des Algorithmus) (Komplexität O (1) oder O ( N))

  2. Für jedes noch leere Wort Slots (die Kreuzungen mit bereits gefüllten Wortslots haben), berechnen Sie ein Constraint-Verhältnis (das kann variieren, einfach ist die Anzahl der verfügbaren Lösungen in diesem Schritt) und sortieren die leeren Wortslots mit diesem Verhältnis (Komplexität O (NlogN ) oder O (N))

  3. Durchlaufen Sie die leeren Wortslots, die im vorherigen Schritt berechnet wurden, und probieren Sie mehrere Cancidate-Lösungen aus (stellen Sie sicher, dass “Arc-Consistency beibehalten wird”, dh Gitter hat nach diesem Schritt eine Lösung, wenn dieses Wort verwendet wird) und sortieren Sie sie nach maximale Verfügbarkeit für den nächsten Schritt (dh der nächste Schritt hat eine maximal mögliche Lösung, wenn dieses Wort zu diesem Zeitpunkt an dieser Stelle verwendet wird, usw.) (Komplexität O (N * MaxCandidatesUsed))

  4. Füllen Sie dieses Wort aus (markieren Sie es als gefüllt und gehen Sie zu Schritt 2)

  5. Wenn kein Wort gefunden wird, das die Kriterien von Schritt .3 erfüllt, versuchen Sie, zu einer anderen Kandidatenlösung eines vorherigen Schritts zurückzukehren (Kriterien können hier variieren) (Komplexität O (N))

  6. Wenn der Backtrack gefunden wurde, verwenden Sie die Alternative und setzen Sie gegebenenfalls bereits gefüllte Wörter zurück, die möglicherweise zurückgesetzt werden müssen (markieren Sie sie erneut als nicht ausgefüllt) (Komplexität O (N))

  7. Wird kein Backtrack gefunden, kann die No-Lösung gefunden werden (zumindest bei dieser Konfiguration, Initial Seed etc ..)

  8. Sonst, wenn alle Wordlots gefüllt sind, haben Sie eine Lösung

Dieser Algorithmus führt einen zufälligen konsistenten Ablauf des Lösungsbaums des Problems durch. Wenn es zu irgendeinem Zeitpunkt eine Sackgasse gibt, führt es eine Zurückverfolgung zu einem vorherigen Knoten durch und folgt einer anderen Route. Bis entweder eine gefundene Lösung oder eine Anzahl von Kandidaten für die verschiedenen Knoten erschöpft ist.

Der Konsistenzteil stellt sicher, dass eine gefundene Lösung tatsächlich eine Lösung ist und der zufällige Teil es ermöglicht, unterschiedliche Lösungen in verschiedenen Ausführungen zu erzeugen und auch im Durchschnitt eine bessere performance zu haben.

PS. All dies (und andere) wurden in reinem JavaScript (mit parallel processing und WYSIWYG) implementiert

PS2. Der Algorithmus kann leicht parallelisiert werden, um mehr als eine (unterschiedliche) Lösung gleichzeitig zu erzeugen

Hoffe das hilft

Ich würde zwei Zahlen generieren: Länge und Scrabble. Angenommen, ein niedriger Scrabble-Score bedeutet, dass es einfacher ist, mitzumachen (niedrige Punktzahlen = viele gewöhnliche Buchstaben). Sortieren Sie die Liste nach Länge absteigend und Scrabble-Score aufsteigend.

Als nächstes gehe einfach die Liste runter. Wenn sich das Wort nicht mit einem bestehenden Wort kreuzt (überprüfen Sie jedes Wort auf seine Länge und Scrabble-Punktzahl), dann legen Sie es in die Warteschlange und überprüfen Sie das nächste Wort.

Spülen und wiederholen, und dies sollte ein Kreuzworträtsel erzeugen.

Natürlich bin ich mir ziemlich sicher, dass dies O (n!) Ist und es nicht garantiert ist, das Kreuzworträtsel für dich zu vervollständigen, aber vielleicht kann jemand es verbessern.

Hier ist ein JavaScript-Code, der auf Nickfs Antwort und Bryans Python-Code basiert. Einfach posten, falls jemand anderes es in js benötigt.

 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(); } 

Ich habe rund um Kreuzworträtsel Generator Engine gespielt, und ich fand dies das Wichtigste:

0. !/usr/bin/python

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

    b. mache einen Gegenstand / Gegenstand wie den Cursor, der sich zur einfachen Orientierung durch die Matrix bewegt, es sei denn, du willst später durch zufällige Auswahl iterieren.

  2. das erste, nehme das erste Paar auf und lege es von 0,0 auf und ab; speichern Sie das erste als unser aktuelles Kreuzworträtsel “Führer”.

  3. Bewegen Sie den Cursor nach der Reihenfolge diagonal oder zufällig mit größerer diagonaler Wahrscheinlichkeit zur nächsten leeren Zelle

  4. Iteriere über die Wörter like und nutze die freie Leerzeichenlänge, um die maximale Wortlänge zu definieren: 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. um das Wort mit dem freien Raum zu vergleichen, den ich benutzt habe, zB:

     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. Nach jedem erfolgreich verwendeten Wort ändern Sie die Richtung. Schleife, während alle Zellen gefüllt sind ODER wenn dir keine Wörter oder eine Begrenzung der Iterationen zur Verfügung stehen, dann:

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

… und wiederhole ein neues Kreuzworträtsel.

  1. Machen Sie das Scoring-System durch Leichtigkeit der Füllung und einige Schätzwerte. Geben Sie eine Punktzahl für das aktuelle Kreuzworträtsel ein und schließen Sie eine spätere Auswahl ab, indem Sie sie an die Liste der gemachte Kreuzworträtsel anhängen, wenn die Punktzahl von Ihrem Punktesystem erfüllt wird.

  2. Nach der ersten Iterationssitzung wiederholen Sie erneut aus der Liste der erstellten Kreuzworträtsel, um den Job zu beenden.

Durch die Verwendung von mehr Parametern kann die Geschwindigkeit um einen großen Faktor verbessert werden.

Ich würde einen Index von jedem Buchstaben bekommen, der von jedem Wort verwendet wird, um mögliche Kreuze zu kennen. Dann würde ich das größte Wort wählen und es als Basis verwenden. Wähle das nächste große und überquere es. Spülen und wiederholen. Es ist wahrscheinlich ein NP-Problem.

Eine andere Idee besteht darin, einen genetischen Algorithmus zu erstellen, bei dem die Stärke-Metrik angibt, wie viele Wörter Sie in das Gitter einfügen können.

Der schwierige Teil, den ich finde, ist, wann man weiß, dass eine bestimmte Liste nicht überschritten werden kann.

Ich habe über dieses Problem nachgedacht. Mein Sinn ist, dass man, um ein wirklich dichtes Kreuzworträtsel zu erstellen, nicht hoffen kann, dass Ihre begrenzte Wortliste ausreicht. Daher möchten Sie vielleicht ein Wörterbuch nehmen und es in eine “Trie” -Datenstruktur einfügen. Auf diese Weise können Sie leicht Wörter finden, die die restlichen Leerzeichen ausfüllen. In einem Trie ist es ziemlich effizient, eine Traversierung zu implementieren, die beispielsweise alle Wörter der Form “c? T” enthält.

Also, mein generelles Denken ist: Erstellen Sie eine Art von relativ roher Gewalt Ansatz wie einige hier beschrieben, um ein Kreuz mit niedriger Dichte zu erstellen, und füllen Sie die Lücken mit Wörterbuch Wörtern.

Wenn jemand anderes diesen Ansatz gewählt hat, lass es mich wissen.

Hier ist eine Swift-Version des Kreuzworträtselgenerators basierend auf Bryans Python-Code.

Teilen Sie es einfach für den Fall, dass jemand es braucht.

Ich habe eine 100% jQuery Lösung für dieses Problem jQuery .

Beispieldemo: http://www.earthfluent.com/crossword-puzzle-demo.html

Quellcode: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

Die Absicht des Algorithmus, den ich verwendet habe:

  1. Minimiere die Anzahl der unbrauchbaren Quadrate im Gitter so weit wie möglich.
  2. Habe so viele miteinander gemischte Wörter wie möglich.
  3. Rechnen Sie in extrem kurzer Zeit.

Ich werde den Algorithmus beschreiben, den ich verwendet habe:

  1. Gruppiere die Wörter nach denen, die einen gemeinsamen Buchstaben teilen.

  2. Erstellen Sie aus diesen Gruppen Sätze einer neuen Datenstruktur (“Wortblöcke”), die ein Primärwort ist (das durch alle anderen Wörter läuft) und dann die anderen Wörter (die durch das Primärwort laufen).

  3. Beginnen Sie das Kreuzworträtsel mit dem ersten dieser Wortblöcke ganz oben links im Kreuzworträtsel.

  4. Für den Rest der Wortblöcke, ausgehend von der rechten unteren Position des Kreuzworträtsels, bewegen Sie sich nach oben und nach links, bis keine freien Plätze mehr verfügbar sind. Wenn sich mehr leere Spalten nach oben als nach links befinden, bewegen Sie sich nach oben und umgekehrt.