Wie man ein Wortsuchrätsel mit Lösungswort generiert

Ein Wortsuchrätsel mit Lösungswort generieren Sie so: Legen Sie zufällige Wörter aus dem Wörterbuch in ein leeres Gitter, bis genau so viele Felder frei bleiben, wie das Lösungswort Buchstaben hat. Diese Felder füllen Sie dann mit dem Lösungswort, von links nach rechts und von oben nach unten. Auf dem Handy dauert das ein paar Millisekunden und braucht kein Backtracking, also kein Zurückgehen zu früheren Entscheidungen, wenn der Generator feststeckt.

Ein Wortsuchrätsel ist ein Buchstabengitter, in dem man Wörter aus einer Liste sucht und streicht. Das Lösungswort ergibt sich aus den Buchstaben, die danach übrig bleiben. Der Generator muss also ein vollständig gefülltes Gitter bauen, in dem nach dem Streichen genau das Lösungswort stehen bleibt. Mit dem folgenden Ablauf entstehen die Wortsuchrätsel in unserer App mit Kreuzworträtseln und Wortsuche (App Store, Google Play).

#Regeln für das Gitter

Legen Sie vorher fest, was ein fertiges Gitter erfüllen muss. In unserer App gilt:

• Wörter laufen in acht Richtungen: waagerecht, senkrecht und entlang beider Diagonalen, jeweils auch rückwärts.
• Zwei Wörter dürfen sich höchstens einen Buchstaben teilen.
• Kein Wort darf durch ein Feld des Lösungsworts laufen.
• Das Gitter muss voll sein. Ein leeres Feld ist ein Fehler.
• Das Lösungswort wird von links nach rechts und von oben nach unten aus allen nicht gestrichenen Buchstaben gelesen.

#Schritt 1: Wörterbuch vorbereiten

Teilen Sie das Wörterbuch einmal am Anfang in Gruppen nach Wortlänge auf. Ein zufälliges Wort einer bestimmten Länge ist dann ein einziger Zufallsindex. Wenn Sie für jedes Wort das ganze Wörterbuch filtern, wird die Generierung spürbar langsamer, denn für ein Gitter werden Hunderte Wörter probiert.

Unser slowakisches Wörterbuch hat 16.713 Wörter mit 3 bis 21 Buchstaben, die meisten mit sieben oder acht, das deutsche 134.937. Ein paar praktische Tipps:

• Lassen Sie Eigennamen und Abkürzungen im Wörterbuch. Dann tauchen im Gitter Wörter wie HOUSTON oder MAINE auf. Ohne kurze und „seltsame“ Wörter lässt sich das Gitter nicht dicht genug füllen.
• Filtern Sie Vulgäres mit einer eigenen Liste, die sich abschalten lässt, wenn jemand Inhalte für Erwachsene will.
• Bei mehreren Sprachen laden Sie nur die gerade gespielte. Das englische Wörterbuch hat über 414.000 Wörter. Werden beim App-Start alle vier Sprachen auf einmal geladen, steht ein schwächeres Handy bis zu 11 Sekunden still.

#Schritt 2: Lösungswort wählen

Das Lösungswort sollte mindestens so viele Buchstaben haben wie die Gitterseite und höchstens vier mehr. Ein kürzeres geht im Gitter unter, ein längeres braucht zu viele Löcher.

In unserer App ist das Lösungswort die Pointe eines Witzes. Man streicht die Wörter und liest aus den übrigen Buchstaben, wie der Witz endet. Wir bauen das Lösungswort vom Ende des Witzes: Von hinten kommen ganze Wörter dazu, bis die Länge in diesem Bereich liegt.

Die Bilder unten verwenden den englischen Witz „Two snakes walk into a bar. Turns out they were lizards.“ (Zwei Schlangen gehen in eine Bar. Es stellt sich heraus, dass es Eidechsen waren.) auf einem 10×10-Gitter. Das Lösungswort ist WERELIZARDS, 11 Buchstaben. Die Wörter in den Bildern stammen aus dem englischen Wörterbuch, beschränkt auf geläufige Wörter, damit sie lesbar sind.

#Warum nicht mit dem Lösungswort beginnen

Die erste Idee ist, es wie mit dem Bleistift zu machen: die Buchstaben des Lösungsworts in Lesereihenfolge auf zufällige Felder verteilen und dann Wörter darum herum bauen.

Das sieht vernünftig aus, bis das Ende kommt. Der Generator wählt ein leeres Feld, versucht ein Wort in allen Richtungen und Verschiebungen hindurchzulegen, und wenn das Gitter dicht wird, bleiben isolierte Löcher. Ein einzelnes Loch zwischen zwei Buchstaben des Lösungsworts lässt sich mit nichts füllen, denn das kürzeste Wort hat drei Buchstaben und kein Wort darf durch das Lösungswort laufen.

Bei einer Stichprobe von 200 Gittern 10×10 ergab dieser Ansatz nur in 28 % der Fälle ein volles Gitter, im Schnitt blieben 1 bis 2 Löcher. Sie nachträglich zu flicken ist aufwendig. Setzen Sie das Lösungswort also erst ein, wenn die Wörter fertig sind.

#Schritt 3: Gitter füllen, bis genau N Löcher übrig sind

Das Füllen ist ein einfacher Greedy Algorithm: Jedes Wort wird gelegt, sobald es passt, und nie wieder entfernt. Der Generator merkt sich nur eine Zahl: wie viele Felder noch leer sind. Ein Wort legt er nur, wenn danach nicht weniger leere Felder übrig bleiben, als das Lösungswort Buchstaben hat (N).

