ROTARENEGLRIUQTROW

Wortsuchrätsel per Skript erstellen für jedermann – und Programmierer

Ob Kurzweil für den Kindergeburtstag, Mystery beim Geocachen oder Konzentrationstest für Bewerber – Schlangenworträtsel wie das aus c’t 10/2023 sind vielseitig. Mit unserem Python-Skript können Sie Ihre eigenen Rätsel kreieren.

Von Oliver Lau

Klassische Wortsuchrätsel geben eine Matrix mit einem wirren Buchstabensalat vor, in dem sich Wörter in horizontaler, vertikaler und diagonaler Leserichtung verstecken. Die enthaltenen Wörter stehen meist daneben; es geht nur darum, sie in der Matrix zu finden. Bei den schwierigeren Vertretern dieser Rätselgattung kann man die Wörter nicht nur nach rechts und unten lesen, sondern auch nach links und oben.

Für das Gewinnspiel anlässlich des 40-jährigen Bestehens der c’t-Redaktion war uns das aber zu schnöde. Das Wortsuchrätsel in c’t 10/2023 (S. 58) sollte beträchtlich schwieriger sein. Die Regeln:

1. Die Leserichtung kann innerhalb eines Wortes wechseln, auch mehrfach.
2. Ein Wort kann sich an der gegenüberliegenden Kante der Matrix fortsetzen.
3. Wörter können sich kreuzen, teilweise überschneiden oder ineinander übergehen.
4. In der Schwierigkeitsstufe „Sado“ ist der nächste Buchstabe nicht in einer unmittelbar benachbarten Zelle zu finden, sondern jeweils in der übernächsten oder noch weiter entfernt.

Für das veröffentlichte Rätsel haben wir von der letzten Fiesheit abgesehen, aber unser Python-Skript, das wir zum Generieren von Schlangenworträtseln programmiert haben, kann solche Rätsel erzeugen. Das Folgende zeigt, wie Sie es benutzen und an Ihre Wünsche anpassen.

Starten

Sie finden das Skript im GitHub-Repository zu diesem Artikel (siehe ct.de/y937 ). Wenn Sie das Repository nicht mit git clone https://github.com/607011/wordsearch.git klonen wollen, können Sie auch eine Zip-Datei des jüngsten Standes herunterladen. Dazu drücken Sie den grünen, mit „Code“ beschrifteten Knopf und wählen dann „Download ZIP“.

Um das Skript snakewordcreator.py auszuführen, benötigen Sie Python 3. In unserem kostenlos online verfügbaren Starthilfeartikel können Sie nachlesen, wie Sie Python unter Windows, Linux und macOS einrichten [1].

Wenn Sie startklar sind, rufen Sie die Eingabeaufforderung (Windows) oder ein Terminal (Linux, macOS) auf und steuern darin das beim Klonen oder Entzippen angelegte Verzeichnis an. Im Unterverzeichnis „wortlisten“ finden Sie unter anderem die UTF-8-kodierte Textdatei it.txt. Sie enthält die für das Rätsel in c’t 10/2023 verwendeten Wörter, ein Wort pro Zeile. Sie können sie erweitern oder Textdateien mit eigenen Wortlisten erstellen.

Um aus der Beispielwortliste Ihr erstes Schlangenworträtsel zu erzeugen, tippen Sie Folgendes ein:

python3 snakewordcreator.py wortlisten/it.txt

Nach einer kurzen Denkpause spuckt das Skript das Resultat aus. Da beim Generieren ganz viel Zufall im Spiel ist, sieht die Ausgabe bei Ihnen sehr wahrscheinlich anders aus als im Screenshot unten.

Wenn Sie die Ausgabe mit dem Inhalt der eingelesenen Wortliste vergleichen, wird Ihnen auffallen, dass die Wörter dort in derselben Reihenfolge stehen. Das ist so, weil das Skript die Wörter in dieser Reihenfolge abarbeitet. Die Ausgabe enthält allerdings nicht alle Wörter, sondern nur die, die es nach dem Zufallsprinzip in die Matrix einfügen konnte, bis es nach einer einstellbaren Zahl von Versuchen pro Wort aufgibt. Voreingestellt sind 10 · Breite · Höhe Versuche.

Mit Breite ist die Anzahl der Spalten in der Matrix gemeint, mit Höhe die Anzahl der Zeilen; beide Werte sind 10 per Default. Sie können die Größe über die Kommandozeilenoptionen --width (Breite) und --height (Höhe) anpassen, die Anzahl der Versuche über --max-tries, zum Beispiel wie folgt:

