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

Die Größe des Spielfeldes hängt einzig vom Wert der Variablen TOTAL ab; es sollte also ausreichend sein, in Zeile 3 var TOTAL = 81; zu schreiben. Wenn Sie das Experiment selbst durchführen wollen, dürfte der einfachste Weg zum Ziel darin bestehen, die Beispielseite aufzurufen, den Quelltext in ein (unformatiertes) Textdokument zu kopieren und in einem Browser Ihrer Wahl anzeigen zu lassen. Allerdings wird diese lokale Kopie nicht wie gewünscht auf Klicks in die Menuzeile reagieren, so daß Sie selbst Hand anlegen müssen, um ein Sudoku in Standardgröße zu erhalten:

Ändern Sie den Eintrag in Zeile 439 in var TOTAL = 81;; wenn Sie befürchten, 81 Felder könnten zu groß für Ihr Browserfenster sein, können Sie noch in Zeile 261 width: 32px; und in Zeile 338 var cell_size = 32; schreiben. Bevor Sie das geänderte Dokument Ihrem Browser übergeben, sollten Sie sich jedoch vergewissern, nur wenige Klicks vom Task Manager, der Aktivitätsanzeige oder wie immer das Hilfsprogramm, mit dem man auf Ihrem Betriebssystem Prozesse gezielt zum Absturz bringen kann, heißt, entfernt zu sein.

Der letzte Satz ließ es schon befürchten: Das gewünschte Ergebnis will sich nicht einstellen. Wenn Sie einen mitteilsamen Browser wie Mozilla Firefox einsetzen, werden Sie stattdessen eine Nachricht wie Ein Skript auf dieser Seite ist eventuell beschäftigt oder es antwortet nicht mehr sehen; schweigsamere Vertreter ihrer Zunft brechen das Laden der Seite einfach kommentarlos ab1. Das ist nicht nur enttäuschend, sondern wirft auch Fragen auf: Ist der Algorithmus vielleicht doch nicht für jede Spielfeldgröße, sondern nur den Spezialfall 4x4 geeignet? Oder ist er eigentlich allgemeingültig, versagt aber aus aus irgendwelchen Gründen bei 81 Feldern?

Keins von beidem. Falls Sie sich in einer Programmiersprache zu Hause fühlen, die ohne eine Laufzeitumgebung auskommt, welche kompromißlos auf das Wohl des Anwenders achtet, können Sie den Algorithmus in ebendiese Sprache übertragen; das Programm wird ohne Warnmeldung laufen und irgendwann zu einem Ergebnis kommen. Die Betonung liegt allerdings auf irgenwann. Zwar wird die tatsächliche Laufzeit von den zufälligen Werten, die die Funktion randomize_unweighted() generiert hat, abhängen, aber aller Wahrscheinlichkeit erheblich höher sein, als Ihrer Geduld zuzumuten ist. Das ist eine schlechte Nachricht, da das Problem offensichtlich prinzipieller Natur ist und deswegen nicht durch einfaches Ausbessern zu beheben ist.

Zwei Fragen drängen sich auf: Wie kann es sein, daß die Anzahl der Bearbeitungsschritte und damit die Laufzeit ins Unermeßliche wächst, nur weil man den Wert einer einzigen Variablen von 2 auf 3 erhöht? Und selbst wenn, warum sind Browser solche Spielverderber und rechnen nicht solange, wie es eben dauert?

Die erste Frage kommt ohne Mutmaßungen über die Intentionen von Menschen (nämlich den Programmieren von Browsern) aus und ist deshalb leichter oder zumindestens eindeutiger zu beantworten.

Zum einen wirkt sich die Erhöhung in der vierten Potenz aus: Statt 24 = 16 Felder geht es nun um 34 = 81 Felder, das ist immerhin gut das Fünffache; das allein könnte diesen enormen Anstieg aber noch nicht erklären. Die Anzahl der tatsächlichen Rechenschritte abzuschätzen ist nicht ganz trivial, zumal sie zumindestens teilweise von einer Zufallsfunktion abhängt; man kann sich aber ein ungefähres Bild des Anstiegs der Rechenschritte machen, indem man statt des mühsam ausgetüftelten rekursiven Algorithmus' einen einfachen, aber verschwenderischen (Sie können ihn auch gern als dümmlich bezeichnen) für beide Fälle annimmt. So erfährt man zwar nicht, wieviel die Maschine wirklich zu tun hat, erhält aber eine Vorstellung davon, um wieviel schwerer die Aufgabe wird, wenn man die Kantenlänge des Spielfelds vergrößert.

