Kreuzworträtsel selber machen – 1000 Mark für den Gewinner
Kreuzworträtsel sind bei jung und alt beliebt. Das beweisen die vielen Rätselzeitschriften. Aber ein Kreuzworträtselprogramm zu schreiben ist etwas ganz anderes, als ein Rätsel zu lösen. Diese Aufgabe ist eine Herausforderung für gute Programmierer. Das beste Ergebnis des Kreuzworträtsel-Wettbewerbs stellen wir Ihnen vor.
Es läßt kaum Wünsche offen. Der Bildschirmaufbau ist genauso gut gelöst wie die Druckerausgabe. Auch den Bedienungskomfort kann man sich kaum besser vorstellen.
Ein Kreuzworträtselprogramm zu schreiben ist eine knifflige Aufgabe. Nicht nur die für den Betrachter eines Rätsels selbstverständlichen Regeln, wie das Kreuzen von Worten senkrecht zueinander und die dichte Vernetzung von Wörtern, auch die Geschwindigkeit und der Komfort des Programmes spielen eine große Rolle. Damit blieb in diesem Falle nur der Einsatz von Maschinensprache übrig. Das Kreuzworträtselprogramm besteht also aus zwei Teilen. Einem Rahmenprogramm in Basic, sowie einer Maschinenroutine, die im Bereich ab $C000/49152 geladen wird und die die Schwerarbeit leistet (zirka 30 Wortvergleiche/Sekunde).
Um das Rätselprogramm nicht unnötig mit der Eingabe des Wortschatzes zu belasten, werden die Wörter vorher mit einem Editor eingegeben und bis zu 255 in einem File auf Diskette abgelegt. Das eigentliche Rätselprogramm liest diese Files dann ein und verwendet sie im Rätselfeld (Bild 1). Trotzdem ist die Eingabe von Hand möglich. Denn der große Wortschatz eines Menschen kann niemals auf Diskette gespeichert werden.
Die Programme
Bevor also die Erzeugung eines Kreuzworträtsels starten kann, muß ein Wortschatz mit dem Lexikon-Editor eingegeben werden (Bild 2). Dieses Programm hat vier Aufgaben:
- Directory lesen. Dabei werden nur die bereits auf Diskette vorhandenen Wortschatzdateien angezeigt.
- Wortdatei anlegen. Mit diesem Programmteil können Sie bis zu 255 Wörter und die zugehörigen Fragestellungen eingeben und diese dann auf Diskette als Wortdatei ablegen. Eine spezielle Eingaberoutine (Zeile 1000 — 1099) sorgt dafür, daß nur erlaubte Zeichen eingegeben werden. Es ist zum Beispiel unsinnig, ein Kreuzwort einzugeben, das aus mehreren Teilen besteht, wie etwa »Level II Basic«, oder eine Mischung aus Zahlen und Buchstaben, wie »C 64«.
So können Sie sich also im Laufe der Zeit eine ganze Bibliothek von Wortschätzen aufbauen, die beliebig während der Rätselerzeugung einzusetzen sind.
Eine Besonderheit ist die Verkettung von Dateien. Sie können Nachfolgedateien benennen, die im Rätselprogramm automatisch nachgeladen werden, sobald der Vorgängerwortschatz erschöpft ist. Beispiel: Sie wollen ein Rätsel zum Thema »Computer« basteln. Geben Sie jetzt mit Hilfe des Lexikon-Editors den ersten Teil des geplanten Wortschatzes ein und benennen ihn mit »Computer.1«. Der Folgewortschatz soll »Computer.2« sein. Nachdem Sie den 1. Teil abgespeichert haben, geben Sie den 2. Teil ein und benennen den Nachfolger mit »Computer.3« und so weiter. Wollen Sie diese Kette beenden, wird einfach ein »q« (Quit) für den Nachfolger angegeben. Das Rätselprogramm bricht dann später an dieser Stelle mit dem automatischen Nachladen ab.
Bei dieser Methode hängt die Qualität des Rätsels entscheidend von der Staffelung der Dateien ab, das heißt im ersten File sollten lange Wörter stehen und mit jedem Folgefile die durchschnittliche Wortlänge abnehmen. Die Erstellung des Rätsels gerät dadurch wesentlich flüssiger, denn mit zunehmender Dichte des Wortfeldes müssen die Wörter natürlich immer kürzer werden, damit sie noch einzubauen sind.
- Wortdatei ändern. Mit Sicherheit tauchen irgendwann falsch eingegebene Kreuzwörter auf, so daß eine Datei verbessert werden muß. Unter diesem Programmpunkt kann daher die entsprechende Wortdatei geladen und editiert werden.
- Abbrechen. Mit Verlassen des Editors kann das Rätselprogramm geladen und gestartet werden, so daß ein fließender Übergang von der Worteingabe zur Rätselerstellung möglich ist.
Nun zum Kreuzworträtselprogramm. Wie schon gesagt, besteht dieses Programm aus zwei Teilen, einer Maschinenroutine und dem Basic-Rahmenprogramm. Dieses Rahmenprogramm (Bild 3) will ich zuerst beschreiben.
Nach dem Start des Programmes beginnt zunächst eine Initialisierungsphase (Zeilen 27—39). In einem Unterprogramm (ab Zeile 970) werden die Maschinenroutine für das Kreuzworträtsel und Treibersoftware für den Drucker am User-Port geladen. Wenn Sie einen Drucker am IEC-Bus betreiben, ist dieser Programmteil (Zeile 976 + 979) natürlich nicht nötig und zu entfernen.
Im folgenden Unterprogramm zur Dimensionierung der Variablen und Definition einiger Konstanten (Zeile 915—969) erfolgt der erste Sprung in die Maschinenroutine (Zeile 937), um sie zu initialisieren.
Nach dem Bildaufbau (Unterprogramm ab Zeile 600), ist auf dem Monitor ein Kreuzwortfeld von 20x20 Zeichen zu sehen. Das Programm fragt jetzt nach dem Startwort, das als erstes Wort im Feld eingetragen werden muß, um der Maschinenroutine einen Kristallisationspunkt zu bieten (Zeile 34—35). Geben Sie ein möglichst langes Wort ein, das Sie zum Beispiel unbedingt im Rätsel verarbeiten möchten. Bei dieser Eingabe findet, wie schon beim Editor, ein Zeichencheck statt, der es unmöglich machen soll, unerlaubte Zeichen im Rätselfeld unterzubringen. Danach müssen Sie sich zwischen einer waagerechten oder senkrechten Eintragung entscheiden, und ein Cursor taucht im Wortfeld auf. Fahren Sie wie gewohnt mit den Cursortasten die gewünschte Wortposition an und drücken die RETURN-Taste. Da es das erste Wort ist und genügend Platz im Wortfeld herrscht, wird Ihr Wort ohne Protest sofort eingetragen. Jetzt noch schnell die zugehörige Fragestellung eingetippt, und das erste Wort ist korrekt eingetragen.
Sie können dieses Spiel beliebig fortsetzen und theoretisch das ganze Rätsel auf diese Weise per Hand erstellen. Alle Eingaben von Hand sind frei von dem Zwang, ein Wort mit einem anderen kreuzen zu müssen. Sie können Ihre Wörter also beliebig positionieren, sollte ein Wort allerdings nicht passen, wird es zurückgewiesen und der Handeingabe-Modus abgebrochen.
Regulär verlassen Sie die Handeingabe, indem Sie anstelle eines neuen Wortes ein »q« eintippen. Später können Sie die automatische Rätselerzeugung jederzeit unterbrechen und mit F7 wieder in den Handmodus zurückkehren.
Im Wortfeld stehen nun ein oder mehrere Wörter, die als Startpunkte für andere Wörter dienen. Senkrechte Eintragungen sind weiß und waagerechte gelb gefärbt.
Bleibt nur die Angabe, welcher auf Diskette gespeicherte Wortschatz als erstes geladen werden soll (Zeile 37). Dabei können Sie sich mit »$« auch das Inhaltsverzeichnis der Diskette ansehen, für den Fall, daß Ihnen der Name eines Wortschatzes entfallen ist.
Nach erfolgreichem Laden des ersten Wortschatzes beginnt nun die automatische Rätselerzeugung (Hauptschleife Zeile 40—99). Zunächst überraschend schnell füllt sich das Wortfeld mit zufällig plazierten und gekreuzten Wörtern. Dieser Vorgang wird von der Maschinenroutine gesteuert. Auf die genaue Arbeitsweise dieses Programmteiles gehe ich noch gesondert ein. Links oben auf dem Bildschirm erscheint die Anzahl der Wörter, die bereits eingetragen sind (maximal 255 sind möglich) und daneben die momentane prozentuale Größe des noch zur Verfügung stehenden Wortschatzes im Speicher.
Bei jeder Eintragung wird die Liste der Kreuzwörter gekürzt und das benutzte Wort aus der Liste gestrichen. Dies geschieht durch Vertauschen der Stringvektoren des zu streichenden Wortes und des letzten Wortes im Array (Zeile 300—399). Diese Methode wurde gewählt, um die Bildung von neuen Strings im Speicher zu vermeiden und der schrecklich langsamen Garbage-Collection aus dem Wege zu gehen.
Während der Rätselerzeugung können Sie sich in Ruhe überlegen, ob Sie ein automatisches Nachladen von Wortschätzen gestatten wollen oder nicht. In der rechten Bildhälfte ist inzwischen die Belegung der Funktionstasten zu sehen, und mit der F6-Taste schalten Sie die Autolader-Option ein oder aus. Erscheint »Aus« im F6-Tastenfeld, ist das Nachladen gesperrt.
Die Maschinenroutine sucht derweil ständig nach passenden Stellen im Wortfeld. Dieser Vorgang kann im Prinzip endlos sein, da irgendwann natürlich kein geeignetes Wort mehr zu finden ist. Aus diesem Grund hat das Programm eine »Geduld-Schwelle«, eine Anzahl von Suchversuchen, innerhalb derer ein passendes Wort gefunden werden muß. Ist die Versuchszahl ohne Erfolg abgelaufen, geht das Programm davon aus, daß der Wortschatz nicht mehr ausreicht. Diese »Geduld-Schwelle« können Sie in Zeile 964 selbst bestimmen.
Bevor allerdings in der obersten Bildzeile die Meldung »Wortschatz ungenügend« erscheint (Zeile 64/Unterprogramm 110—158), hebt das Programm noch die »Blausperre« auf (Zeile 66). Dieses Flag hat dem Maschinenprogramm bisher mitgeteilt, daß nur dann eine Eintragung erlaubt ist, wenn dabei auch ein blaues, unbesetztes Feld abgedeckt wird. Eine Maßnahme, um das Rätsel möglichst dicht zu packen. Ab sofort ist also auch das Einpassen eines Wortes nur auf besetzten Feldern möglich. Läßt sich auch jetzt kein Wort mehr finden, erscheint endgültig der Hinweis auf mangelnde Wortauswahl. Wenn Sie das »Autoladen« zugelassen haben, wird nun der Folgewortschatz, falls vorhanden, gelesen und das Spiel beginnt von Neuem. Selbstverständlich ist auch das Laden von Wortdateien vor Ablauf der »Geduld-Schwelle« machbar. Dazu dient die Fl-Taste. Aber Vorsicht, auf die Gefahr, daß Sie einen bereits verbrauchten Wortschatz nochmal laden, müssen Sie schon selbst achten.
Es dauert gar nicht so lange, dann ist das Wortfeld so dicht gepackt, daß der Maschinenroutine keine Eintragung mehr gelingt. Jetzt sind Sie gefordert, und mit der F7-Taste wählen Sie die Handeingabe an. Genau wie bei der Eintragung der ersten Startwörter können Sie Ihre »Lückenfüller« positionieren und die Fragestellung dazu eingeben.
Zufrieden mit Ihrer Arbeit (hoffentlich!) bleibt nur noch der Ausdruck des Rätsels. Mit F4 wird er gestartet. Das Unterprogramm für die Druckausgabe nimmt im Programm den weitaus größten Platz ein (Zeile 740—914). Ich verwende einen Epson RX-80-Drucker, der mit Hilfe einer speziellen Treibersoftware (Epson Software-Interface) auch CBM-Sonderzeichen drucken kann. Dazu muß eine unübliche Geräteadresse (6) angegeben werden (Zeile 761 und 900). Sollten Sie also einen CBM-grafikfähigen Drucker am IEC-Bus betreiben, tauschen Sie diese Adresse gegen die gewohnte »4« (im Listing schon geändert).
Auch die Druckerinitialisierung ist von Drucker zu Drucker verschieden (Zeilen 754—758). Achten Sie darauf, daß Ihr Drucker hier folgende Einstellung erhält:
- Zeilenabstand = 0
- CBM-Grafikmodus
- Startposition des Druckkopfes = lr (Linker Rand, kann in Zeile 946 geändert werden).
Für den Ausdruck der Fragestellung wird der RX80 im Engschriftmodus versetzt, um Platz zu sparen (Zeile 824—827). Auf diesen Effekt können Sie natürlich verzichten, müssen dann aber die Zeilenlänge (cz, in Zeile 948) ändern, da der Ausdruck vom Programm mit Randausgleich versehen wird (Zeile 847—889).
Nun wie versprochen zum Maschinenprogramm, kurz genannt »Such« (Bild 4 und 5). Diese Routine liegt im Bereich $C000/49152, wo sie gut gegen überschreiben durch Basic geschützt ist. Der Einsprung erfolgt über den USR-Vektor (definiert in Zeile 931 bis 932), das heißt es findet eine Parameterübergabe zwischen Basic und Maschinenroutine statt. Basic übergibt in »dl« die Anzahl der Versuche, die die Routine durchlaufen sollen (Zeile 44). Mit der Rückkehr aus der Routine wird der Variablen »u« ein Wert zwischen 1 und 4 zugewiesen. Aus dem Wert von »u« kann also auf die Ursache für den Abbruch der Routine geschlossen werden:
- u = 1; eine Taste ist betätigt worden.
- u = 2; die Suche nach einem passenden Kreuzwort war vergeblich.
- u = 3; ein Wort wurde gefunden und in das Wortfeld eingetragen.
- u = 4; die maximale Anzahl (255) von eingetragenen Kreuzwörtern ist erreicht; keine weitere Eintragung möglich.
Das Rahmenprogramm kann jetzt entsprechend reagieren und zum Beispiel im Falle u = 3 das benutzte Wort aus der Wortliste streichen. Im Falle einer Eintragung (von Hand oder automatisch) wird das Wort nicht nur in den Bildspeicher eingesetzt, sondern es werden auch einige weitere Informationen abgelegt:
- Eintragung im »Wortbeginn/ende«-Speicher (50176 bis 50575); hier wird vermerkt, ob ein Rätselfeld den Start- oder Endpunkt eines Kreuzwortes repräsentiert. Der Speicher ist, wie die folgenden auch, in 20 Zeilen mit je 20 Positionen (Speicherstellen) aufgeteilt. Das linke Halbbyte (4 Bit) einer Speicherstelle trägt die Informationen über senkrechte, das rechte Halbbyte über waagerechte Start/Endpositionen. Das 1. Bit im Halbbyte wird für Endpunkte gesetzt, das 3. Bit für Startpunkte. Diese Informationen werden später bei der Ausgabe des Rätsels auf dem Drucker benötigt, um an den richtigen Stellen die Nummer der zugehörigen Fragestellung eintragen zu können.
- Eintragungen im »Senkrecht«-Speicher (50576 bis 50975); in dieser Speichermatrix werden die Ordnungsnummern der Fragestellungen für senkrechte Rätselwörter abgelegt. Bei der Druckausgabe wird diese Matrix abgefragt (Zeile 773 bis 777), um die Nummer der Fragestellung im entsprechenden Startfeld einzusetzen.
- Eintragung im »Waagerecht«-Speicher (50976 bis 51375), wie unter b) Zeile 796 bis 800).
Um die Speicherinhalte vor dem Start des Rätselprogramms zu löschen, springt man die Routine mit »sys 50016« an (Zeile 937).
Nun zur Arbeitsweise der Routine während der automatischen Rätselerzeugung. Zunächst muß das Maschinenprogramm erst einmal wissen, ob es wegen einer Handeintragung angesprungen wurde oder zur automatischen Wortsuche. Dazu liest die Routine die Speicherstelle 26 aus. Ist das Ergebnis Null, wird in den Automodus verzweigt. Andernfalls wird in 26 die Länge des von Hand eingetragenen Wortes übergeben (siehe Zeile 662 bis 663). Die Routine braucht dann nur den Paß des Wortes zu überprüfen und bei korrekter Eintragung ins Basic zurückzukehren. Paßt das Wort allerdings nicht, verfällt die Routine in den Automodus. Das Maschinenprogramm durchläuft im Automodus eine Schleife, die zunächst durch Auslesen des Rauschgenerators im Soundchip ein Wort aus dem Wortschatz per Zufall bestimmt. Dann erfolgt auf die gleiche Weise die Auswahl eines Startpunktes im Bildspeicher. Ist dieser Punkt nicht geeignet für eine Eintragung, wird Zeile für Zeile des Wortfeldes nach einer Alternative gesucht. Im Falle eines Treffers startet der Wortvergleich. Das gewählte Wort wird mit dem Inhalt des Bildspeichers auf Übereinstimmung geprüft. Paßt es nicht, kommt das nächste Wort aus dem Wortschatz-Array an die Reihe. Bei Erfolg kehrt »Such« ins Basic zurück, wenn nicht, beginnt die Schleife von Neuem.
Damit der Zugriff auf das Array klappt, muß es nur als erstes im Basic-Programm definiert worden sein (Zeile 925). »Primitiv« werden Sie vielleicht anmerken. Richtig, aber Computer sind nun mal (sehr) schnelle Idioten.
(Gert Büttgenbach/gk)clr | = Shift Clear/Home-Taste | rvon | = Revers on |
home | = Home-Taste | rvof | = Revers off |
cyan | = Control und 4 | crsr | = Cursor rechts |
whit | = Control und 2 | crsl | = Cursor links (crsl*28 = 28 mal Cursor links) |
red | = Control und 3 | crsd | = Cursor unten |
Ein reverses »Z« bedeutet die Farbe Hellblau = Commodore-Taste und 7.