\documentclass[11pt,a4paper]{article}

\usepackage[german]{babel}
\usepackage[utf-8]{inputenc} 
\usepackage{url} 
\usepackage{multicol}
\usepackage{moreverb}
\parindent0pt


\begin{document}

\title{Gforth–R8C erzeugt Sudoku–Rätsel–Vorgaben}

\author{Fred Behringer}

\maketitle

\begin{multicols}{2}

\section*{Einleitung und Ziel}

In Sudoku (= Ziffer je einmal), dem neuen geistigen Volkssport für Anspruchsvolle, verlangt man, dass in einer 9x9--Matrix jede Ziffer von 1 bis 9 in jeder Zeile, in jeder Spalte und in jeder 3x3--Teilmatrix genau einmal auftritt. Eine gewisse Anzahl von Elementen (meist um die 27d herum) werden vorgegeben, der Rest muss erraten werden. Sudoku--Rätselsammlungen in Buch-- oder Blockform (mit durchschnittlich 200 Rätseln und auf den letzten Seiten angegebenen Lösungen) kosten inzwischen nur noch 2--Euro--fünfzig.

Hexadoku (siehe VD--Heft 2/2006) fängt bei 0 an und hört mit F auf, Sudoku fängt bei 1 an und hört mit 9 auf. Es soll hier schon  verraten werden, dass man sich manches vereinfacht, wenn man die gesamte Matrix zunächst einmal um 1 verringert, die reduzierte Matrix (die also auf Ziffern von 0 bis 8 statt von 1 bis 9 aufbaut) dann verarbeitet und erst bei den Bildschirm--Ausgaben wieder 1 hinzuzählt. Dass das funktioniert, ist klar, wenn man bedenkt, dass es ja auf die \emph{Aufkleber} der Elemente nicht ankommt, wenn sie nur alle voneinander verschieden sind. Selbst auf eine bestimmte Reihenfolge der Ziffern kommt es nicht an. Man könnte auch per definitionem einfach eine neue Reihenfolge einführen, was mathematisch auf eine Umordnung hinausliefe.

Der R8C ist ein kleiner schwarzer Winzling mit etwas Drumherum. Das Drumherum soll uns hier nicht sonderlich interessieren. Harvard--Architektur oder von--Neumann--Architektur, Flash--Speicher oder RAM--Speicher, wer will das so genau wissen?

Auf der diesjährigen Forth--Tagung hat Bernd Paysan einiges über das Drumherum der Übertragung seines Gforth--Systems auf den R8C berichtet und Heinz Schnitter hat seinen Assembler für den R8C skizziert.

Wir wollen uns die Sache einfacher machen. Wir stellen uns einfach auf den Standpunkt, wir wissen gar nichts. Wir behandeln Gforth auf dem R8C einfach so wie viele andere Forth--Systeme auch, mit einem gewissen RAM--Bereich, in den wir (interaktiv per Tastatur) Forth--Wort um Forth--Wort eines Anwendungsprogramms packen können.

Ausgangspunkt ist irgendeine Version von {\tt gforth-r8c.mot} (siehe [1]), die (ein für alle Mal) per FDT in den Flash Speicher des R8C geladen wird --- genau so, wie es bei den drei Beispiels--mot--Programmen auf der Glyn--CD auch geschieht. (Falls sich Fragen ergeben: Ich habe Gforth 0.6.2-20060409 verwendet.) Der interaktive Verkehr des eingeladenen Gforth--R8C--Systems mit dem PC als Terminal (über die Tastatur und den PC--Bildschirm) möge sich per Windows--HyperTerminal abspielen: Die Baudrate muss bei Gforth--R8C 38400 betragen! (Bei FDT pendelt sich die Baudrate auf 9600 ein.) Für den Rest der Parameter bei HyperTerminal verwende man 8N1, kein Protokoll. (Ich habe meine Experimente auf einem AMD--K6--2/500 unter Windows 98 und Windows ME und auf einem AMD--64/3200+ unter Windows XP durchgeführt.) Beim Arbeiten mit HyperTerminal könnte es sein, dass das Schriftbild (zunächst noch) viel zu klein erscheint. Man ändere das (beispielsweise) über \emph{Ansicht – Schriftart – Courier New, Standard, 11 – Großbild} ab. Mit der größeren Schrift wird auch das Terminal--Fenster größer.