Die Anzahl auffindbarer gelöster Sudokus wird tendenziell in irgendeiner Weise (möglicherweise exponentiell) proportional zur Anzahl der Spielfelder sein; der Einfachheit halber möge in beiden Fällen nach einer einzigen ganz bestimmten Lösung gesucht werden. Alle denkbaren Möglichkeiten, die zur Verfügung stehenden Zahlen in die Spielfelder einzutragen, mögen notiert und am Ende mit der gesuchten Lösung verglichen werden.

In einem 16-teiligen Sudoku stehen 4 mögliche Zahlen zur Verfügung; gäbe es nur ein einziges Spielfeld, wären es also 4 Möglichkeiten insgesamt. Zwei Spielfelder böten 4x4 = 42 = 16 Möglichkeiten, drei Spielfelder 4x4x4 = 43 = 64. Für ein komplettes Spielfeld mit 16 Feldern käme man auf 416 = 4294967296 zu notierende Situationen, also gut 4 Milliarden. Diese Zahl erscheint auf den ersten Blick sehr hoch (ich habe diesen Algorithmus nicht ohne Grund als verschwenderisch bezeichnet), ist aber kaum erwähnenswert im Vergleich zu 981 (gerundet eine 2 mit 77 Nullen)! Die nächste Spielfeldgröße hätte 16256 Möglichkeiten, die übernächste 25625 - letztere einzeln aufzuführen wäre wohl selbst für die Computer von Geheimdiensten eine Überforderung.

Diese Überlegungen gingen von einigen unzulässigen Vereinfachungen aus; trotzdem dürfte klargeworden sein, daß jeder auf Ausprobieren beruhende Sudoku-Algorithmus, der eine bestimmte Spielfeldgröße gerade noch bewältigt, vor dem nächstgrößeren Spielfeld kapitulieren muß2. Von einem realistischen Standpunkt aus betrachtet ist es völlig egal, ob die Laufzeit sich um das 5x1067fache, wie oben geschätzt, verlängert oder nur um die Hälfte, ein Hundertstel oder die Wurzel dieses Werts3. Das gilt ebenso, wenn man - etwas wirklichkeitsnäher - statt Potenzen mit Fakultäten rechnet (da ein vernünftiger Algorithmus gar nicht erst versucht, benachbarte Felder mit der gleichen Zahl zu belegen).

Einen wirklich experimentierfreudigen Programmierer wird die lange Laufzeit kaum abschrecken; warum überlassen Browser nicht dem Anwender die Entscheidung, wie lang ein Programm laufen darf?

Diese Tatsache ist durch den Umstand zu erklären, daß aus Sicht eines Browsers nicht Programmierer, sondern Endnutzer (also Menschen, die im Internet surfen, ohne zu wissen, was sie erwartet) als Anwender angesehen werden. Der Browser weiß natürlich genausowenig, was die aufgerufene Webseite für Überraschungen birgt, und versucht, anhand vorgefertigter Kriterien eine Entscheidung zu treffen, ob der auf der Webseite hinterlegte Inhalt wünschenswert ist oder nicht. Rekursionen mit mehr als ein paar Millionen Selbstaufrufen gelten jedenfalls nicht als wünschenswert, da die Gefahr droht, daß sie niemals zu einem Ende gelangen.

Der Verzicht auf Rekursion reicht aber nicht, um sehr aufwendige Operationen durchführen zu dürfen. Auch mit einer while - oder einer do-while - Schleife käme der Browser irgendwann zu dem Schluß, er befinde sich in einer möglicherweise unendlich lang andauernden Rechenoperation und tue dem Anwender durch Abbruch der Ausführung einen Gefallen.

