Rekursion, fürsorgliche Browser, vorherbestimmte Zufallszahlen
oder
Wie man den Stack verschont

Im folgenden auftauchende Zeilenangaben beziehen sich auf den hier hinterlegten Code bei eingeschalteten Kommentaren (also in der Voreinstellung). Sie erreichen diesen Code nur über diesen Link, nicht über das Menu. Beim zu den Erläuterungen dieser Seite passenden Code muß in Zeile 3 var TOTAL = 16; stehen. Das Programm ist in Javascript verfaßt; die Gründe dafür können Sie hier nachlesen. Ein lauffähiges Beispiel genau dieses Codes finden Sie hier.


Die Zeilen 14 - 31 sind für die Funktionalität des eigentlichen Algorithmus nicht notwendig; da die dort angegebenen Funktionen im Code aufgerufen werden, ist aber zumindestens die Erwähnung der Prototypen nötig. Es handelt sich lediglich um Anzeigemechanismen, damit man die Früchte der Arbeit genießen kann.

Die Zeilen 3 - 11 belegen die Variablen SMALL_LINE, LINE und TOTAL mit passenden Werten. Ausgangspunkt ist die Gesamtanzahl der Felder des Spielfelds, die im vorliegenden Fall 16 beträgt. Falls bei geltender Relation SMALL_LINE4 = TOTAL die Variable SMALL_LINE nicht ganzzahlig sein sollte, wird passend abgerundet.

In Zeile 134ff stehen die verwendeten globalen Variablen. i, random, redundant, tmp, unset_count nehmen Ganzzahlen auf, die im weiteren Verlauf als Zwischenergebnisse benötigt werden; sie an dieser Stelle im Code aufzuführen ist lediglich ein Entgegenkommen an die Freunde typsicherer Sprachen. tries_to_set ist für die Funktionalität irrelevant und zählt lediglich die Anzahl der Bearbeitungsschritte mit.

Äußerst wichtig dagegen sind die beiden Arrays riddle und indices. Ersteres ist eine Liste der Spielfelder; die Werte der einzelnen Elemente sind die angezeigten Zahlen (hier also möglich 1 bis 4 und zusätzlich 0 als neutrales Element, wenn noch kein Wert gefunden wurde). Statt der angesichts der graphischen Darstellung naheliegenden zweidimensionalen Anordnung habe ich mich für eine lineare (von links nach rechts und von oben nach unten) entschieden, und zwar aus folgenden Gründen:

indices ist eine Liste, in der die Schlüssel von riddle in der Reihenfolge, in der sie bearbeitet werden sollen, aufgeführt sind. Der Zugriff auf ein Spielfeld im soundsovielten Bearbeitungsschritt ist also riddle[indices[soundsoviel]]. Wie im vorangegangenen Kapitel erläutert, müssen in indices die Zahlen von 0 bis (TOTAL-1) in zufälliger Reihenfolge untergebracht werden.

Beide Arrays müssen mit Werten befüllt werden. Im Fall von riddle ist das sehr einfach, da anfangs noch für kein Spielfeld ein Zahlenwert bekannt ist, und geschieht in Zeile 143f. Die Befüllung von indices erfolgt durch die Funktion randomize_unweighted() aus Zeile 114ff, aufgerufen in Zeile 147. Eine allgemeine Beschreibung für diesen Zweck verwendbarer Algorithmen finden Sie hier. Die Entscheidung, von den beiden aufgeführten Methoden die für Listen optimierte zu verwenden, ist einer Laune geschuldet; da die Initialisierung der Arrays nur einen winzigen Bruchteil der für diesen Algorithmus benötigten Rechenleistung verbraucht, ist es vollkommen egal, welche verwendet wird.

Der im letzten Kapitel skizzierte Algorithmus beinhaltet die Absicht, alle Spielfelder der in indices festgelegten Reihenfolge nach mit einer gültigen Zahl zu belegen. Zu diesem Zweck wird eine Möglichkeit zu überprüfen benötigt, ob eine Zahl gültig ist oder nicht. Als gültig gelte eine Zahl, die weder in der Zeile noch in der Spalte noch in dem kleinen Quadrat ihres Aufenthaltorts vorkommt. Dazu dient die Funktion contains_element() aus Zeile 54ff, die überprüft, ob ein übergebenes Element in einer übergebenen Sammlung vorhanden ist1. Manche Programmiersprachen haben eine solche Funktion bereits in den Sprachstandard aufgenommen.

