Wie man ein Schwedenrätsel mit Lösungswort generiert

Ein Schwedenrätsel mit Lösungswort generieren Sie in zwei Phasen: Suchen Sie zuerst mit einer lokalen Suche die Maske, also die Verteilung von Fragefeldern und Buchstabenfeldern, und füllen Sie sie dann mit Wörtern aus dem Wörterbuch als Constraint-Satisfaction-Problem (CSP) mit Backtracking. Setzen Sie das Lösungswort nicht vorab ins Gitter. Erst wenn das Rätsel fertig ist, suchen Sie einen Witz, dessen Pointe sich darin von links nach rechts und von oben nach unten lesen lässt.

So entstehen die Schwedenrätsel in unserer App mit Kreuzworträtseln und Wortsuchrätseln (App Store, Google Play). Ein Gitter kostet wenige Sekunden bis einige Dutzend Sekunden Rechenzeit, deshalb generieren wir die Rätsel vorab auf einem leistungsfähigeren Rechner und liefern sie mit der App aus. Wortsuchrätsel entstehen ganz anders und einfacher, das beschreibt der Artikel Wie man ein Wortsuchrätsel mit Lösungswort generiert.

#Was ein Schwedenrätsel erfüllen muss

Ein Schwedenrätsel hat keine schwarzen Felder. Jedes Feld ist ein Buchstabe oder ein Fragefeld mit Pfeil nach rechts oder nach unten. Daraus ergeben sich harte Bedingungen:

• Jeder Buchstabe gehört zu einem waagerechten und einem senkrechten Wort. Ein Buchstabe, den nur ein Wort kreuzt, lässt sich nicht überprüfen und wirkt wie ein Fehler.
• Jedes Wort hat mindestens zwei Buchstaben und davor ein Fragefeld. Deshalb bestehen die erste Zeile und die erste Spalte immer nur aus Fragefeldern.
• Die Buchstaben bilden eine zusammenhängende Fläche ohne abgetrennte Inseln.
• Jedes Wort muss im Wörterbuch stehen und mindestens eine Umschreibung haben. Kein Wort kommt im Gitter zweimal vor.

Dazu kommen weiche Qualitätskriterien: wenige Wörter mit zwei Buchstaben, keine Fragefelder, die ins Leere zeigen, und möglichst wenige sehr lange Wörter, die schwer zu füllen sind. Das Problem ist rechnerisch schwer. Engel et al. (2012) haben gezeigt, dass schon das Füllen einer Maske mit Wörtern NP-vollständig ist.

#Warum Wort für Wort füllen nicht reicht

Der erste Gedanke ist, wie ein Mensch mit Bleistift vorzugehen: das Lösungswort in Wörter teilen, sie wie in der Zeitung in eine Zeile legen, durch jeden Buchstaben ein kreuzendes Wort führen und den Rest des Gitters mit einem Greedy Algorithm auffüllen. Ein Greedy Algorithm wählt in jedem Schritt, was gerade am besten aussieht, und revidiert die Entscheidung nie. Wo nichts passt, bleibt ein Loch. Und weil Greedy-Füllen nicht zurückgehen kann, rettet der Rest des Gitters nichts mehr, wenn die ersten zehn Wörter schlecht sind.

Eine bessere Heuristik für die Wortwahl hilft nur wenig. Sie können die Längen der kreuzenden Wörter von mittleren, um die fünf Buchstaben, hin zu den Extremen probieren. Oder evolutionär vorgehen: eine Population halbfertiger Rätsel, aus jedem fünf Nachkommen mit je einem Wort mehr, bewertet nach gefüllten Feldern, Anzahl der Vokale und Gleichmäßigkeit der Buchstaben, und nur die besten kommen in die nächste Generation. Die Ergebnisse werden etwas dichter, aber die Löcher bleiben, weil die Heuristik nur den nächsten Schritt sieht.

Den Ausweg zeigt die Bachelorarbeit von Jakob Engel an der TU München (2009); er ist auch Erstautor des oben genannten Artikels. Teilen Sie die Aufgabe in zwei unabhängige Phasen: Finden Sie erst eine gute Maske, ohne auf Wörter zu achten, und füllen Sie sie dann. Engel verwendete für die Maske einen evolutionären Algorithmus. Wir verwenden eine einfachere lokale Suche mit zufälligen Erschütterungen, beschrieben im nächsten Schritt.

#Schritt 1: die Maske per Hill Climbing

Die Maske ist ein Gitter, in dem jedes Feld entweder Fragefeld oder Buchstabe ist. Um sie zu finden, reicht Hill Climbing: eine lokale Suche, die kleine Änderungen macht und diejenigen behält, die das Ergebnis nicht verschlechtern.

Beginnen Sie zufällig, mit Fragefeldern auf etwa 22 % der inneren Felder. Geben Sie jeder Maske eine Strafpunktzahl. Harte Verstöße (zu kurzes Wort, Buchstabe ohne kreuzendes Wort, abgetrennte Insel) sollten meist 1.000 Punkte kosten, weiche Mängel (Zweibuchstabenwörter über dem Budget, ein Fragefeld, das auf kein Wort zeigt, gehäufte Fragefelder) 50 bis 500.