Der Versuch, den bestehenden Algorithmus für ein 16-teiliges Sudoku auf ein 81-teiliges Sudoku zu übertragen, stößt also auf drei Schwierigkeiten:

An der Gültigkeit des zweiten Punkts ist nichts zu ändern; der erste soll im weiteren Verlauf durch Optimierungsmaßnahmen umgangen werden. Zunächst möchte ich Ihnen aber eine Möglichkeit vorstellen, den Algorithmus in kleine Stückchen zu unterteilen und damit den Sicherheitsvorkehrungen des Browsers zu entziehen. Der praktische Nutzen ist zwar gering, da es nicht sinnvoll ist, Langzeitalgorithmen ausgerechnet in Javascript ausführen zu lassen, aber dadurch wird wenigstens das Gefühl der Handlungsfreiheit wiederhergestellt.

Die dafür benötigte Funktion nennt sich setTimeout() und tut im wesentlichen das, was man bei diesem Namen erwartet: Sie führt die als Parameter angegebene Anweisung verzögert aus. Das ist allerdings nicht dasselbe wie sleep() aus manchen anderen Programmiersprachen: Letzteres hält die ganze Programmausführung an, während ersteres sich die verzögert auszuführende Anweisung merkt, mit den nachfolgenden Anweisungen fortfährt und nach der voreingestellten Zeit den zurückgehaltenen Befehl abarbeitet. Das bedeutet nicht, daß jetzt mehrere Prozesse gleichzeitig ausgeführt werden und man auf diese Weise die Rechenleistung vervielfachen kann - die Aufmerksamkeit der Maschine springt einfach zwischen mehreren Aufgaben hin- und her. Damit wird auch die Gefahr, die die Verwendung von setTimeout() beinhaltet, klar: Es ist nicht leicht vorherzusagen, an welcher Stelle das Programm angelangt ist, wenn der verzögert auszuführende Befehl an der Reihe ist.

Das ist nicht die einzige Einschränkung, die man in Kauf nehmen muß. Rekursive Vorgänge oder gar rekursive Funktionen mit Rückgabewert lassen sich nicht ohne weiteres ausführen; schließlich kann man kaum hoffen, mit der Anweisung Führe das Folgende in Abhängigkeit von einer Information, die du erst später erhältst, aus bei einem Computer auf Verständnis zu stoßen. Zudem muß man sich an den Gedanken gewöhnen, daß alles erheblich länger dauert - schließlich besteht beim vorliegenden Anwendungszweck der Sinn ja gerade darin, durch Gewähren einer kleinen Verschnaufpause den Verdacht des Browsers, er sei in einer endlosen Rechenoperation gefangen, zu zerstreuen.

Natürlich ist setTimeout() eigentlich für gänzlich andere Arten des Einsatzes konzipiert. Will man - wie hier - das Programm möglichst schnell abarbeiten, aber einen drohenden Abbruch vermeiden, wird man in der Regel nicht etwas wie das folgende schreiben: 

                        
function retarded_count_down (number) {
    console.log(number);
    if ( number > 0 )
        setTimeout(retarded_count_down, 41, --number);
}

retarded_count_down(25);

Hier wird die Ausgabe jeder einzelnen Zahl verzögert; das kostet ein Vielfaches der Zeit der eigentlichen Berechnung - unabhängig davon, wie klein man den Verzögerungswert einstellt. Geschickterweise wird man versuchen, erst kurz bevor der Browser mißtrauisch wird mit einer Verzögerung zu arbeiten. Angenommen, beim vorangegangenen Beispiel wären 10 unverzögerte Aktionen hintereinander gerade noch zu bewältigen, ohne den Browser zu verärgern, könnte man den Code vielleicht folgendermaßen gestalten: 

                        
function retarded_count_down (number) {
    console.log(number);
    while ( number > 0 ) {
        if ( number % 10 == 0 ) {
            setTimeout(retarded_count_down, 666, --number);
            return;
        }
        console.log(--number);
    }
    console.log("Done!");
}

retarded_count_down(25);

Hier wird die Funktion nur dann verzögert aufgerufen, wenn der aktuelle Wert durch 10 teilbar ist, ansonsten abwärts gezählt.