Da die bereits gesetzten Werte in riddle aus den obengenannten Gründen linear gespeichert werden, müssen die jeweiligen Werte der Zeilen, Spalten und kleinen Quadrate bei jeder Überprüfung der Gültigkeit eines Wertes aufs neue ermittelt werden2. Dies geschieht in zwei Schritten: get_collection() aus Zeile 41ff gibt für jedes Spielfeld die Ordnungszahl der beinhaltenden Zeile, Spalte und des beinhaltenden kleinen Quadrats aus; das (willkürlich festgelegte) Ordnungssystem geht jeweils von links nach rechts und von oben nach unten und beginnt jeweils mit 0. Die Sammlungen tatsächlicher Werte für Zeilen, Spalten und kleine Quadrate werden von den Funktionen get_horizontal(), get_vertical() und get_square() aus Zeile 64ff, Zeile 79ff und Zeile 94ff zurückgegeben3.

Nun ist alles für die Erstellung eines gelösten Sudoku, also das Befüllen der Spielfelder mit Werten, vorbereitet. Die dafür zuständige Funktion set_values() steht in Zeile 159ff und wird in Zeile 193 aufgerufen. Da es sich um das Herzstück des Algorithmus handelt, werde ich mich bemühen, sie besonders detailliert zu besprechen.

Der übergebene Parameter index ist die Ordnungszahl des Bearbeitungsschritts. Nach Möglichkeit sollen diese Schritte der Reihe nach, also von 0 bis 15 ausgeführt werden4; nur wenn die Funktion auf eine Situation trifft, die ein weiteres Vorgehen unmöglich macht, wird sie einen oder mehrere Schritte zurückgehen. Der andere Parameter forbidden_number ist der Eitelkeit geschuldet, ein und die selbe Funktion sowohl für das Setzen als auch für das Löschen von Werten zu verwenden. Beim Setzen wird dieser Parameter nicht benötigt; es ist lediglich darauf zu achten, keine Zahl zu übergeben, die als Wert auf dem Spielfeld vorkommen könnte - anders ausgedrückt: im vorliegenden Fall ist alles außer 1, 2, 3 und 4 erlaubt.

Wie oben erwähnt, ist die Relation zwischen Bearbeitungsschritt und tatsächlichem Spielfeld riddle[indices[index]]. Zur Erleichterung der Lesbarkeit wird in Zeile 161 die temporäre Variable real_index eingeführt, die die Ordnungszahl des Spielfeldes angibt. Über diese Ordnungszahl lassen sich sowohl veränderliche Werte (die Zahl, die auf dem jeweiligen Spielfeld angezeigt wird) setzen und lesen als auch unveränderliche Werte (zu welcher Zeile, Spalte und zu welchem kleinen Quadrat das jeweilige Spielfeld gehört) ermitteln. Da letztere Information unbedingt benötigt wird, wird sie in Zeile 163 eingeholt und im temporären Array blocks gespeichert5.

An dieser Stelle lohnt es, innezuhalten und über die prinzipielle Vorgehensweise nachzudenken. Die entscheidende Frage an dieser Stelle ist Welcher Wert ist für das aktuelle Spielfeld empfehlenswert? Derartige Fragestellungen sind für Computer viel zu schwierig. Deswegen soll die Aufgabe in zwei Teilschritte zerlegt werden, nämlich 1) Gehe alle denkbaren Werte durch. 2) Entscheide für jeden Wert, ob er möglich ist. Im zweiten Punkt liegt das Problem verborgen - die in ihm enthaltene Fragestellung erwartet als Antwort JA oder NEIN. Diese Antwort hängt davon ab, ob in der zugehörigen Zeile, Spalte und dem zugehörigen kleinen Quadrat der auszuprobierende Wert mehr als einmal vorkommt - aber diese Zeilen, Spalten und Quadrate sind ja zumindestens teilweise noch leer, so daß das Nichtauffinden von Duplikaten keine Gewißheit geben kann, es gebe auch keine: eingentlich müßte man die Werte für alle Spielfelder auf einmal setzen. Falls eines Tages der heißersehnte Quantencomputer erfunden werden sollte und sich zudem jemand erbarmt und einen Quanten-Sudoku-Algorithmus entwickelt, wird das wahrscheinlich die bevorzugte Methode sein; momentan muß man sich mit sequentieller Abarbeitung der Einzelschritte begnügen.

