Im Rahmen unseres zweiten Sudoku-Artikels werden wir uns mit der Entwicklung von rekursiven und iterativen Backtracking-Algorithmen beschäftigen, mit deren Hilfe sich selbst die kniffligsten Sudoku-Rätsel mit Leichtigkeit lösen lassen.

Im vorangegangenen Artikel haben wir das Rätselspiel Sudoku von seiner eleganten Seite kennengelernt. Wir haben uns ein wenig mit der Mathematik beschäftigt, die einem Sudoku-Rätsel innewohnt und uns mit diversen Strategien vertraut gemacht, mit denen sich einfache Rätsel allein durch logisches Denken und ohne Zuhilfenahme von Notizen lösen lassen. Ein gutes Sudoku zeichnet sich meiner Meinung nach dadurch aus, dass man es ausschließlich durch logische Schlussfolgerungen zu lösen vermag.

So gesehen könnten manche das Thema des heutigen Artikels als eine Art Rückschritt betrachten, denn womit wir uns heute auseinandersetzen, hat mit (künstlicher) Intelligenz so rein gar nichts zu tun. Backtracking-Algorithmen bedienen sich keiner logischen Zusammenhänge, um ein Sudoku-Rätsel zu vervollständigen, sondern nutzen stattdessen die enorme Rechenpower moderner Computer in Kombination mit dem Trial-and-Error-Prinzip, um eine Lösung zu finden. Okay, dass klingt vielleicht ein bisschen zu abwertend. Nicht alle Probleme dieser Welt müssen mit künstlicher Intelligenz und maschinellem Lernen bewältigt werden. Warum einfach, wenn es auch kompliziert geht? Und darüber hinaus lassen sich Backtracking-Verfahren ja durchaus auch aufwerten oder in Kombination mit anderen (KI-)Algorithmen einsetzen. Es ist zum Beispiel verhältnismäßig einfach möglich, einen Backtracking-Algorithmus zur Lösung von Sudoku-Rätseln dahingehend zu erweitern, dass sich mit ihm zusätzlich auch neue Rätsel nach dem Zufallsprinzip generieren lassen.

Backtracking einfach erklärt

Backtracking-Algorithmen (zu Deutsch: Rücksetzverfahren) sind gewissermaßen die Allzweckwaffe des Programmierers zur Lösung von Planungsproblemen (z. B. Wegfindung), zur Ermittlung der bestmöglichen Spielstrategien bei Zwei-Personen-Spielen wie Schach und Vier gewinnt (Minimax-Algorithmus) oder zur Lösung von Puzzlespielen wie Sudoku. Im Wesentlichen beruhen sämtliche Backtracking-Methoden auf dem Prinzip von Versuch und Irrtum, wobei die Lösung eines Problems (z. B. eines Sudoku-Rätsels) immer Schritt für Schritt im Zuge einer Tiefensuche erfolgt (durch schrittweises Ausfüllen der noch leeren Sudoku-Felder).

Sofern man beim Lösen eines Problems aufgrund von früher gemachten Fehlern in einer Sackgasse landet (es findet sich für ein noch leeres Sudoku-Feld keine passende Ziffer), werden zunächst ein und dann mehrere Lösungsschritte zurückgenommen (zuvor eingetragene Ziffern wieder entfernt), damit sich ein alternativer Lösungsweg testen lässt. Wenn es für ein gegebenes Problem eine Lösung gibt, wird es spätestens dann gefunden, wenn unser Backtracking-Verfahren alle denkbaren Lösungswege evaluiert hat.

(Rekursive) Funktionen aus der Sicht eines Programmierers

Beim Aufruf einer besonders einfach gestrickten Funktion wird der Compiler auch ohne unsere Einflussnahme (durch Verwendung des inline-Schlüsselwortes) sehr wahrscheinlich den Funktionsaufruf eigenmächtig durch den zur Funktion gehörigen Programmcode ersetzen. Bei komplexeren oder rekursiv arbeitenden Funktionen ist das jedoch nicht möglich. In diesen Fällen wird der ausführbare Code (Maschinencode) dieser Funktionen, zu denen selbstverständlich auch die Hauptprogrammfunktion zählt, bei Programmstart in einen als Codesegment bezeichneten Speicherbereich geladen, wohingegen die globalen und statischen Variablen im sogenannten Datensegment hinterlegt werden. Immer, wenn eine Funktion aufgerufen wird, erfolgt ein Sprung zu derjenigen Speicheradresse, die den Einstiegspunkt der besagten Funktion markiert. Nachdem eine Funktion ihre Arbeit beendet hat, erfolgt im letzten Schritt ein Rücksprung zu derjenigen Speicheradresse, von der aus die Funktion zuvor aufgerufen wurde.

Eine Funktion arbeitet immer mit einer Kopie der Werte (Zahlenwerte, Klassen- oder Strukturobjekte, Speicheradressen, Referenzen usw.), die ihr beim Aufruf als Argumente übergeben wurden. Folgerichtig kann eine Funktion niemals die Originalwerte der ihr beim Funktionsaufruf übergebenen Argumente verändern. Diese Kopien werden genau wie die Rücksprungadressen oder die Werte anderer lokal deklarierter Variablen in einem speziellen Speicherbereich gespeichert, dem Stack (Stapelspeicher).

Die Tatsache, dass die Lebensdauer aller lokal in einer Funktion (im Funktionskopf oder im Funktionsrumpf) deklarierten Variablen erst endet, sobald die Funktion wieder verlassen wird, ist bei der Implementierung rekursiv arbeitender Funktionen von besonderer Bedeutung. Ruft sich eine solche Funktion beispielsweise zehnmal selbst auf, dann sind im Stack dementsprechend die lokal verwendeten Variablen von zehn Funktionen hinterlegt. Das hört sich zwar im ersten Moment nicht nach viel an, da die Stackgröße aber andererseits recht knapp bemessen ist (im Megabytebereich liegt), gilt es, im Zuge der Implementierung eines rekursiven Algorithmus sicherzustellen, dass es bei seiner Ausführung zu keinem Speicherüberlauf (Stack-Overflow-Fehler) kommt.

Tail- versus Head-Rekursion

In Abhängigkeit davon, an welcher Stelle der rekursive Funktionsaufruf innerhalb einer Funktion erfolgt, spricht man entweder von einer sogenannten Tail- oder einer Head-rekursiv arbeitenden Funktion. Um nun die Unterschiede zwischen diesen beiden Rekursionsverfahren samt der damit einhergehenden Funktionsaufrufe besser nachvollziehen zu können, rufen die beiden an dieser Stelle betrachteten rekursiven Funktionen ihrerseits die nachstehend gezeigte RecursionTestOutput()-Testfunktion auf:

static int32_t g_RecursionTestOutputFuncCallCounter = 0;
void RecursionTestOutput(int32_t num) {
  cout << "(" << g_RecursionTestOutputFuncCallCounter << ") "
       << num << " "; }

Anhand der in Listing 1 illustrierten TailRecursiveTestFunction() werden wir uns zunächst einmal einen Überblick über die grundsätzlichen Programmabläufe innerhalb einer Tail-rekursiv arbeitenden Funktion verschaffen.

• Schritt 1: Anzahl der bisher durchgeführten rekursiven Funktionsaufrufe zu Überwachungszwecken zwischenspeichern:

  g_RecursionTestOutputFuncCallCounter++;

• Schritt 2: Überprüfen, ob die Abbruchbedingungen für einen Stopp der rekursiven Funktionsaufrufe erfüllt sind:

  if (counter >= maxCount)
    return...