Schwierig ist die geringe Anzahl von internen RAM--Bytes (externes RAM gibt es beim R8C nicht). Etwas mehr als 700. Das war der Grund, nicht auf Hexadoku (16x16) der Zeitschrift Elektor aufzubauen, sondern sich auf das ursprüngliche Sudoku (9x9) zu besinnen. Das per Tastatur einzugebende Forth--Programm (siehe unten) benötigt nur etwas mehr als 640 Bytes. Es sind also noch genügend RAM--Bytes für schnelle Zusatzexperimente frei (siehe weiter unten bei den blinkenden LEDs). Warum Sudoku ausgerechnet auf dem R8C? Mehr dazu weiter unten. 

Genau wie im VD--Heft 2/2006 geht es hier nicht um Sudoku--\emph{Lösungsmöglichkeiten}\/, sondern um die Erzeugung von zulässigen Sudoku--\emph{Vorgaben}\/. Dazu wird von einer \emph{zulässigen} Sudoku--Matrix ausgegangen (die man als \emph{Lösung} eines vorgegebenen Sudoku--Rätsels auffassen kann). Über einen einfachen Zufalls--Mechanismus (der hier nicht besprochen werden soll) werden daraus willkürlich etwa 27d Vorgabeelemente (Erfahrungswert aus der Sudoku--Literatur) ausgewählt. 

Die unmittelbar einsichtige zulässige Anfangsmatrix (im Hexadoku--Rätsel aus dem VD--Heft 2/2006 hatte ich dafür die Bezeichnung \emph{kanonische} Matrix verwendet) wird schon bei Tastatur--Eingabe des Sudoku--Programms erzeugt und in den RAM--Speicher gelegt und kann danach leider nicht mehr \emph{per Knopfdruck} wiederhergestellt werden, ohne das Sudoku--Programm zu zerstören. Der RAM--Platz war für einen solchen Knopfdruck--Programmbaustein zu knapp. Allerdings hat man über  {\tt m}  und  {\tt ij!}  die (umständliche) Möglichkeit, sich durch Handeingabe eine \emph{beliebige} Sudoku--Matrix, also auch eine \emph{kanonische}, zu erzeugen. Platz für die Befehle für eine solche interaktive (über den Interpreter, nicht erst den Compiler laufende) Eingabe ist auf jeden Fall noch vorhanden. Platz für die Abspeicherung der Matrix selbst ist ja schon da. Ein Beispiel: Für das dritte Element (sein Wert ist 0) in der zweiten Zeile (bei der reduzierten Matrix beginnt die Zählung mit 0, nicht mit 1) gebe man für ein solches Vorhaben ein:


\begin{verbatim}
0 2 3 ij!
\end{verbatim}

Die (reduzierte) kanonische Sudoku--Matrix sieht wie folgt aus:


\begin{verbatim}
0 1 2 3 4 5 6 7 8 
3 4 5 6 7 8 0 1 2
6 7 8 0 1 2 3 4 5
1 2 3 4 5 6 7 8 0
4 5 6 7 8 0 1 2 3
7 8 0 1 2 3 4 5 6
2 3 4 5 6 7 8 0 1
5 6 7 8 0 1 2 3 4
8 0 1 2 3 4 5 6 7
\end{verbatim}

Die Überprüfung der Zulässigkeit dieser Matrix (die Frage, ob die Sudoku--Regeln erfüllt sind) fällt nicht schwer: Man gehe einfach mit dem Auge durch, Zeile um Zeile, Spalte um Spalte, 3x3--Teilmatrix um 3x3--Teilmatrix. Mit


\begin{verbatim}
2 3 ij@ .
\end{verbatim}

(der Punkt gehört dazu) kann man sich vergewissern, dass die Eingabe richtig angekommen ist.

Will man etwas Variation ins Programm bringen, so kann man statt der verwendeten \emph{kanonischen} Matrix auch deren \emph{Transponierte} (Zeilen mit Spalten vertauschen) einsetzen. Achtung: Im Feld  m  wird die um 1 reduzierte Sudoku--Matrix abgespeichert. Die Eintragungen gehen von 0 bis 8. Erst beim Bildschirm--Anzeigen über  v  wird alles wieder um 1 nach oben verschoben. Man beachte: Bei diesen nachträglichen Per--Hand--Eintragungen wird nicht ans Ende des Dictionarys \emph{compiliert} (nicht  {\tt c,}). Das (mit  {\tt m}  benannte) Speicherfeld ist ja schon vorhanden. Die (neuen) Werte werden per  {\tt c!}  (byteweise) dorthin (nach {\tt m}) \emph{abgespeichert}. Also:


