% Artikel Hexdoku Martin Bitter % Content-Encoding: UTF-8 \begin{document} \title{Hexadoku} \author{Martin Bitter} \maketitle \usepackage{moreverb} \newcommand{\code}[1]{{\tt #1}} \newcommand{\file}[1]{{\tt #1}} \begin{multicols}{2} Auf der Website des Vereins gab es einen Hinweis zu einem interessanten Hardwareprojekt der Zeitschrift Elektor: ein Microkontrollerboard, das der Ausgabe 12/2005 beilag (leider vergriffen). Es gibt Überlegungen, dazu ein Forth zu entwickeln. Diesem Hinweis folgend, klickte ich mich also zu \url{http://www.elektor.de/} --- wirklich interessant! Dabei stieß ich auf ein Preisrätsel in Form eines Hexadoku. Hexa-watt? Dokumentation im Hexcode? Nein --- ein Hexadoku ist die Abwandlung eines Sudokus. (Wie dekliniert man Sudoku?) Die Regeln sind schnell erklärt: Ein Sudoku ist ein Spielfeld aus 9 Zeilen und 9 Spalten. Zusätzlich ist es in drei mal drei (9) Quadrate eingeteilt. In diesem Spielfeld gilt es nun, die Ziffern 1--9 so zu verteilen, dass jede Ziffer in jeder Reihe, in jeder Spalte und in jedem Quadrat einmal --- und nur einmal! --- vorkommt. Fertig! Kurze Regel, langes Spiel. Es gibt $9! \times 722 \times 27 \times 27.704.267.971$ Möglichkeiten vgl.\ \url{http://de.wikipedia.org/wiki/Sudoku}. Zum Teil ausgefüllte Sudokus sind in Japan als Denkspiele sehr beliebt, sollen aber auch bei uns schon recht bekannt sein. Ein Hexadoku ist ein erweitertes Sudoku. Statt 9 Zeilen und Spalten gibt es je 16. Statt 9 Unterquadrate sind es ebenfalls 16. Und statt der Ziffern von 1--9 werden die Hex-Ziffern 0--F verwendet. Die Anzahl gültiger Hexadokus ist mir unbekannt. Regeln verstanden --- Spielplan ausgedruckt und losgelegt \ldots Bald wurde das Kombinieren und Ausprobieren langweilig. Das muss sich doch mit dem Rechner abkürzen lassen! Andererseits: à la brute force im Backtracking, das ist doch unter der Ehre! Oder? Aber eine Hilfe, die den stupiden Teil der Arbeit erledigt --- die kann man (ich) schon benutzen! Das war der Anlass. Es entstand das Programm Hexadoku (Quellcode \file{hexadoku.f}) mit bigforth unter Linux. Es sollte aber auch in anderen Umgebungen funktionieren. Vielleicht muss man die Worte zum Dateihandling anpassen. Für das Folgende mag es hilfreich sein, sich das Hexadoku aufzumalen (siehe Quelltext) oder auszudrucken (\code{start}). Mein Vorgehen in kurzen Worten: Nachdem die Rätselaufgabe (als 16 Strings) gespeichert ist, kann sie mit \code{neu} in das eigentliche Spielfeld (Array) übertragen werden. Unbesetzte Zellen werden mit FF gekennzeichnet. \emph{Über} dem Spielfeld liegen weiter 17 Felder (\code{ebene}). Das erste Feld wird mit Nullen, das zweite mit Einsen, \dots{} das 16.\ (F.) Feld mit Fs gefüllt. Das 17.\ Feld wird mit Nullen belegt. Jetzt wird überprüft, welche Ziffer in einer Zelle des Spielfeldes gesetzt ist. In der Zelle in Zeile 2 Spalte 0 ist das die 3. Das bedeutet, in der 4.\ Ebene, die den Wert 3 repräsentiert, werden alle Zellen der Zeile 2 und alle Zellen der Spalte 0 als \emph{verbrannt} (FF) gekennzeichnet. Die Zelle 2 0 gehört zum Unterquadrat 1. Also werden auch alle Zellen der 4.\ Ebene, die zu diesem Unterquadrat gehören, markiert. Dies geschieht für alle Zellen des Spielfeldes. Übrig bleiben 16 Ebenen, die nur dort Werte von 0--F enthalten, wo diese auch für die betreffende Spielfeldzelle noch erlaubt sind. Mit dem Wort ? \code{( Zeile Spalte -{}- )} kann man sich anzeigen lassen, welche Ziffern das sind. Bsp.: \code{2 1 ?} zeigt an, dass hier noch die Ziffern \code{0 4 A F} möglich sind. Das war der Plan --- soweit so gut! Aber ein wenig Hilfe mehr ist erlaubt. Oder? Also weiter: Nun wird gezählt, wie viele erlaubte Ziffern es zu jeder Zelle noch gibt. Dazu werden einfach alle Zellen \emph{über} einer unbesetzten Spielfeldzelle betrachtet und gezählt. Das Ergebnis findet sich in der 17.\ Ebene und kann mit \code{.v} betrachtet werden. Bsp.: \code{.v} zeigt nun an, dass zu der Zelle 2 1 noch 4 erlaubte Zahlen existieren. Auch das ist eine Hilfe. Aber noch weiter: Wenn nun schon mal gezählt ist, dann kann man doch überprüfen, bei welchen Zellen nur noch ein Wert möglich ist, und diesen dann auch gleich eintragen lassen. Das macht das Wort \code{automatik} (Kurzform \code{au}). Natürlich muss man eine Spielfeldzelle auch per Hand setzen können, falls die Automatik nicht weiterweiß. Das macht \code{ z!}, dem man den Wert und die Koordinaten übergibt. Bsp.: \code{0 2 1 z!} . Netterweise läuft ohne weiteres Zutun die Automatik an. Zum Schluss bleibt dann nur noch, das jeweilige Ergebnis schön formatiert auszugeben. Das entsprechende Wort \code{.ebene} gibt das aktuelle Spielfeld formatiert aus und zeigt einiges an Statistik an: zur leichteren Orientierung die Zeilen- und Spaltenindizes, die Anzahl der freien Zellen pro Zeile, Spalte und Unterquadrat, die Anzahl der automatisch gesetzten Spielfeldzellen und die Anzahl der noch möglichen Kombinationen, soweit sie berechenbar ist (in den allermeisten Fällen führt dies zu einem Überlauf --- sobald hier ein vernünftiger Wert angezeigt wird, ist man der Lösung schon recht nahe (subjektiv)). Das alles hilft schon ganz schön! Aber bequemer geht es, wenn man Spielstände speichern, ändern und zurückrufen kann. Hier habe ich mich entschieden, die gemachten Eingaben zu speichern. Dazu wird ein Stack angelegt, auf den mit den Worten \code{z} und \code{n} zugegriffen werden kann. \code{z} steht für zurück und \code{n} für noch einmal. Dieser Zug-Stack kann mit \code{save\_zuege} gespeichert und mit \code{lade\_zuege} wieder eingelesen werden. Trotz alledem habe ich bisher nicht die Lösung gefunden (Zeitmangel natürlich!). Es kann aber sein, dass das Programm einigen Lesern der Vierten Dimension Spaß und Kurzweil im Umgang mit Hexadokus bereitet. (Es ist für den privaten Gebrauch entstanden, gar nicht kommentiert und enthält immer noch Bugs und Unschönheiten, wie zum Beispiel, dass nur noch eine freie Zelle in einer Spalte/Zeile nicht als Fehler erkannt wird.) Auch wenn es nicht so ganz sportlich ist: Vielleicht kann \file{hexadoku.f} ja als Ausgangspunkt für eine vollautomatische Lösung dienen? \end{multicols} \begin{quote} \begin{small} \listinginput[1]{1}{2006-01/hexadoku.f} \end{small} \end{quote} \end{document}