snakewordcreator.py --width 15 --height 14 --max-tries 1000 wortlisten/it.txt

Da nicht garantiert ist, dass ein in der eingelesenen Liste enthaltenes Wort in der Matrix landet, sollten Sie die Wörter, die Sie unbedingt drin haben wollen, möglichst weit vorne aufführen. Gleiches gilt für lange Wörter, weil die Wahrscheinlichkeit, mit der das Skript Wörter platzieren kann, mit ansteigendem Füllstand der Matrix sinkt. Nach hinten raus ist es also sinnvoll, kurze Wörter oder Akronyme aufzulisten.

Wenn Sie sich nicht die Mühe der händischen Sortierung machen wollen, bewirkt die Option --sort descending, dass das Skript die Wörter nach absteigender Länge abarbeitet.

Weil die Textausgabe der Matrix nur leidlich brauchbar ist, kann das Skript auch eine in gängigen Vektorgrafikprogrammen wie dem kostenlosen InkScape bearbeitbare SVG-Datei erzeugen: Mit der Option --svg schlangenwort.svg schreibt das Skript die SVG-Daten in die Datei schlangenwort.svg.

Justieren

Wenn das Skript ein neues Wort platziert, sucht es sich per Zufall eine Stelle in der Matrix, die entweder mit noch keinem Buchstaben oder mit dem ersten Buchstaben des Wortes belegt ist. Für jeden weiteren Buchstaben macht es nach demselben Prinzip bei einem der vier Nachbarfelder weiter. Zur Erhöhung des Schwierigkeitsgrades können Sie verhindern, dass es dabei zweimal nacheinander dieselbe Richtung einschlägt. Dazu dient der Schalter --forbid-same-direction.

In der Standardeinstellung erlaubt das Skript, dass sich ein Wort an der gegenüberliegenden Kante fortsetzt, beispielsweise vom rechten Rand zum linken übergeht oder vom oberen Rand zum unteren. Wenn Sie das unterbinden und damit das generierte Rätsel etwas leichter machen wollen, verwenden Sie den Schalter --forbid-wrap.

Wenn es noch ein bisschen leichter werden soll, teilen Sie dem Skript mit, dass es den jeweils nächsten Buchstaben eines Wortes bevorzugt rechts vom Vorgänger platzieren soll. Um die Wahrscheinlichkeit für den rechten Nachbarn zu verdoppeln, verwenden Sie die Option --right-weight 2, zum Verzehnfachen --right-weight 10 und so weiter. --right-weight 1 hat keine Wirkung, weil es das Standardverhalten ist.

Wie man es von Kreuzworträtseln im deutschsprachigen Raum kennt, wandelt das Skript die Umlaute Ä, Ö und Ü in AE, OE und UE sowie ß in SS um, bevor es ein Wort platziert. Wenn Sie Umlaute und Eszetts erhalten wollen, starten Sie das Skript mit --allow-umlauts.

Sollte Ihnen ein kleiner Sadist innewohnen, sagen Sie dem Skript, dass der jeweils nächste Buchstabe nicht in der Nachbarzelle landen soll, sondern n Zellen weiter: --hop 1 entspricht dem Standardverhalten, mit --hop 2 wählt das Skript die übernächste Zelle, mit --hop 3 überspringt es zwei Zellen und so weiter.

Prüfen

Wenn so viel Zufall im Spiel ist wie bei unserem Skript, kann es passieren, dass Rätsler in der Matrix Wörter finden, die es in der ursprünglichen Liste gar nicht gibt. Um zu prüfen, ob sie recht haben, können Sie die ebenfalls im Repository befindliche Mini-Webanwendung benutzen.

Öffnen Sie die Datei check.html in einem Browser, sehen Sie zwei leere Eingabefelder: Das obere erwartet die Eingabe des Wortes, das Sie in der Matrix aufspüren wollen, das untere die Matrix, wie Sie das Skript in Textform ausgibt.

Wenn Sie sie dort per Copy & Paste einfügen, erscheint die Matrix darüber ein weiteres Mal, aber etwas ansehnlicher. Mit jedem Zeichen, das Sie ins obere Eingabefeld tippen, schlängelt sich eine farbliche Hinterlegung durch die Matrix, die die gefundenen Buchstaben hervorhebt. Vielleicht sind Sie bei Ihrem eigenen Rätsel auch so überrascht wie wir, welche Begriffe außer den vorgegebenen in der Matrix enthalten sind (siehe c’t 13/2023, S. 50).

Modifizieren