\begin{verbatim}
0 m 00 + c! 3 m 01 + c! 6 m 02 + c!  
\end{verbatim}

und so weiter und so fort, oder etwas einfacher:

\begin{verbatim}
0 0 0 ij!  3 0 1 ij!  6 0 2 ij!
\end{verbatim}

Wichtig sind eigentlich nur die Zahleneingaben. Also nutze man die Möglichkeiten von Forth und baue sich ganz schnell eigens für diesen Zweck beispielsweise das Hilfswort

\begin{verbatim}
: y ij! ;
\end{verbatim}

Dies lässt sich in direkter Tastatureingabe auch noch nachträglich erledigen. So viel Platz ist da, im R8C. Das spart Tipparbeit und das Tastatur--Umschalten für {\tt !}\ \  .Was eingegeben und nach  {\tt m}  gelegt werden soll, ist die gleich folgende \emph{transponierte kanonische} Matrix. Sie entsteht aus der eingangs erwähnten \emph{kanonischen} Matrix, indem man dort Zeilen und Spalten vertauscht. Der leichteren Überprüfbarkeit wegen habe ich im Folgenden die kanonische Matrix (als zweite) neben ihre Transponierte geschrieben.


\begin{small}
\begin{verbatim}
0 3 6 1 4 7 2 5 8   0 1 2 3 4 5 6 7 8
1 4 7 2 5 8 3 6 0   3 4 5 6 7 8 0 1 2
2 5 8 3 6 0 4 7 1   6 7 8 0 1 2 3 4 5 
3 6 0 4 7 1 5 8 2   1 2 3 4 5 6 7 8 0
4 7 1 5 8 2 6 0 3   4 5 6 7 8 0 1 2 3
5 8 2 6 0 3 7 1 4   7 8 0 1 2 3 4 5 6
6 0 3 7 1 4 8 2 5   2 3 4 5 6 7 8 0 1
7 1 4 8 2 5 0 3 6   5 6 7 8 0 1 2 3 4 
8 2 5 0 3 6 1 4 7   8 0 1 2 3 4 5 6 7 
\end{verbatim}
\end{small}

Man prüft sofort nach, Zeile um Zeile, Spalte um Spalte, 3x3--Teilquadrat um 3x3--Teilquadrat, dass die Sudoku--Regeln erhalten bleiben.

Weitere Möglichkeiten, Variation ins Geschehen zu bringen: Klar, dass man aus einer beliebigen \emph{zulässigen} Sudoku--Matrix wieder eine \emph{zulässige} Sudoku--Matrix bekommt, wenn man alle Zeilen oder/und alle Spalten in umgekehrter Reihenfolge hinschreibt. Das alles wurde im VD--Heft 2/2006 schon beschrieben und begründet, muss aber hier \emph{außen vor} bleiben, da das RAM des R8Cs eben doch nicht allzu viel hergibt. Insgesamt gilt:

Geänderte Vorgabe--Matrizen bei gleichbleibender Sudoku--Matrix werden durch  {\tt v}  angezeigt. Geänderte Sudoku--Matrizen mit passender Vorgabe--Matrix werden durch  {\tt s}  angezeigt.

Solche Tastatureingaben müssen natürlich immer durch [return] abgeschlossen werden, um Wirksamkeit zu erlangen.

Die Sudoku--Matrix sollte bei möglichst kleinem Programm genügend durchgerüttelt werden. Ich habe das mit den willkürlich aufzurufenden Bausteinen   {\tt x addn  xchi  xchj}   erreicht.

Bei  {\tt x addn}  kann {\tt x} eine beliebige Zahl sein. Sie wird in der Form  {\tt 9 mod}  eingebaut. Man überzeugt sich leicht davon (Aufgabe für den Leser!), dass bei Addition modulo 9 von beliebigem x zu allen Matrix--Elementen die Sudoku--Regeln unverletzt bleiben.
{\tt xchj}  vertauscht willkürlich zwei Spalten in einem Dreierlängsstreifen. (Dreierlängsstreifen, damit nicht nur die Spalten, sondern auch die geänderten Teilquadrate Regeltreue bewahren.)
{\tt xchi}  macht Ähnliches, nur nicht ganz so willkürlich.

Man kann bei irgendeiner schon erreichten Sudoku--Matrix die angegebenen drei Befehle auch (einzeln oder in beliebiger Reihenfolge) per Hand eingeben.

