<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}
</pre></body></html>