leer = Zeilen × Spalten
solange leer > N und Versuche < 2000:
    wort = zufälliges Wort der gewählten Länge
    höchstens 50-mal wiederholen:
        start = zufälliges Feld, richtung = zufällig aus 8
        wenn das Wort nach den Gitterregeln passt:
            neu = Anzahl leerer Felder, die das Wort füllt
            wenn leer - neu >= N:
                Wort legen
                leer = leer - neu
                weiter mit dem nächsten Wort
wenn leer != N: Gitter wegwerfen und neu anfangen

Die ersten Wörter landen frei im leeren Gitter:

Mit der Zeit beginnen Wörter, Buchstaben zu teilen. Das ist erwünscht, denn jeder geteilte Buchstabe ist ein Feld weniger, das gefüllt werden muss:

Sobald die Zahl der leeren Felder auf N fällt, ist Schluss. Wo die Löcher liegen, ist egal. Sie dürfen überall verstreut sein, weil das Lösungswort keinen zusammenhängenden Weg bilden muss:

#Schritt 4: Wortlängen mit Verstand ziehen

Lange Wörter machen ein Wortsuchrätsel interessant, kurze machen es fertig. Ziehen Sie die Länge deshalb aus zwei Normalverteilungen (normalverteilte Zufallszahlen liefert zum Beispiel die Box-Muller-Methode):

Die Länge ist immer mindestens 3 und höchstens die Gitterseite. Dazu zwei Regeln, ohne die der Generator am Ende hängen bleibt:

• Erzwingen Sie am Ende die genaue Länge. Fehlen 5 oder weniger Felder, suchen Sie ein Wort mit genau der fehlenden Länge (mindestens 3). Sonst versucht der Generator endlos Sechs-Buchstaben-Wörter, die nicht mehr passen.
• Rationieren Sie Wörter mit drei Buchstaben. Die ersten drei Versuche an einem Gitter dürfen keins enthalten, Versuche 4 bis 6 eins, die nächsten drei zwei und so weiter. Drei Buchstaben sind im Wörterbuch oft Abkürzungen wie DNA oder CPU und wirken im Rätsel billig. Erlauben Sie sie erst, wenn es anders nicht geht.

#Schritt 5: Lösungswort in die Löcher gießen

Gehen Sie das Gitter von links nach rechts und von oben nach unten durch und schreiben Sie in jedes leere Feld den nächsten Buchstaben des Lösungsworts. Da es genau N Löcher gibt, passt das Lösungswort ohne Rest.

Zu sehen ist am Ende nur das:

#Wenn ein Gitter misslingt

Erreicht der Generator innerhalb von 2.000 Versuchen nicht genau N leere Felder, werfen Sie das ganze Gitter weg und fangen neu an, höchstens 100-mal. Kein Flicken von Löchern. Das ist grob, aber für Gitter bis 12×12 reicht es mit Abstand. Größere Gitter brauchen mehr Versuche, wie die Tabelle unten zeigt.

#Erfolgsquote und Tempo je Gittergröße

Der Generator lief auf 300 Gittern pro Größe, mit echten Witzen und dem slowakischen Wörterbuch (Node.js 22 auf einer Server-CPU, ein Handy ist langsamer; die Bilder nutzen das englische Wörterbuch, die Zahlen das slowakische, weil es kleiner und damit der strengere Test ist). „Erster Versuch“ heißt, dass die erste Füllrunde mit einem vollen Gitter endete.

Was das für einen eigenen Generator bedeutet:

• Das durchschnittliche Wort hat 4,7 Buchstaben, obwohl das Ziel bei etwa 6 liegt. Lange Wörter passen in ein dichtes Gitter einfach öfter nicht.
• Etwa 9 bis 10 % der Felder teilen sich zwei Wörter. Das müssen Sie nicht einstellen, es folgt aus der Regel „höchstens ein gemeinsamer Buchstabe“.
• Es gibt weniger Diagonalen, als Sie erwarten. Die Richtung wird gleichverteilt aus acht gezogen, Diagonalen müssten also die Hälfte der Wörter sein. In einem kleinen Gitter fällt ein diagonales Wort aber viel öfter über den Rand. Bei 8×8 sind 24 % der Wörter diagonal, bei 15×15 schon 33 %. Wenn Sie mehr Diagonalen wollen, geben Sie ihnen beim Ziehen der Richtung mehr Gewicht.

#Tipp: dasselbe Gitter bei jedem Lauf

Für Store-Screenshots brauchen Sie jedes Mal genau dasselbe Gitter. Ersetzen Sie in diesem Modus den üblichen Zufallsgenerator durch einen einfachen linearen Kongruenzgenerator mit festem Seed (zum Beispiel aus der Sprache abgeleitet). Bleibt die gesamte Arithmetik in dem Bereich, den Zahlen in JavaScript exakt darstellen, ist das Ergebnis auf jedem Gerät gleich. Mit demselben Trick sind auch die Bilder in diesem Artikel entstanden.

Wenn Sie ein ähnliches Problem lösen, Rätsel generieren oder eine mobile App brauchen, schreiben Sie uns. Kurze Clips aus der Entwicklung gibt es auch auf YouTube. Ebenso Schritt für Schritt ist beschrieben, wie man ein Sudoku mit eindeutiger Lösung generiert. Für Kreuzworträtsel statt Wortsuche lesen Sie, wie man ein Schwedenrätsel mit Lösungswort generiert.