Ich gebe zu, dass es bei diesen wirklich sehr wenigen Umformungsmöglichkeiten einfach ist, bei den geänderten \emph{Sudoku}--Matrizen den ursprünglichen systematischen Aufbau (\emph{kanonische Matrix}) wiederzuerahnen --- zumal, wenn man das Prinzip kennt. Aus den vom Programm per {\tt v}  angebotenen veränderten \emph{Vorgabe}--Matrizen dürfte der Wiedererkennungseffekt jedoch nicht mehr ganz so groß sein. Von \emph{leichtem Erraten} kann bei den erzeugten Vorgabe--Matrizen sicher keine Rede sein – wenn einem nicht jemand das kanonische Aufbau--Prinzip vorher verraten hat.

Natürlich ist es nicht Aufgabe des R8Cs, Sudoku--Rätsel--Vorgaben zu liefern. Dazu nimmt man den PC. Gforth--R8C ist aber ein ausgewachsenes Forth--System (Bernd und Heinz sei Dank) und es kann sicher nicht schaden zu sehen, dass der R8C mit Gforths Hilfe auch anspruchsvollere (Nichtsteuer--)Aufgaben bewältigen kann. Andererseits braucht man sich aber auch von den Beispielsprogrammen auf der von Elektor mitgelieferten Glyn--CD nicht beeindrucken zu lassen. Man gebe (von Gforth--R8C aus interaktiv (!) ins per Reset--Taste wieder löschbare R8C--RAM) ein:


\begin{verbatim}
: blink 
    100 0 do 
       i led!  100 ms   
       0 led!  100 ms 
    loop ;  

\end{verbatim}

und schließe mit der Return--Taste ab. Aufruf per  {\tt blink}  lässt die vier LEDs als Kombination im Rhythmus der Binärzahlen von 0000 über 0001 bis 1111 aufleuchten – mindestens genauso schön wie bei Glyn. Ohne Umwege über den PC, mit ganz normalen Forth--Mitteln. (Bernd hat dazu das schöne Forth--Wort  {\tt led!}  mit den 16 LED--Kombinationen als Eingabeparameter eingeführt.) 

Das ist aber dann auch ein weiterer Grund, weshalb ich auf Sudoku verfallen bin: Sudoku braucht keine Elektor--Experimentierplatine (für 69,-- Euro), das R8C--Platinchen in Minimalbeschaltung reicht (die Minimalbeschaltung habe ich um den RS232 ergänzt und ich danke Rolf Schöne für Hinweise). Bei der LED--Ansteuerung müsste man sich auf der Minimalbeschaltung die LEDs selbst hinzubasteln --- kein ersthaftes Problem, aber sicher nicht jedermanns Sache.

Es ist nicht ganz einfach, das Sudoku--Programm fehlerfrei ins R8C--RAM zu bringen. In jeder Zeile kann man zwar mit der Delete--Taste wieder zurückgehen, um Fehleingaben zu korrigieren, ist aber erst einmal die betreffende Eingabezeile über die Return--Taste abgeschlossen worden und hat das System das betreffende Wort akzeptiert, obwohl es nicht korrekt eingegeben wurde, dann bleibt einem nur die Reset--Taste. (Die ganze bisherige (Sudoku--)Arbeit ist dann futsch.) Das Wort  {\tt forget}  ist nicht vorgesehen. {\tt forget}  ist aber auch kein ANS--Wort. Hat man es aber geschafft, das Sudoku--Programm ins R8C--RAM zu bringen, dann kann man das Ganze per  {\tt savesystem}  fixieren. Die Reset--Taste greift ab dann (auch nach Ausschalten und Wiedereinschalten) diesen Teil nicht mehr an. Kleinere Schnellzusätze, wie das  {\tt blink}  bei den LEDs, wird man dann immer noch per Reset--Taste wieder los. Will man aber wirklich das gesamte (eingegebene und per   {\tt savesystem} fixierte) Sudoku--Programm wieder loswerden, dabei aber das schon per FDT eingeflashte Gforth--R8C beibehalten, dann erreicht man das per {\tt empty}.
\end{multicols}

[1]  \url{http://www.forth-ev.de/wiki/doku.php/projects:r8c:r8c\_forth}

\section*{Forth-Programm}


\listinginput[1]{1}{2006-03/sudoku-r8c.fs}




\end{document}