Ein praxisnäheres Beispiel finden Sie auf dieser Seite. Dort geht es darum, möglichst schnell eine große Anzahl an Primzahlen zu ermitteln; das dauert länger, als der Browser ununterbrochen zu rechnen bereit wäre, deswegen werden von Zeit zu Zeit die ermittelten Primzahlen dem Nutzer gezeigt und die Berechnungen danach - verzögert - fortgesetzt.

Um dem Sudoku-Algorithmus eine unbegrenzte Laufzeit zu ermöglichen, soll im folgenden der Code so umgeschrieben werden, daß an geeigneten Stellen Verzögerungen eingebaut werden können. Von einer Lösung entfernt man sich dadurch noch weiter, da die Pausenzeiten der Gesamtlaufzeit hinzuzurechnen sind; andererseits empfinde ich es durchaus als reizvoll und manchmal auch lehrreich, durch Verzögerungen im menschlich noch wahrnehmbaren Bereich4 dem Code bei der Arbeit zusehen zu können.


 zurück: 4x4 rekursiv

1 Task Manager bzw. Aktivitätsanzeige werden Sie wahrscheinlich nicht benötigen; Browser pflegen sich in aller Regel selbst zu schützen.  ↑ 

2 Auch wenn es praxisorientierten Menschen als befremdlich erscheint: Bei der allgemeinen Beurteilung der Schwierigkeit eines algorithmischen Problems (bzw. der Leistungsfähigkeit eines gegebenen Algorithmus) betrachtet man nie die Anzahl der tatsächlich benötigten Rechenschritte, sondern immer das Verhältnis zwischen Komplexität der Ausgangssituation und Anzahl der Rechenschritte bei steigender Komplexität der Ausgangssituation - anders ausgedrückt: man konzentriert sich nicht auf den Schwierigkeitsgrad eines einzelnen Problems, sondern auf die Steigerung der Schwierigkeit, wenn die Ausgangssituation sich verkompliziert. Das liegt daran, daß sowohl die Leistungsfähigkeit von (neu entdeckten) Algorithmen als auch die verwendeter Hardware sich ständig ändert; was heute noch als praktisch unlösbar gilt, könnte in ein paar Jahren leicht zu bewältigen sein. Die Frage, ob die nächstschwierigere Variation des Problems in diesem Fall auch noch leicht zu bewältigen ist, hängt jedoch nicht vom jeweiligen Stand von Wissenschaft und Technik ab.  ↑ 

3 Es hat sich die Ansicht durchgesetzt, die meisten Menschen könnten die Größenordnung einer Zahl besser einschätzen, wenn sie in Dezimalschreibweise notiert ist. Ich bin mir da nicht so sicher, möchte Ihnen aber den Anblick nicht vorenthalten:
Nach obiger Schätzung verlängert sich die Laufzeit, wenn man von einem 16-teiligen Sudoku zu einem 81-teiligen Sudoku übergeht, um den Faktor 50000000000000000000000000000000000000000000000000000000000000000000
Die (willkürlich) erwähnte Wurzel wäre ungefähr 7000000000000000000000000000000000  ↑ 

4 Die Filmindustrie arbeitet in der Regel mit 24 bis 30 Bildern pro Sekunde (24, 25, 29.97 oder 30), für Mobilgeräte optimierte Filmformate mit 15; die Untergrenze für die Wahrnehmung fließender Übergänge soll bei 12 (der Bildfrequenz früher Stummfilme) liegen, die Obergrenze für das Wahrnehmen von Einzelinformationen (oft auch als Abtastfrequenz des Auges bezeichnet) bei - je nach Untersuchung - etwas über 70; Programmierern zugänglich ist in der Regel eine Frequenz von bis zu 60 Bildern pro Sekunde, was von Spieleherstellern auch - wo möglich - ausgenutzt wird. Für eigene Experimente empfehle ich dringend, beim Millisekundenwert eine Primzahl einzusetzen, um Überschneidungen mit anderen periodischen Prozessen möglichst gleichmäßig zu verteilen.  ↑