Die Frage Ist der auszuprobierende Wert möglich? soll in zwei Teilfragen zerlegt werden, nämlich 1) Kollidiert der auszuprobierende Wert mit bereits gesetzten Werten? 2) Kollidiert der auszuprobierende Wert mit noch zu setzenden Werten? Die Beantwortung der zweiten Teilfrage ist aus Unkenntnis zukünftiger Werte vorläufig nicht möglich, die der ersten Teilfrage schon; erschließt man aus der ersten Antwort eine Antwort auf die Gesamtfrage, ergeben sich statt der gewünschten Möglichkeiten JA oder NEIN stattdessen die Möglichkeiten NEIN (Duplikat gefunden) oder VIELLEICHT (kein Duplikat gefunden, aber es könnte später noch eins auftreten). Das ist ärgerlich, aber nicht hoffnungslos6.

Zunächst soll nach einer Möglichkeit gesucht werden, bei der die Antwort doch JA sein könnte - und die gibt es tatsächlich, nämlich dann, wenn keine noch zu setzenden Werte mehr auftreten können, also bei Erreichen des letzten Eintrags aus indices. Daraus läßt sich eine Taktik entwickeln:

Es ist nicht nötig, bei Spielfeldern vom Anfang der Liste tatsächlich alle künftigen Spielfelder einzeln abzufragen7; die Entscheidungsfindung kann folgendermaßen zusammengefaßt werden:

Es wurde somit eine Möglichkeit gefunden, die ungeliebte Antwort VIELLEICHT in eine der verwendbaren Antworten JA oder NEIN umzuwandeln. Es besteht allerdings noch das Problem, daß sich zukünftige Prüfungen auf die mit VIELLEICHT MÖGLICH deklarierten Werte beziehen; also müssen alle Werte mit dem Prädikat VIELLEICHT erst einmal auf Verdacht gesetzt werden. Dafür gibt es prinzipiell zwei Möglichkeiten:

Die erste Möglichkeit spart den Schritt des eventuellen Löschens, muß aber vielfach Variationen des gesamten Spielfeldes, die sich kaum voneinander unterscheiden, zwischenspeichern. Auch wenn moderne Computer in der Regel großzügig mit Speicherplatz ausgestattet sind, habe ich mich für die ressourcensparendere zweite Variante8 entschieden.

Nach diesem theoretischen Ausflug möge es mit der Besprechung des Codes weitergehen.

Die Zeilen 165 - 182 beinhalten eine Schleife, die für das aktuelle Spielfeld die möglichen Werte, hier 1 bis 4, durchprobiert. Wird in den Zeilen 171 - 176 festgestellt, daß der auszuprobierende Wert in Zeile, Spalte oder kleinem Quadrat bereits vorkommt, wird der Rest der Schleife mit continue; übersprungen. Falls der auszuprobierende Wert die Prüfungen erfolgreich übersteht, wird in Zeile 178 durch riddle[real_index] = i; der Wert (vorläufig) übernommen.

In Zeile 180f steht mit if ( index == (TOTAL - 1) || set_values((index + 1), 0) ) return 1; die zuvor besprochene Entscheidungsfindung: Falls das Spielfeld das letzte ist oder der Aufruf dieser Funktion mit um 1 erhöhtem Index erfolgreich ist, brich mit Erfolgsmeldung ab (die Kompatibilität mit bereits gesetzten Werten ist ja schon überprüft worden). Wichtig ist, den Index nur für den jeweiligen Funktionsaufruf zu erhöhen (deshalb index + 1 und nicht ++index) und einen eventuellen Erfolg durch return 1; abzuschließen, damit keine nachfolgenden Operationen das gelöste Sudoku wieder für ungültig erklären können.