Ändern Sie dann in einer Schleife ein Feld von Fragefeld zu Buchstabe oder umgekehrt, oder verschieben Sie ein Fragefeld um ein Feld diagonal. Behalten Sie die Änderung, wenn die Strafe nicht gestiegen ist, sonst machen Sie sie rückgängig. Richten Sie die Hälfte der Änderungen auf die Felder mit der höchsten Strafe, dann verschwinden grobe Fehler schnell:

Hill Climbing bleibt leicht in einem lokalen Minimum hängen. Wenn sich 2.000 Schritte lang nichts verbessert, „schütteln“ Sie das Gitter: Schalten Sie in der besten bisher gefundenen Maske fünf zufällige Felder um und suchen Sie weiter. Das sind die Spitzen im Diagramm. Bringen auch drei Erschütterungen keine bessere Maske und hat sie keine harten Verstöße, hören Sie auf.

Die fertige Maske hat eine Reststrafe von 200 für weiche Mängel, aber keinen harten Verstoß:

Die Strafen für ein Fragefeld ohne Wort und für eine abgetrennte Insel sollten von Anfang an in der Maske stecken. In einem großen Bestand fertiger Rätsel ohne sie zeigten 13,2 % der Fragefelder auf kein Wort, und 23,5 % der Gitter hatten eine abgetrennte Buchstabeninsel. Mit ihnen sind es 5,0 % und 0 %.

#Schritt 2: Füllen mit Wörtern als CSP

Aus der Maske entsteht eine Liste von Slots, also Plätzen für Wörter mit bekannter Länge und bekannten Kreuzungen. Das Füllen ist ein klassisches Constraint-Satisfaction-Problem (CSP): Jeder Slot ist eine Variable, seine Domäne sind die Wörter, die hineinpassen, und die Bedingungen sind gleiche Buchstaben an den Kreuzungen. Gelöst wird es mit Backtracking, einer Suche, die in einem toten Zweig einen Schritt zurückgeht und eine andere Möglichkeit probiert:

für jeden Slot: Domäne = alle Wörter dieser Länge
solange nicht alle Slots gefüllt sind:
    wähle den Slot mit der kleinsten Domäne (bei Gleichstand den mit den meisten Kreuzungen)
    für jedes Wort der Domäne, das beste zuerst:
        setze das Wort
        schränke die Domänen der kreuzenden Slots auf Wörter mit passendem Buchstaben ein
        wenn eine Domäne leer wurde: rückgängig machen, nächstes Wort versuchen
        sonst mit dem nächsten Slot weitermachen
    wenn kein Wort passt: einen Slot zurückgehen
nach 50.000 Schritten aufgeben

In der Literatur heißen diese Heuristiken MRV (Minimum Remaining Values, zuerst der Slot mit den wenigsten Möglichkeiten) und Forward Checking (nach jedem Setzen die Domänen der Nachbarn einschränken, damit ein toter Zweig sofort auffällt und nicht erst zehn Wörter später). Indizieren Sie das Wörterbuch vorab nach Länge, Position und Buchstabe. „Wörter mit Q an dritter Stelle“ sind dann eine einzige Schnittmenge, kein Durchlauf durch das ganze Wörterbuch.

Auch die Reihenfolge der Wörter zählt. Geben Sie Wörtern mit mehr verschiedenen Umschreibungen im Wörterbuch den Vorrang. Das ist ein einfaches Signal für ein gängiges Rätselwort. Ohne das füllt sich das Gitter mit unbekannten Abkürzungen.

#Schritt 3: das Lösungswort im fertigen Gitter

Beim Füllen wissen Sie noch nicht, wie das Lösungswort lautet. Lesen Sie die Buchstaben des fertigen Gitters von links nach rechts und von oben nach unten und suchen Sie einen Witz, dessen Pointe in dieser Zeichenkette als Teilfolge vorkommt. Die Buchstaben stehen also in der richtigen Reihenfolge, müssen aber nicht nebeneinander liegen. Wird einer gefunden, verteilen Sie die Buchstaben möglichst gleichmäßig über das Gitter, damit sich die Pointe nicht aus einem einzigen Wort erraten lässt.

Diese Reihenfolge (erst das Gitter, dann der Witz) erhöht die Zahl fertiger Rätsel drastisch. In unserer Messung passt ein einziges 12×12-Gitter im Schnitt zu 86 Witzen aus der slowakischen Liste (5.960 Witze). Es findet sich also immer einer, der in dieser Größe noch nicht verwendet wurde.

#Warum das Lösungswort nicht vorab wie in der Zeitung

In der Zeitung steht das Lösungswort meist an einer Stelle, in einer Zeile und in Wörter geteilt. Dahin führen zwei Wege, und beide liefern sehr wenige Ergebnisse.

Der erste Weg ist, das Lösungswort vorab ins Gitter zu setzen. Dann muss es hineinpassen. Unsere Pointen haben im Schnitt 10,3 Buchstaben und 2 Wörter. So groß ist der Anteil der Witze aus der slowakischen Liste, die sich in einer bestimmten Größe überhaupt platzieren lassen:

Mit vorab gesetztem Lösungswort gelingt das Füllen kleiner Gitter etwa so oft wie ohne. Bei 15×15 waren es 5 von 60 Versuchen gegenüber 8 ohne, bei 18×18 keiner von 60. Jedes solche Gitter dient außerdem nur einem Witz, und in kleinen Größen lässt sich die Mehrheit der Witze gar nicht platzieren.

Der zweite Weg ist, das Gitter frei entstehen zu lassen und die Pointe darin als zusammenhängenden Abschnitt zu suchen. In einer Stichprobe von 2.200 fertigen slowakischen Rätseln (200 jeder Größe von 8×8 bis 18×18) fand sich die ganze Pointe als zusammenhängender Abschnitt in einer Zeile oder Spalte nur in 81 Gittern (3,7 %). Darf jedes Wort der Pointe an einer anderen Stelle liegen, sind es 443 Gitter (20 %), und das noch ohne die Bedingung, dass die Wörter nebeneinander stehen. In Lesereihenfolge fand sich in jedem von ihnen ein Witz. Für den Preis eines über das Gitter verstreuten Lösungsworts bekommen Sie um Größenordnungen mehr Rätsel.

#Leistung des Generators und warum er nicht auf dem Handy läuft

Der Generator lief mit dem slowakischen Wörterbuch 60 Versuche pro Größe, in einem Thread (JavaScript auf Node 22, Server-CPU Intel Xeon 2,8 GHz in der Cloud). Ein Versuch ist eine Maske und ein Füllvorgang. „Erfolgreich gefüllt“ heißt, dass der CSP innerhalb von 50.000 Schritten eine Lösung gefunden hat.

Was die Messung zeigt:

• Ein kleines Gitter ist kein leichtes. Ein 8×8-Gitter hat viele kurze Slots mit vielen Kreuzungen und wenig Spielraum, das Füllen gelingt nur in 5 % der Versuche. Ein gefülltes Gitter kostet im Schnitt etwa 10 Sekunden Rechenzeit bei 8×8, 4 Sekunden bei 12×12 und 18 Sekunden bei 18×18.
• Die meisten Versuche scheitern. Starten Sie Versuche deshalb parallel auf allen Kernen und nehmen Sie das erste ausreichend gute Ergebnis.
• Auf dem Handy ergibt das keinen Sinn. Niemand will beim Öffnen eines Rätsels Dutzende Sekunden warten, und die App müsste das ganze Wörterbuch mit Umschreibungen mitliefern. Ein Generator in der App muss außerdem ständig die Kontrolle an die Oberfläche abgeben, sonst friert die App ein.

#Generieren in großen Mengen

Der Generator gehört deshalb auf einen Rechner mit Mehrkernprozessor. Bei uns hat jeder Kern einen eigenen Thread mit dem Wörterbuch, das einmal beim Start geladen wird. Ein Gitter ist fertig, sobald einer der Threads ein Ergebnis mit ausreichend wenigen ungenutzten Feldern liefert. Im Dauerbetrieb erzeugt er reihum ein Rätsel jeder Größe in jeder Sprache. So sind über 14.000 Rätsel in vier Sprachen (Slowakisch, Tschechisch, Englisch, Deutsch) und elf Größen von 8×8 bis 18×18 entstanden. Jeder Witz kommt pro Größe und Sprache höchstens einmal vor.

Bei dieser Menge zählen zwei Dinge:

• Format. Ein vollständiger Datensatz braucht etwa 28 kB pro Rätsel und 390 MB für den ganzen Bestand. Das meiste lässt sich berechnen (Koordinaten, Feldtypen, Nummern der Fragefelder). Ein kompaktes Format mit dem Gitter als einer einzigen Zeichenkette braucht etwa 2 kB, 15 MB für den Bestand und etwa 7 MB im Installationspaket der App.
• Qualität messen. Messen Sie nach jeder Generierung den Anteil der Fragefelder ohne Wort und der Gitter mit Inseln, und lassen Sie die Prüfung fehlschlagen, wenn die Zahlen schlechter werden.

#Was der Ansatz nicht abdeckt

• Fragefelder ohne Wort. Das durchschnittliche Rätsel hat immer noch 2,7 Fragefelder, die ins Leere zeigen. Die linke obere Ecke ist immer eines davon.
• Wörterbücher ohne Häufigkeiten. Das deutsche Wörterbuch aus Wiktionary hat für die meisten Wörter nur eine Umschreibung, die Sortierung nach Anzahl der Umschreibungen unterscheidet daher kaum, und seltene Wörter landen im Gitter. Eine Häufigkeitsliste würde helfen, wir haben noch keine.
• Das Lösungswort steht nicht an einer Stelle. Wer es aus der Zeitung kennt, sucht es vielleicht in einer Zeile. Das ist ein Kompromiss, kein Ideal.

Wenn Sie ein ähnliches Problem mit generierten Inhalten lösen oder eine mobile App brauchen, schreiben Sie uns.