Bislang haben wir beschrieben, wie Sie das Skript von außen über Kommandozeilenparameter steuern können. Wenn Sie das Verhalten des Skripts anderweitig feintunen wollen oder Ihnen Features fehlen, fühlen Sie sich ermuntert, Hand an den Code zu legen. Das Folgende zeigt Ihnen ein paar nützliche Stellen für Erweiterungen oder Modifikationen.

Zum Beispiel könnten Sie auf die Idee kommen, ein Wortsuchrätsel für traditionelles Chinesisch oder für Hebräisch zu erstellen. Dann wollen Sie vielleicht die Richtung nach unten oder links für den jeweils nächsten Buchstaben bevorzugen. Dafür eignet sich die SnakeWordPuzzleGenerator-Membervariable self.weights, die der Konstruktor standardmäßig wie folgt initialisiert:

self.weights = [
    self.right_weight, 1, 1, 1]

Sie enthält eine Liste relativer Gewichte, anhand derer der Generator die nächste Richtung auswählt. Der i-te Wert aus self.weights korrespondiert mit dem i-ten Wert aus der Liste der vier möglichen Richtungen in self.directions:

self.directions = [
    RIGHT, LEFT, DOWN, UP]

Beide Werte braucht die innere Funktion get_random_direction() in der Methode construct(): Sie sortiert die Liste der Richtungen zufällig, aber gewichtet um: Je höher das mit einer Richtung korrespondierende Gewicht ist, umso größer ist ihre Chance, weiter vorne einsortiert zu werden. Den nächsten Buchstaben hängt das Skript dann in der ersten Richtung an das bereits positionierte Wort an, in der er passt. Die while-Schleife läuft so lange, bis random.choices() alle Richtungen entsprechend ihrer Gewichte ausgewählt hat:

if any(w != 1 for w in self.weights):
  remaining_directions = \
               self.directions.copy()
  remaining_weights = \
               self.weights.copy()
  directions = []
  while not all(d in directions
           for d in self.directions):
    choice = random.choices(
      remaining_directions,
      weights=remaining_weights,
      k=1,
    )[0]
    idx = remaining_directions\
                       .index(choice)
    remaining_directions.pop(idx)
    remaining_weights.pop(idx)
    directions.append(choice)

RIGHT, LEFT und so weiter sind nicht einfach irgendwelche ausgedachten Werte, sondern repräsentieren die Deltas der Koordinaten in der Matrix. RIGHT ist gleich (+self.hop, 0), was einen Schritt nach rechts in x-Richtung (Spalten) unter Beibehaltung der y-Koordinate (Zeile) bedeutet. UP ist (0, -self.hop), also in der Spalte eine Zeile nach oben. Anders als im von der Schule gewohnten kartesischen Koordinatensystem liegt der Ursprung informatiktypisch in der linken, oberen Ecke und nicht in der linken, unteren. self.hop wiederum enthält den Wert, den Sie über den Kommandozeilenparameter --hop gesetzt haben (Default: 1).

Die Liste möglicher Richtungen self.directions ist die Stelle im Code, die Sie anfassen müssen, um die Fortsetzung von Wörtern in der Diagonalen zu erlauben. Sie müsste vier zusätzliche Elemente enthalten, darunter etwa LEFT_DOWN mit dem Wert (-self.hop, +self.hop) oder RIGHT_UP mit (+self.hop, -self.hop).

Abschließend noch zwei Ideen: nicht stumpf per --forbid-same-direction unterbinden, dass das Skript zweimal nacheinander dieselbe Richtung einschlägt, sondern es beispielsweise über einen Schalter wie --prefer-same-direction plus einen Prozentwert wahrscheinlicher oder weniger wahrscheinlich machen. Zusätzlich zu --right-weight einen Schalter für --down-weight einführen – oder gleich einen Schalter --weights, dem eine Liste von vier Gewichten folgt.

Initiative

Mit den Standardeinstellungen produziert das Skript ganz schön fiese Wortsuchrätsel, deren Schwierigkeitsgrad Sie mit Kommandozeilenoptionen nach oben oder unten korrigieren können. Noch mehr Möglichkeiten eröffnen sich, wenn Sie bereit sind, in den Code einzugreifen. Ein paar geeignete Stellen haben wir Ihnen gezeigt. Wir sind gespannt, was Ihnen einfällt, und freuen uns über Feedback entweder an die Mailadresse am Artikelende oder als Issue im GitHub-Repository. Ansonsten wünschen wir viel Spaß beim Ausbaldowern von Wortlisten, beim Rätseln – oder beim Zuschauen, wie andere rätseln. (ola@ct.de)

Quellcode bei GitHub: ct.de/y937