Das Erreichen der Zeilen nach der Schleife ist ein sicheres Zeichen dafür, daß kein gültiger Wert gefunden werden konnte. Also wird in Zeile 184ff mit riddle[real_index] = 0; ein eventueller auf Verdacht vergebener Wert zurückgesetzt und mit return 0; der Mißerfolg bekanntgegeben.

Das gelöste Sudoku ist nun fertig; Sie können das Ergebnis in Zeile 196f anzeigen lassen.

Nun sollen Spielfelder unkenntlich gemacht werden - und zwar maximal so viele, daß das Sudoku noch eindeutig lösbar ist. Zu diesem Zweck werde eine Liste zu löschender Spielfelder angelegt und so lange gelöscht, wie das verbleibende Sudoku lediglich eine einzige Lösung aufweist. Sobald es mehr als eine Lösung gibt, soll statt des im letzten Kapitel vorgeschlagenen Punktes Rücknahme des Löschens dieser Zahl darauf verzichtet werden, den Vorgang des Löschens anzuzeigen - aus Sicht des Nutzers hat das den gleichen Effekt. Da es, wie erwähnt, hier nicht darauf ankommen soll, besonders schwierige Sudokus zu erzeugen, ist es egal, was für eine Liste man verwendet; der Einfachheit halber sei es wiederum indices, diesmal rückwärts durchlaufen.

Wie gewährleistet man Eindeutigkeit? Auch dafür hält die Mathematik eine einfache Antwort bereit: Im Zweifelsfall, indem man zeigt, daß alle anderen Lösungen auf einen Widerspruch stoßen. Beim vorliegenden Problem bedeutet das, einen Wert zu löschen und zu versuchen, das verbleibende Sudoku zu lösen, wobei es nicht erlaubt ist, den gelöschten Wert wieder seinem ursprünglichen Spielfeld zuzuweisen. Scheitert dieser Versuch, kann es nur einen - den ursprünglichen - Wert für das betroffene Spielfeld geben. Danach fahre man auf gleiche Weise mit dem nächsten Wert fort. Es ist dabei nicht nötig, mehr als für eines, nämlich das letzte, Spielfeld einen Wert zu verbieten, da die Eindeutigkeit für die restliche Lösung ja schon im vorangegangenen Schritt nachgewiesen wurde9.

Auch wenn ich es durch eine möglichst unscheinbare Formulierung zu verschleiern versucht habe, wird Ihnen vielleicht aufgefallen sein, daß das Unkenntlichmachen der Werte tendenziell mehr Rechenschritte benötigt als das Setzen derselben, denn für jeden gelöschten Wert muß ein Lösungsversuch gestartet werden. Natürlich wird das erst wirklich ausschlaggebend, wenn bereits mehrere Werte gelöscht sind und der neue Lösungsversuch eine längere Kette von Spielfeldern durchlaufen muß.

Zur Verwirklichung des Plans werden erst mit unset_count in Zeile 213 bzw. Zeile 220 ein Schleifenzähler definiert und dann zwei rekursive Vorgänge ineinander verschachtelt; der äußere besteht nicht aus einer rekursiven Funktion, sonderm aus dem, was ich im zweiten Kapitel als inhaltlich rekursiv bezeichnet habe, nämlich einer do-while - Schleife in Zeile 214 bzw. Zeile 222. Dieser speichert den Wert des aktuellen Spielfeldes in tmp = riddle[indices[TOTAL - unset_count]]; und ruft set_values() mit dem jeweiligen Index der Liste auf, wobei diesmal tmp als zusätzlicher Parameter übergeben wird und innerhalb der Funktion als forbidden_number behandelt wird. Dieser Name ist selbsterklärend - wenn beim Durchprobieren möglicher Werte in Zeile 194 eine Übereinstimmung zwischen dem aktuellen Wert und forbidden_number entdeckt wird, wird dieser Wert aus der Liste der möglichen Kandidaten ausgeschlossen. Eventuelle Selbstaufrufe von set_values() übergeben allerdings, wie oben erläutert, stets 0, verbieten also keinen Wert beim Durchprobieren.

