\documentclass[ngerman]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \setcounter{secnumdepth}{0} \setcounter{tocdepth}{0} \usepackage{multicol} \usepackage{babel} \makeatother \begin{document} \title{Forth erzeugt automatisch Hexadoku\discretionary{–}{}{–}Rätsel\discretionary{–}{}{–}Vorgaben} \author{Fred Behringer} \maketitle \newcommand{\Def}[1]{\emph{#1}} \newcommand{\Code}[1]{{\ttfamily #1}} \newcommand{\qed}{\hfill$\circ$} \newcommand{\ssp}{\discretionary{}{}{}\,} \newcommand{\emphb}[1]{\emph{#1}} \begin{abstract} %Zusammenfassung Bei Sudoku (Vorstufe zu Hexadoku) werden üblicherweise etwa 30 Elemente vorgegeben. Diese können nicht beliebig gewählt werden. Sie müssen \emph{zulässig} sein, d.h., aus einer \emph{zulässigen} Gesamtmatrix stammen. Es soll eine Analyse darüber versucht werden, wie man es (mit Hilfe von Forth) schafft, praktisch beliebig viele voneinander verschiedene zulässige Hexadoku--Rätsel zu erzeugen. \emph{Erzeugen}, als Vorgabeschema, \emphb{nicht} unbedingt schon \emphb{lösen!} Allerdings soll auch über das (schnelle) Lösen gesprochen werden, und zwar bei einer extrem spärlich verteilten geringen Anzahl von vorgegebenen Elementen. \end{abstract} \begin{multicols}{2} \section{Bedienungsschnellanleitung} Dinge, die in dieser Schnellanleitung noch unklar bleiben, werden, so hoffe ich, aus dem eigentlichen Textteil dieses Artikels heraus klarer (man fange am besten mit {\bf Einleitung und Ziel} an, zu lesen). Die Eingabe \Code{hexa} \key{ret} liefert (auf dem Bildschirm) beliebig viele (vom Programm \emph{zufällig} ausgewählte) Hexadoku--Vorgaben, pro Knopfdruck (\key{ret}) je eine. Die vorherige Eingabe \Code{loes? on} \key{ret} liefert, solange sie nicht durch \Code{loes? off} \key{ret} umgestellt wurde, neben der Vorgabematrix jeweils auch immer die zugehörige zulässige Matrix (die \emph{Lösung}). Voreingestellt ist \Code{loes? on}. Ausgangspunkt im Hauptprogramm \Code{hexa} ist die \emph{kanonische Matrix} (siehe unten). Schon beim ersten Weiterschreiten (nach eingeleitetem \Code{hexa} \key{ret}) ist das Tableau (das Feld \Code{matrix}) völlig undurchsichtig geworden. Von der ursprünglich durch \Code{kanon} systematisch aufgebauten zulässigen \Code{matrix} ist nichts erkennbar Systematisches mehr übrig geblieben. Das Weiterschreiten (von \emph{zulässiger} \Code{matrix} zu \emph{zulässiger} \Code{matrix}) geschieht über einen beliebigen Tastendruck (unter Aussparung der Returntaste). Den Erzeugungsprozess zum Aufbau von zulässigen Matrizen verlassen kann man mit der Returntaste oder mit \key{q} oder mit \key{Q}. \key{q} oder \key{Q} ist als Hommage an MinForth (siehe weiter unten unter {\bf Forth--Programme}) gedacht. Kein Autor ist gegen Denk-- oder Programmierfehler gefeit: Es könnten beim Benutzer nach vielen Schritten im \Code{hexa}--Prozess Zweifel an der immer noch vorliegenden Zulässigkeit von \Code{matrix} aufkommen. Man breche den Prozess über die Returntaste ab und prüfe die gerade erreichte \Code{matrix} über \Code{mok?} \key{ret}. Natürlich liegt hier ein Teufelskreis vor: Für diese Prüfung muss man sich auf das Prüfprogramm \Code{mok?} verlassen können. Das lässt sich aber durch eine einmalige strenge logische Überlegung ein für alle Mal erledigen. Das Hauptprogramm \Code{hexa} liefert (zumeist jedenfalls) eine reproduzierbare Serie von Ergebnissen. Das ist nicht weiter schlimm, da man ja den Prozess \Code{hexa} und den damit verbundenen Pseudozufallsprozess beliebig weit forttreiben kann, bevor man an eine Übernahme der Ergebnisse (der gelieferten Rätselvorgaben) denkt. Man kann aber auch das Programm \Code{hexa} umformulieren und es von der (an sich beliebig eingebbaren) Anfangszahl für den Pseudozufallsprozess (im Programm habe ich 2000 gewählt) abhängig werden lassen. (Man beachte auch das unter {\bf Forth--Programme} über MinForth Gesagte.) Voreingestellter Wert für die Abfragevariable \Code{kanon?} ist \Code{kanon? on} . Stellt man auf \Code{kanon? off} um und leitet erst dann den Erzeugungsprozess per \Code{hexa} ein, so wird man sich wundern: Schon die erste Matrix ist dann im Allgemeinen nicht zulässig (mit mok? nachprüfen!). Zum ordnungsgemäßen Start braucht der Erzeugungsprozess die Einstellung \Code{kanon? on} . Es wird dann mit der (zulässigen) kanonischen Matrix begonnen und alle nachfolgenden Matrizen sind ebenfalls zulässig. Bricht man den Erzeugungsprozess dann aber irgendwann durch Drücken der Returntaste ab und gibt wieder \Code{hexa} \key{ret} ein, so wird wieder mit der kanonischen Matrix gestartet. Will man das (was durchaus wünschenswert sein kann) verhindern, so kann man den Erzeugungsprozess über die Returntaste kurz unterbrechen und dann \Code{kanon? off} \key{ret} eingeben. Wenn man daraufhin wieder \Code{hexa} \key{ret} eingibt, so fährt der Erzeugungsprozess mit der bis dato bereits erreichten (zulässigen) Matrix fort. An Bildschirm--Anzeigemöglichkeiten aus dem Stand heraus (außerhalb eines eingeleiteten \Code{hexa}) stehen zur Verfügung: \Code{.m} für die momentane Matrix (Rätsellösung), \Code{.v} für die zugehörige Vorgabematrix (zu stellendes Rätsel) und \Code{.m\&v} für beides zusammen. Mit \Code{cpy-m} kann man die Matrix auf den Platz für die Vorgabematrix kopieren, mit \Code{xch-m} tauscht man Matrix und Vorgabematrix gegeneinander aus. Wegen einer praktischen Inbetriebnahme unter verschiedenen Forth--Systemen sehe man weiter unten im Abschnitt {\bf Forth--Programme} nach. \section{Einleitung und Ziel} Magische Quadrate ($n{\times} n$--Matrizen) faszinieren den Betrachter seit Menschengedenken. Nicht immer ist es die Summe der (aus natürlichen Zahlen bestehenden) Elemente, die über Zeilen, Spalten und Diagonalen hinweg konstant bleiben soll. Verlangt man, dass in einer $9{\times} 9$--Matrix jede Ziffer von 1 bis 9 in jeder Zeile, in jeder Spalte und in jeder $3{\times} 3$--Teilmatrix genau einmal auftritt, dann hat man es mit einer Sudoku--Matrix zu tun. Sudokus (su = Ziffer, doku = einmal) sind seit einigen Jahren erst in Amerika, dann in Japan (daher der Name) und jetzt auch bei uns in Deutschland beliebt geworden. Ein neuer Volkssport, sozusagen: Eine gewisse Anzahl von Elementen (meist um die 30 herum) werden vorgegeben, der Rest muss \emph{erraten} werden. Sudoku--Rätselsammlungen (mit durchschnittlich 200 Rätseln und auf den letzten Seiten angegebenen Lösungen) wurden zuhauf fünfeuroweise auf den Markt geworfen. Die Zeitschrift Elektor (und in Holland deren Mutterblatt Elektuur) hat ihre Leser mit dem Begriff \emph{Hexadoku} begeistert: Eine $16{\times} 16$--Matrix, die in sechzehn $4{\times} 4$--Teilmatrizen aufgeteilt ist. (\emph{Aufteilung} heißt Überdeckung mit $4{\times} 4$--Teilmatrizen, die mit den Elementen der Gesamtmatrix auskommt.) Vorgegeben ist eine gewisse Anzahl von Elementen, der Rest soll \emph{erraten} (irgendwie gefunden) werden. In jeder Zeile, in jeder Spalte und in jedem Teilquadrat soll jede Hexadezimalziffer von 0 bis F genau einmal vorkommen (hier also auch die \emphb{0,} bei \emphb{Sudoku} fängt es \emphb{erst bei 1} an.) Martin Bitter hat sofort erkannt, dass Sudoku (besser: Hexadoku) ein willkommenes Mittel sein kann, den lernschwachen unter den Schülern seiner Integrativen Schule spielerisch das logische Denken beizubringen. Er hat im VD--Heft 1/2006 ein Forth--Programm zur Lösungshilfe veröffentlicht. (Aus Amerika hört man von \emph{unserem Reporter} Henry Vinerts, dass John Rible, erwähnt in comp.lang.forth, auf einem kürzlichen SVFIG--Treffen über ein vollständiges Lösungsverfahren in Forth vorgetragen hat. John Rible stützt seine Lösung auf einen Rekursive--Backtracking--Algorithmus von Robert Spykerman, den John um einen Brute--Force--Backtracking--Solver ergänzt hat. Bernd Paysan hat in einer persönlichen Mitteilung an das Redaktions--Team der VD sofort nach Bekanntwerden von Martins Anstrengungen angedeutet, wie ein vollständiges Lösungsverfahren aussehen kann. Fred Behringer hat das Hexadoku--Rätsel aus dem Elektor--Heft 2/2006 mit Bleistift, Papier und Radiergummi gelöst und damit den Elektor--Hauptpreis, das E--Blocks--Starter--Kit--Professional, gewonnen.) In den Sudoku--Büchern werden die \emph{Rätsel} mit \emphb{wenig}er \emphb{Vorgaben} als \emphb{schwer} bezeichnet, die mit \emphb{mehr Vorgaben} als \emphb{leicht}er. \emphb{Das kann man, so behaupte ich, so generell nicht sagen.} Die kleinste Anzahl von Vorgaben ist 0. Das müsste dann also ein schweres Rätsel sein. \emphb{Null} liefert aber ein \emphb{ganz ganz leicht}es Spiel. Ich gebe dafür gleich anschließend eine \emph{Lösung} an (\emphb{eine} Lösung --- mit der Eindeutigkeitsfrage müsste man sich noch gesondert befassen), die ich als Ausgangspunkt für weitere Überlegungen nehmen und als \emph{kanonisch} bezeichnen möchte. Matrizen mit einem \emphb{einzigen} vorgegebenen Element, das sieht man schnell ein, lassen sich \emphb{ebenfalls ganz einfach} behandeln. Zwei vorgegebene Elemente bereiten keine Schwierigkeit. Vier vorgegebene Elemente, das wird man sich mit dem weiter unten Gesagten ebenfalls leicht überlegen können, liefern verhältnismäßig schnell eine Lösung, wenn sie sich gleichmäßig auf vier waagerecht angeordnete, vier senkrecht angeordnete oder vier diagonal angeordnete Teilmatrizen verteilen. Ein bisschen Überlegung braucht man dazu allerdings schon. Dass Vorgaben nicht willkürlich gemacht werden können, ist klar: Zweimal die 1 in ein und derselben Zeile oder in ein und derselben Spalte wäre ja beispielsweise schon eine unzulässige Vorgabe. \begin{description} \item[Frage 1:] Wenige Vorgaben sind leicht, viele Vorgaben sind ebenfalls leicht. Gibt es eine mittlere Vorgabenbelegung, die einer schwersten Schwierigkeitsstufe zugeordnet werden kann? \end{description} Ich erwähne diese Frage nur, weil sie mit der kanonischen Belegung eng zusammenhängt. Auch will ich mir über vollständige, computerübertragbare Lösungsverfahren (Algorithmen) keine Gedanken machen. Die Eindeutigkeitsfrage (Bedingungen an die Vorgaben, welche eine eindeutige Lösung garantieren) wäre ebenfalls interessant. Was mich hier interessiert aber ist die folgende \begin{description} \item[Frage 2:] Wie kann man automatisch eine (im praktischen Sinne) beliebige Anzahl von verschiedenen Hexadoku--Rätseln erzeugen? \end{description} (Martin möchte sich ja schließlich nicht jede Woche ein neues Hexadoku--Rätselbuch, so es solche überhaupt je geben wird, kaufen müssen. Dass man nach erfolgreicher Beantwortung der obigen Frage den Computer dazu befähigen könnte, automatisch, ohne Zutun des Menschen, Bücher (Hexadoku--Rätselbücher) zu schreiben und auf den Markt zu werfen, ist ein interessanter und sicher diskutierwürdiger Nebeneffekt. Haben wir damit die KI--Frage gelöst (der Computer als Bücherschreiber) und eine erfolgversprechende KI--Begriffsbestimmung gefunden?) \begin{figure*} \begin{center} \begin{small} \renewcommand{\arraystretch}{1.5} \begin{tabular}{|c|c|c|c||c|c|c|c||c|c|c|c||c|c|c|c|} \hline 0&1&2&3&4&5&6&7&8&9&A&B&C&D&E&F\\ \hline 4&5&6&7&8&9&A&B&C&D&E&F&0&1&2&3\\ \hline 8&9&A&B&C&D&E&F&0&1&2&3&4&5&6&7\\ \hline C&D&E&F&0&1&2&3&4&5&6&7&8&9&A&B\\ \hline \hline 1&2&3&4&5&6&7&8&9&A&B&C&D&E&F&0\\ \hline 5&6&7&8&9&A&B&C&D&E&F&0&1&2&3&4\\ \hline 9&A&B&C&D&E&F&0&1&2&3&4&5&6&7&8\\ \hline D&E&F&0&1&2&3&4&5&6&7&8&9&A&B&C\\ \hline \hline 2&3&4&5&6&7&8&9&A&B&C&D&E&F&0&1\\ \hline 6&7&8&9&A&B&C&D&E&F&0&1&2&3&4&5\\ \hline A&B&C&D&E&F&0&1&2&3&4&5&6&7&8&9\\ \hline E&F&0&1&2&3&4&5&6&7&8&9&A&B&C&D\\ \hline \hline 3&4&5&6&7&8&9&A&B&C&D&E&F&0&1&2\\ \hline 7&8&9&A&B&C&D&E&F&0&1&2&3&4&5&6\\ \hline B&C&D&E&F&0&1&2&3&4&5&6&7&8&9&A\\ \hline F&0&1&2&3&4&5&6&7&8&9&A&B&C&D&E\\ \hline \end{tabular} \end{small} \caption{\label{kanonischeMatrix}Die kanonische Matrix} \end{center} \end{figure*} \section{Definitionen und Bezeichnungen} \Def{Matrix} sei eine abkürzende Bezeichnung für eine $16{\times} 16$--Matrix mit den Hexadezimalziffern 0 bis F als \Def{Elementen}. Zeilen-- und Spaltenzählungen \emphb{beginnen bei 0!} Matrizen seien aufgeteilt in $4{\times} 4$--Teilmatrizen. Jede solche Teilmatrix heiße \Def{Viererquadrat}. Die Viererquadrate einer Matrix seien \emph{blockzeilenweise} mit 0 bis F durchnummeriert: Das Viererquadrat 9 ist von links gesehen das zweite (\emph{Längsstreifen} 1), von oben gesehen das dritte (\emph{Querstreifen} 2) Quadrat. Auch die Zählung der Viererquadrate \emphb{beginnt bei 0!} Von \Def{Reihe} sprechen wir, wenn wir uns nicht genau festlegen wollen, ob wir Zeile oder Spalte meinen. Eine waagerechte Anordnung von vier Viererquadraten möge \Def{Querstreifen} heißen. Eine senkrechte Anordnung von vier Viererquadraten heiße \Def{Längsstreifen}. Soll es offen bleiben, ob Quer-- oder Längsstreifen gemeint ist, sprechen wir einfach von \Def{Streifen}. Eine \Def{zulässige Matrix} ist eine Matrix (im obigen Sinne), bei welcher in jeder Zeile, in jeder Spalte und in jedem Viererquadrat jede der \Def{Hex}(adezimal)\Def{ziffern} von 0 bis F genau einmal vorkommt. Elemente, die (noch) nicht bekannt sind, bezeichnen wir mit dem \Def{Leerzeichen} (Space). (Space tritt als Platzhalter, als variables Element, als Variable auf.) Ein \Def{zulässiger Streifen} ist ein Streifen einer zulässigen Matrix. Eine \Def{Vorbelegung} ist eine willkürliche Auswahl von Elementen einer Matrix, deren restliche Elemente mit Space (20h) gekennzeichnet sind. \Def{Eine zulässige Vorbelegung} ist eine Vorbelegung, die aus (mindestens) einer zulässigen Matrix durch Weglassung von Elementen (Belegung mit Space) hervorgeht. Eine \Def{Transformation} ist (hier) eine (eineindeutige, also bijektive) Umordnung der Elemente einer Matrix. Eine \Def{zulässige Transformation} ist eine Transformation, die eine zulässige Matrix in eine zulässige Matrix überführt. In der vorliegenden Arbeit geht es um zulässige Transformationen, die sich aus beliebig zusammengewürfelten zulässigen Transformationen zusammensetzen. \section{Feststellungen} Die meisten der jetzt folgenden Feststellungen sind leicht einzusehen und benötigen keinen Beweis. Bei anderen reicht eine kurze Erläuterung oder ein Beispiel. Die Feststellungen lassen sich in zwei Klassen einteilen, allgemeine Feststellungen (die für beliebige Belegungen gelten) und solche, die sich (wie bei \emph{kanonischen} Matrizen, siehe unten) auf eine bestimmte, festverankerte Belegung beziehen. Letztere können selbstverständlich mit Auge und Gehirn (mit Bleistift und Papier) auf Richtigkeit überprüft werden: Das Auge braucht \emph{nur} 256 Elemente zu überfliegen. Aber gerade weil die Überprüfung der sehr anspruchslosen Regeln in den durchaus überschaubaren Matrizen so einfach ist, lässt sich das auch \emph{per Knopfdruck} überaus leicht erledigen. {%\bf Ich gebe weiter unten ein Forth--Programm an, welches nicht nur die zufallsmäßige Erzeugung von Hexadokus erledigt, sondern auch die Überprüfung auf Zulässigkeit (einer irgendwie per Hand geänderten zulässigen Matrix).} \begin{description} \item[Feststellung 1:] In einer zulässigen Vorbelegung ist in jeder Zeile und in jeder Spalte keine der auftretenden Ziffern mehr als einmal vertreten. \item[Feststellung 2:] Eine zulässige Matrix bleibt zulässig, wenn in einem Querstreifen zwei Zeilen vertauscht werden. \item[Feststellung 3:] Eine zulässige Matrix bleibt zulässig, wenn in einem Längsstreifen zwei Spalten vertauscht werden. \item[Feststellung 4:] Eine zulässige Matrix bleibt zulässig, wenn in ihr zwei Querstreifen vertauscht werden. \item[Feststellung 5:] Eine zulässige Matrix bleibt zulässig, wenn in ihr zwei Längsstreifen vertauscht werden. \end{description} Vertauscht man generell in einer Matrix $M$ deren Zeilen und Spalten, dann erhält man bekanntlich die zu $M$ \Def{transponierte} Matrix $M^T$. \begin{description} \item[Feststellung 6:] Bekanntlich ist $M^{TT} = M$. \item[Feststellung 7:] Ist $M$ eine Matrix im obigen Sinne und $V$ das Viererquadrat $n$ mit den (zeilenweise zu lesenden) Elementen 0,\ssp 1,\ssp 2,\ssp 3,\ssp 4,\ssp 5,\ssp 6,\ssp 7,\ssp 8,\ssp 9,\ssp A,\ssp B,\ssp C,\ssp D,\ssp E,\ssp F, dann ist das Viererquadrat $m$ mit den Elementen 0,\ssp 4,\ssp 8,\ssp C,\ssp 1,\ssp 5,\ssp 9,\ssp D,\ssp 2,\ssp 6,\ssp A,\ssp E,\ssp 3,\ssp 7,\ssp B,\ssp F von $M^T$ die Transponierte $V^T$ von $V$. \item[Beweis:] Betrachtung der in üblicher Weise doppeltindizierten Elemente von $M$ und Auszählung der Indizes: Vertauschung von Zeilen und Spalten in der Gesamtmatrix $M$ läuft auf eine Vertauschung von Zeilen und Spalten auch in den Viererquadraten hinaus. \qed \item[Feststellung 8:] Die Transponierte einer zulässigen Matrix ist eine zulässige Matrix. \item[Beweis:] Mit den Zeilen/Spalten einer zulässigen Matrix erfüllen auch die Spalten/Zeilen ihrer Transponierten die Kriterien der Zulässigkeit. Alles Weitere folgt aus Feststellung 7. \qed \end{description} \section{Generierverfahren} \begin{description} \item[Feststellung 9:] Die Matrix (im obigen Sinne) in Abbildung \ref{kanonischeMatrix} (Seite \pageref{kanonischeMatrix}) ist eine zulässige Matrix. Wir wollen sie wegen ihres einfachen Aufbaus die \Def{kanonische Matrix} nennen. \item[Beweis:] Einfach durchprobieren, Zeile für Zeile, Spalte für Spalte, Viererquadrat für Viererquadrat! \qed \end{description} Diese Matrix baut sich wie folgt auf: Die (Hex--)Ziffern der ersten Zeile (Zeile 0) in natürlicher Reihenfolge hinschreiben. Eine Kopie der so gebildeten ersten Zeile in die zweite Zeile (Zeile 1) schreiben und diese dann um 4 Spalten nach links rotieren (was links herausfällt, rechts anfügen). Eine Kopie der so gebildeten zweiten Zeile (Zeile 1) in die dritte Zeile (Zeile 2) schreiben und diese wieder um 4 Spalten nach links rotieren lassen. Und schließlich die dritte Zeile (Zeile 2) in die vierte Zeile (Zeile 3) kopieren und die vierte Zeile (Zeile 3) um vier Spalten nach links rotieren. Damit ist der erste Querstreifen (Querstreifen 0) der aufzubauenden kanonischen Matrix gebildet. In die fünfte Zeile (Zeile 4) schreibe man eine Kopie der ersten Zeile (Zeile 0) und rotiere sie um 1 nach links (um 1, nicht um 4!). Dann folgerichtig weiter mit der sechsten, siebten und achten Zeile (jeweils die vorhergehende kopieren und um 4 Spalten nach links rotieren lassen). Bei der neunten Zeile (Zeile 8) wiederum die fünfte (nicht die erste!) nehmen und um 1 Spalte nach links rotieren. Und so weiter und so fort. \begin{description} \item[Feststellung 10:] Aus der kanonischen Matrix aus Feststellung 9 erhält man wieder eine Art kanonischer Matrix (einfach aufgebaut und zulässig), wenn man in Feststellung 9 das Wort links durch das Wort rechts ersetzt. Ich will die zulässige Matrix aus Feststellung 9 daher auch \Def{linkskanonisch} und die, um die es in der vorliegenden Feststellung 10 geht, \Def{rechtskanonisch} nennen. \item[Beweis:] Hinschreiben und Zulässigkeit nachprüfen! \qed \item[Feststellung 11:] Aus einer zulässigen Matrix erhält man wieder eine zulässige Matrix, wenn man die Zeilen oder/und die Spalten in umgekehrter Reihenfolge hinschreibt. \item[Beweis:] Feststellungen 2 bis 5. \emph{Spalten in umgekehrter Reihenfolge hinschreiben} ist dasselbe wie \emph{äußerste Spalten miteinander vertauschen, dann zweitäußerste} usw. Entsprechend für Zeilen. \qed \item[Bezeichnung:] Geht man von der kanonischen Matrix aus und schreibt die Zeilen (Spalten) wie in Feststellung 11 invertiert hin, dann wollen wir die resultierende Matrix die \Def{zeileninvertierte} (\Def{spalteninvertierte}) \Def{kanonische Matrix} nennen. \end{description} \section{Randomisierung} \begin{description} \item[Anzahl der Vorgaben:] Bei Sudoku sind etwa 30 Vorgabe--Elemente üblich. Die Zeitschrift \emph{Elektor} hat in ihren Ausgaben vom Januar, Februar, März und April 120, 122, 119, 111 Elemente vorgegeben. 128 Elemente beispielsweise scheint also eine brauchbare Zahl von Vorgaben zu sein. 128 ist genau die Hälfte von 256, der Gesamtzahl an Matrixelementen. Das legt für die Randomisierung eine Zufallsverteilung von \emph{gerade} und \emph{ungerade} nahe. \item[Einsparung eines echten Zufalls:] Man weiß, wie (Pseudo)zufallszahlen zu konstruieren sind, die den bekannten statistischen Verfahren zur Überprüfung auf Gleichverteilung standhalten. Hier ist das aber sicher nicht nötig: Ob gleichverteilt oder nicht, interessiert uns herzlich wenig, Hauptsache, die Lösung (\emphb{eine} Lösung) lässt sich nicht schon aus der Struktur der Vorgabeelemente heraus sofort erraten. Naheliegend ist also die Vorgabe einer Zahl (\emph{Seed}\/), ab der im Programmspeicher die aufeinanderfolgenden Bytes abgefragt und mit 1 geANDet werden. Bei Ergebnis 0 wird das gerade an der Reihe befindliche der parallel dazu laufenden Matrixelemente \emph{gelöscht} (mit Space belegt), bei 1 bleibt es stehen. Das gibt eine ungefähre Vorgabebelegung mit 50\% aller Elemente, also mit etwa 128d Elementen. In gewisser Bandbreite kann man das noch experimentell durch geeignete Wahl der Pseudozufalls--Seed--Zahl (im Programm habe ich willkürlich 2000 gewählt) variieren (es kann ja ganze Strecken im RAM geben, die mit geraden Bytes, z.B. 0, belegt sind). Möglichkeiten, die vorgegebene Anzahl von Elementen zu reduzieren, bestehen darin, dass man \Code{AUSWAHL} (siehe Programm) auf eine schon getroffene Auswahl anwendet, und das vielleicht sogar mehrfach. Man experimentiere! Die Reduzierungsrate lässt sich schwer vorhersagen. Experimente haben jedoch gezeigt, dass schon nach etwa 10 solcher wiederholten \Code{AUSWAHL}en praktisch kein Belegungselement mehr übrig ist. (Man beachte aber auch das unter {\bf Forth--Programme} über MinForth Gesagte!) \end{description} \section{Löseverfahren bei kleiner Zahl von Vorgaben} Ich will nur auf ein paar Lösungs-- und Prüfverfahren eingehen, die bei 30 (Sudoku) oder 128 (Hexadoku) vorgegebenen Elementen der entsprechenden \Code{MATRIX} nicht mehr anwendbar oder, da nur in Ausnahmefällen auftretend, nicht mehr so wichtig sind. Generelle Lösungsverfahren, so interessant sie sein mögen, sollen hier nicht angegangen werden. \begin{description} \item[Feststellung 12:] Wird in einer Matrix (im obigen Sinne) ein (und nur ein) Element vorgegeben, dann lässt dieses sich (zumindest wie folgt) zu einer zulässigen Matrix ergänzen: O.B.d.A. möge das vorgegebene Element den Wert 7 haben und im Viererquadrat $m$ liegen. Man betrachte die kanonische Matrix.\\ Vielleicht stimmen Zeile und Spalte des vorgegebenen Elementes genau mit jenem Element im Viererquadrat $m$ überein, das den Wert 7 hat. Wenn nicht, dann:\\ Es muss im Viererquadrat $m$ genau ein Element mit dem Wert 7 geben. Es möge in Zeile $i$ und Spalte $j$ liegen.\\ Man vertausche die Zeile des vorgebenen Elementes mit Zeile $i$ und die Spalte mit Spalte $j$. Dann ist nach Feststellung 2 und 3 alles erledigt. \qed \item[Feststellung 13:] Die Lösung von Feststellung 12 ist alles andere als eindeutig, da ja schon die rechtskanonische, die zeileninvertierte kanonische, die spalteninvertierte kanonische Matrix und schließlich die Transponierte aller genannten Matrizen offensichtlich unterschiedliche Lösungen liefern. \item[Feststellung 14:] Hat man bis zu vier vorgegebene Elemente, die sich gleichmäßig so verteilen, dass in den zugehörigen Längs-- und Querstreifen kein weiteres Vorgabeelement liegt (beispielsweise bei Diagonalanordnung), dann gelangt man zu (mindestens) einer Lösung, wenn man in Bezug auf jedes Vorgabeelement so wie in Feststellung 12 vorgeht. \item[Beweis:] Offensichtlich. Kein Streifenpaar beeinflusst ein anderes Streifenpaar. \qed \end{description} Ist man im unten stehenden Programm mit der Anzahl der Vorbelegungselemente (die man beispielsweise über \Code{VORGABE} erhalten hat) zufrieden, nicht aber mit deren Verteilung (weil sie sich beispielsweise alle in einer Ecke der \Code{MATRIX} zusammenballen), dann kommt man eventuell mit folgender Feststellung weiter. \begin{description} \item[Feststellung 15:] Eine zulässige Vorbelegung liefert wieder eine zulässige Vorbelegung, wenn man auf sie eine zulässige Transformation (siehe {\bf Definitionen und Bezeichnungen}) anwendet. \item[Beweis:] Offensichtlich. Die zulässige Transformation entstammt einer zulässigen Matrix (durch Weglassung von Elementen hervorgerufen). Der Begriff der zulässigen Transformation bezieht sich an sich auf eine zulässige Matrix, ist aber ansonsten eine (wiederholbare) Matrixoperation. Man betrachte statt der zulässigen Vorbelegung (welche Leerelemente enthält, genauer, enthalten kann) die (genauer, eine) zugehörige zulässige Matrix, wende die zulässige Transformation auf ebendiese zulässige Matrix an und ersetze die zuvor irgendwie gekennzeichneten ursprünglichen Leerelemente wieder durch Leerelemente. \qed \item[Feststellung 16:] Nimmt man eine der Hexzahlen $0,4,8$ oder C und addiert sie modulo 10h zu sämtlichen Elementen einer zulässigen Matrix, so erhält man wieder eine zulässige Matrix. \item[Beweis:] Addition modulo 10h einer der genannten Konstanten zu den Hexzahlen 0\dots F führt aus eben diesem Bereich nicht hinaus. (Eine solche Konstantenaddition ist umkehrbar eindeutig.) In jeder Zeile, in jeder Spalte und in jedem Viererquadrat ist eine solche Addition gleichbedeutend mit einer Umordnung der betreffenden Elemente. Die Zulässigkeitsbedingungen bleiben also insgesamt erhalten. \qed \item[Bemerkung 1 zu 16:] Man kann in Feststellung 16 beliebige durch 4 teilbare nichtnegative (Hex--)Zahlen nehmen: 8 + 14 = C mod 10h etc. (Auch negative Hexzahlen tun der Überlegung keinen Abbruch: Beweis!) \item[Bemerkung 2 zu 16:] Zu jeder zulässigen Vorbelegung erhält man unmittelbar drei weitere zulässige Vorbelegungen mit exakt gleichen Vorgabepositionen: Addition modulo 10h von $4,8$ oder C zu sämtlichen Elementen. \item[Feststellung 17:] Bei der Addition modulo 10h von 4 zu sämtlichen Elementen der \emphb{kanonischen} Matrix läuft das Ergebnis auf eine Linksrotation (siehe Programmteil) sämtlicher Zeilen um 4 Spalten hinaus. Das gilt auch, wenn man 4 durch andere durch 4 teilbare Zahlen ersetzt. Insbesondere läuft eine Addition modulo 10h um C Spalten auf eine Rechtsrotation um 4 Spalten hinaus. \item[Beweis:] Anhand der unten stehenden Forth--Programme leicht nachweisbar. \qed \end{description} \begin{figure*} \begin{center} \begin{small} \renewcommand{\arraystretch}{1.5} \begin{tabular}{|c|c|c|c||c|c|c|c||c|c|c|c||c|c|c|c|} \hline 0&1&2&3&4&5&6&7&8&9&A&B&C&D& ~ & ~ \\ \hline 4&5&6&7&8&9&A&B&C&D&E&F&0&1& & \\ \hline 8&9&A&B&C&D&E&F&0&1&2&3&4&5& & \\ \hline C&D&E&F&0&1&2&3&4&5&6&7&8&9& & \\ \hline \hline 1&2&3&4&5&6&7&8&9&A&B&C&D&E& & \\ \hline 5&6&7&8&9&A&B&C&D&E&F&0&1&2& & \\ \hline 9&A&B&C&D&E&F&0&1&2&3&4&5&6& & \\ \hline D&E&F&0&1&2&3&4&5&6&7&8&9&A& & \\ \hline \hline 2&3&4&5&6&7&8&9&A&B&C&D&E&F& & \\ \hline 6&7&8&9&A&B&C&D&E&F&0&1&2&3& & \\ \hline A&B&C&D&E&F&0&1&2&3&4&5&6&7& & \\ \hline E&F&0&1&2&3&4&5&6&7&8&9&A&B& & \\ \hline \hline 3&4&5&6&7&8&9&A&B&C&D&E&F&0& & \\ \hline 7&8&9&A&B&C&D&E&F&0&1&2&3&4& & \\ \hline B&C&D&E&F&0&1&2&3&4&5&6&7&8& & \\ \hline F&0&1&2&3&4&5&6&7&8&9&A&B&C& & \\ \hline \end{tabular} \end{small} \caption{\label{modifizierteMatrix}Die letzten beiden Spalten der kanonischen Matrix werden gelöscht.} \end{center} \end{figure*} \section{Eindeutigkeit und Ausschließung} Bei den in der Zeitschrift Elektor bisher zum \emph{Raten} veröffentlichten Hexadokus handelt es sich ganz offensichtlich um Probleme mit \emphb{eindeutigen} Lösungen, auch wenn das nicht gesagt wird. Wir haben aber schon gesehen, dass eine gefundene Hexadoku--Lösung bei \emphb{wenigen Vorgaben alles andere als eindeutig} zu sein braucht. In den Sudoku--Büchern wird als (unter anderen) mögliches Lösungsverfahren das \emphb{Ausschließungsprinzip} empfohlen. Wo es geht, ist es prima und macht Spaß: Angenommen, in einem Viererquadrat fehlen noch zwei Elemente, 0 und 7. Man setze die 0 im Geiste versuchsweise in das eine der in Frage kommenden beiden Kästchen. Ein schneller Blick möge uns zeigen, dass sowohl in der zugehörigen Zeile wie auch in der zugehörigen Spalte schon eine 0 vorkommt. Also bleibt für das betreffende Kästchen nur die 7 --- und für die 0 gibt es anschließend nur noch eine einzige verbleibende Möglichkeit. Voilà! Wenn es aber immer so einfach wäre, wäre das Hexadokulösen einfach wirklich zu einfach. Die Erfahrung zeigt, dass man auf mittlerer Lösungsstrecke meist mehr als nur eine einzige noch verbleibende Möglichkeit in Betracht ziehen muss. Und aus diesen Möglichkeitenkombinationen ist dann durch logische Überlegung eine einzige Restmöglichkeit herauszufiltern. Das gilt für \emphb{eindeutig gegebene Aufgabenlösungen.} Was aber, wenn es mehr als nur eine Lösung gibt? Die Matrix in Abbildung \ref{modifizierteMatrix}, die sich aus der kanonischen Matrix durch Weglassen der letzten beiden Spalten ergibt, stellt eine durchaus zulässige Vorgabematrix dar, eine Vorgabematrix mit 224 aus 256 Elementebelegungen. So etwas könnte man im Endstadium eines Lösungsprozesses vorfinden. Und der Rest wäre nach allem, was man hört, einfach. \emphb{Wirklich einfach?} Es ist klar, dass es zwei mögliche Lösungen gibt, die eine der beiden Spalten zuerst und dann die andere, oder umgekehrt. Im Beispiel aus Abbildung \ref{modifizierteMatrix} kann man den Rest erraten: Zeile für Zeile erst das kleinere Element, dann das größere, oder umgekehrt. Was aber, wenn man eine ähnlich bis auf zwei Spalten vollbesetzte Vorgabematrix nimmt, die nicht direkt aus der kanonischen Matrix stammt, sondern aus einer zuvor gehörig durchgerüttelten kanonischen Matrix? Man müsste im schlimmsten Fall 2 hoch 16 Kombinationen durchprobieren, in jeder Zeile ein Elementepaar, so oder so herum. Natürlich fällt immer dann eine Möglichkeiten--Zweierpotenz weg, wenn man beim Durchprobieren in ein und derselben Spalte auf eine schon vorhandene Ziffer stößt. Und ebenso natürlich braucht man nacheinander jeweils nur immer ein Viererquadrat des betreffenden Längsstreifens zu betrachten. Aber das tut der Überlegung (mit der sehr großen Zahl von Kombinationsmöglichkeiten) keinen Abbruch. Und was, wenn man (zur Verwirrung des Betrachters) ganz am Anfang erst die letzten beiden Spalten der kanonischen Matrix löscht (wie im Beispiel in Abbildung \ref{modifizierteMatrix}) und dann die Matrix unter Zuhilfenahme von Feststellung 1 bis 14 \emph{durchrüttelt?} Das Wissen um die eventuell vorliegende Lösungseindeutigkeit (ob oder ob nicht) wäre (wie man hier sieht) auch aus praktischen Gründen ein erstrebenswertes Ziel. (Es gibt nichts Praktischeres als eine gute Theorie!) \begin{description} \item[Aufgabe 1:] Lösungsexistenz (Zulässigkeit) vorausgesetzt, gebe man hinreichende oder/und notwendige Kriterien für die Eindeutigkeit der angestrebten Lösung an. \item[Aufgabe 2:] Man lasse die gefundenen Kriterien in ein Forth--Löseprogramm einfließen. \end{description} \section{Forth--Programme} Entwickelt habe ich das gesamte Programm in Turbo--Forth von Marc Petremann (16 Bit) unter DOS 6.2. Die Lauffähigkeit getestet habe ich außerdem auch im Subroutine--Threaded--DPMI--Forth von Rick van Norman (32 Bit, ANS) und in ZF von Tom Zimmer (16 Bit). Das System von Rick van Norman ist ein volles ANS--System. Ich habe in meinem Programm darauf geachtet, dass keine nicht--ANS--konforme Bestandteile verwendet werden. Den für das System von Rick van Norman benötigten DPMI--DOS--Extender erreicht man am besten, indem man mein Programm in der DOS--Umgebung von Windows aufruft. Auf Lauffähigkeit getestet habe ich mein Programm in der genannten Umgebung unter Windows 3.11, Windows 95, Windows 98 und Windows ME. Ich habe darauf geachtet, keines derjenigen ANS--Forth--Worte zu verwenden, die in ZF oder Turbo--Forth nicht akzeptiert werden. Andererseits habe ich keine Worte aus ZF oder Turbo--Forth verwendet, die nicht in ANS enthalten sind. Zur Sicherheit habe ich einige Worte (Beispiele \Code{ON} und \Code{OFF}), auf die Gefahr hin, doppeltgemoppelt zu haben, noch einmal definiert. Insbesondere habe ich mich bei der Ausgabe von \Code{MATRIX} auf den Bildschirm beschränkt. Die Ausgabe in eine Datei oder auf den Drucker wird der geneigte Leser (die geneigte Leserin) mit den Mitteln des von ihm (ihr) vorgezogenen Forth--Systems selbst ergänzen. Entsprechendes gilt für die Eingaben (hier nur direkt über die Tastatur). In Turbo--Forth und in dem Forth--System von Rick van Norman lädt man mein Programm per \Code{include hexadoku.fth} ins (schon aufgerufene) Forth--System, in ZF per \Code{fload hexadoku.fth} . (Natürlich muss dabei das Programm als DOS--Datei unter dem Namen \Code{hexadoku.fth} vorliegen (bei anderer Namensgebung entsprechend anders aufzurufen) und im gleichen Verzeichnis liegen wie das aufrufende Forth--System. Eine Unterscheidung zwischen Groß-- und Kleinschreibung ist in keinem der genannten drei Forth--Systeme nötig.) Mein Programm läuft bestens auch im jeweils abgesicherten Modus und auch, wenn (wie mir unbeabsichtigt passierte) nur der amerikanische Tastaturtreiber eingeschaltet ist (Forth ist sehr genügsam!). Von Anfang an wollte ich die Lauffähigkeit des Programms \Code{hexadoku.fth} auch unter dem unterprogramm--gefädelten ANS--Forth--System \emphb{MinForth} von Andreas Kochenburger testen, das ganz normal schon unter DOS (bei mir 6.2) läuft. Es gelang zunächst nicht herauszufinden, wie \emphb{Include}--Dateien einzuladen sind. Schließlich führte mich ein genaueres Betrachten der von \Code{words} \key{ret} ausgegebenen Liste darauf, dass \Code{fload hexadoku.fth} \key{ret} das erledigt. \Code{fload} scheint kein ANS--Wort zu sein, jedenfalls wird es im bekannten ANS--Forth--Buch von Conklin und Rather nicht genannt. Aber auch schon im ANS--Forth--Dokument X3J14 dpANS--6 --- June 30, 1993 ist es nicht verzeichnet. Man lernt nie aus! Also: Mein Programm läuft auch unter MinForth. MinForth akzeptiert zwar erwartungsgemäß auch \Code{key}, liefert aber dabei für die Returntaste keinen Rückgabewert (0Dh) auf dem Stack. Mit \Code{ekey} wäre es in MinForth gegangen, hätte aber in Turbo--Forth und ZF gestört. Um das Programm im allerletzten Moment ohne Fehlergefahr abzuändern, habe ich mich damit beholfen, dass ich nicht nur die Returntaste für den Aussprung aus \Code{hexa} bereitstellte, sondern auch \key{q} und \key{Q}. Eine weitere Schwierigkeit bei MinForth ist die durch \Code{vorgabe} erzeugte Anzahl der vorgegebenen Elemente. Sie beträgt bei MinForth zwischen 40 und 50. Das ist offenbar zu wenig. Statt 2000 müsste wohl in \Code{hexa} eine geschickt gewählte andere Zahl verwendet werden. Ich überlasse das dem/der Leser/in. Das zeitraubende (time--consuming) Prüfprogramm \Code{mok?} lässt sich in MinForth (auch in der DOS--Box von Windows ME) wirklich sehr viel Zeit. Am schnellsten (praktisch sofort) geht es im System von Rick van Norman (von mir getestet in der Vollbild--DOS--Box von Windows ME). \end{multicols} \begin{quote} \begin{small} \listinginput[1]{1}{2006-02/Hexadoku-Fred.f} \end{small} \end{quote} \end{document}