set_values() besitzt zur Steuerung der eigenen Rekursion einen Rückgabewert; dieser wird hier sowohl in Zeile 218f als Entscheidungskriterium für die Frage, ob der Wert des aktuellen Spielfelds gelöscht werden soll, als auch zur Kontrolle der äußeren Schleife verwendet, deren Bedeutung sich mit Fahre fort, solange es unmöglich ist, das Rätsel mit einem anderen als dem tatsächlichen Wert des aktuellen Spielfeldes zu lösen übersetzen ließe. In diesem Fall kann auf die Verwendung einer 'echten' rekursiven Funktion verzichtet werden, da zu jedem Index ohne Berücksichtigung späterer Schritte das Gelingen der Operation mit Gewißheit festgestellt werden kann.

Damit ist die Aufgabe gelöst; bei jedem Aufruf erzeugt der Algorithmus ein neues gültiges 16-teiliges Sudoku. Im nächsten Schritt soll der Vorgang auf die übliche Größe von 81 Spielfeldern übertragen werden.


 zurück: Schema eines Algorithmusweiter: 9x9 - erster Versuch 

1 Da es darum geht, Duplikate zu vermeiden, prüft die Funktion auf Inhaltsgleichheit. Dadurch erübrigt sich die eher philosophische und oft enervierende Diskussion über das Gleiche und das Selbe sowie typgleich und am selben Speicherort. Pragmatischer ausgedrückt: if ( the_array[i] == the_element ) benötigt genau zwei, nicht drei Gleichheitszeichen, in mit ihrer Nähe zur Objektorientierung kokettierenden Sprachen den Vergleichsoperator equals.  ↑ 

2 Es ist ausreichend, die Zugehörigkeit zu Zeile, Spalte und kleinem Quadrat pro Spielfeld vorzunehmen. Wenn man ganz sicher sein sollte, während des Ausprobierens verschiedener Zahlen niemals zwischen Spielfeldern hin- und herzuspringen, könnte man auch die bereits gesetzten Werte einmalig ermitteln und zwischenspeichern. Ich wollte zugunsten der Erweiterbarkeit des Algorithmus diese Möglichkeit aber nicht von vornherein ausschließen.  ↑ 

3 Lassen Sie sich nicht durch get_square() erschrecken; das sieht schlimmer aus, als es ist. Im wesentlichen wird bei der linken oberen Ecke eines kleinen Quadrats zu zählen begonnen und nach SMALL_LINE Werten 'umgebrochen', also in die nächst tiefere Zeile gewechselt.  ↑ 

4 Falls Ihre bevorzugte Programmiersprache bei 1 zu zählen beginnt, müssen Sie hier 1 bis 16 einsetzen.  ↑ 

5 Die Zuordnung ist blocks = [ ZEILE, SPALTE, KLEINES_QUADRAT ];. Falls Sie die numerische Ansprache des Arrays als unübersichtlich empfinden, können Sie auch ein Objekt verwenden, etwa var blocks = {}; blocks.row = ZEILE; blocks.column = SPALTE; blocks.square = KLEINES_QUADRAT;.  ↑ 

6 Viel schlimmer als VIELLEICHT wäre eine Antwort wie SOWOHL ALS AUCH oder KOMMT AUF DIE SICHTWEISE AN oder gar etwas wesensfremdes wie KEINE AHNUNG, IST ABER IMMERHIN BELUSTIGEND oder HIMMELBLAU.  ↑ 

7 Man sollte sich aber der Tatsache bewußt sein, daß der Computer im Laufe der Programmausführung genau das tut.  ↑ 

8 Nicht unberücksichtigt lasse man zudem, daß viele Computersprachen Arrays als Objekte ansehen und diese per Referenz weitergeben - mit oftmals unerwünschten Nebeneffekten beim Kopieren und Löschen.  ↑ 

9 Man könnte auf den Gedanken verfallen, aus Performancegründen trotzdem bereits gesetzte Werte zu verbieten, um Rechenschritte zu sparen. Dabei muß man aber sehr vorsichtig vorgehen, da die Unterschiedlichkeit zweier Lösungen ja nicht zwangsläufig bedingt, daß alle Werte unterschiedlich sind.  ↑