Ein etwas weiter Verbreitetes Beispiel für das Backtracking ist das 8 Dame Problem. Die Aufgabe lautet, positionieren sie 8 Damen auf einem Schachbrett so, ohne das sich eine der Damen gefährden. Für denen die es nicht wissen : Die Dame kann von Ihrer aktuellen Position aus beliebig viele Felder in der gleiche Spalte oder in der gleichen Reihe oder in die Diagonalen rücken. Versuchen sie es mal auf dem Schachbrett zu nachzuahmen. Es gibt exakt 92 Möglichkeiten. Wir haben jetzt die Möglichkeit ein zweidimensionales Array zu verwenden, aber da sich zwei Damen in der gleichen Reihe oder Spalte eh nur bedrohen würden können wir uns das sparen. Wie also soll unsere Funktion dame(..) aussehen. Die erste Dame die wir setzen hat kein Bedrohung zu befürchten. Daher setzen wir sie an die rechte obere Ecke. Also übergeben wir unserer Funktion dame(..) den Wert 7 (Computer fangen von 0 zu zählen an!!!) und unser int-Array 'schachbrett[8]'....

dame(schachbrett, 7);  

Somit sieht unsere Backtrackingfunktion wie folgt aus....

int dame(int *schachbrett, int position)  

Schauen wir uns nun die erste Hälfte unserer Backtracking - Funktion an....

int dame(int *schachbrett, int position)
{
 int x=1;
 static int counter=1;

 while(x<=8)
  {
   schachbrett[position]=x;  

Die Variable x dient zur Indenfizierung der einzelnen Damen. Jede Dame bekommt eine extra Nummer. Des weiteren dient dieser Wert später auch noch zur Überprüfung ob unsere Dame in der Diagonalen gefährdet wird. Aber dazu später mehr. Mit...

schachbrett[position]=x;  

...bekommt das Feld 7 rechts oben den Wert 1...

Als nächstes benötigen wir nun eine Funktion um zu testen ob die Dame mit der Nummer 1 auf der Reihe, Spalte und Diagonalen mit einer anderen Dame kollidiert....

if(!dame_in_gefahr(schachbrett))  

Der Funktion übergeben wir die Daten von unserem Schachbrett. Im 1. Beispiel wird die if - Anweisung logischerweise wahr sein. Also unsere Dame ist nicht in Gefahr (!dame_in_gefahr(..)). Als nächstes prüfen wir in einer weiteren if - Anweisung...

if(position)  

...ob wir nicht schon an die position 0 gekommen sind. Falls nicht dann kommt unser 1.Rekursive Aufruf...

if(dame(schachbrett,position-1))  //die Nächste Dame
    return 1;  

...das heißt das jetzt der momentane Stand der Funktion auf dem Stack gelegt und einen Rückgabewert erwartet. Hier nochmals die Funktion bis hierher im Überblick...

int dame(int *schachbrett, int position)
{
 int x=1;
 static int counter=1;

 while(x<=8)
  {
   schachbrett[position]=x;    //Wir setzten die Dame mit der
                               //Nummer x an feld[position]
   if(!dame_in_gefahr(schachbrett))
    {
     if(position)
      {
       if(dame(schachbrett,position-1))   //die Nächste Dame
         return 1;                  //Dame in dieser Position setzten
       }
     else
          return 1;  

Mit dem erneuten Funktionsaufruf sieht sieht die Situation nun wie folgt aus...

Nun ist unser Dame an Position 7 aber in Gefahr und folgende Anweisung wird nun nicht ausgeführt....

if(!dame_in_gefahr(schachbrett))  

folglich wird nun der Zähler x um 1 erhöht...

x++;  

Somit ergibt sich durch.....

schachbrett[position]=x;  

folgendes Bild auf dem Schachbrett.....

Auch in dieser Stellung werden die beiden Damen kollidiert. Also wird x nochmals um 1 erhöht. Somit sieht es jetzt folgendermaßen aus...

if(position)
  {
   if(dame(schachbrett,position-1))  

...ein erneuter Funktionsaufruf durchgeführt und der Stand der Aktuellen Funktion wird wieder auf dem Stack getan (2.Funktion auf dem Stack) die wiederum auf Ihren Einsatz wartet. Jetzt geht das ganze wieder von vorne los. Der nächste Schritt sieht so aus....

Überspringen wir nun 3 weiter Erhöhungen von x (da sich die nächsten 3 Reihen eh kollidieren).....

Wohl gemerkt heißt das noch laaannge nicht das dies die Endgültige Stellung darstellt da all diese Funktionsaufrufe noch auf dem Stack liegen und darauf warten was mit Ihnen passiert -> 1 = bleibt so 0=weiter suchen...

Der nächste Funktionsaufruf wird nun den Wert 0 zurückgeben, da sich in der 1.Spalte keine Dame platzieren lässt ohne das diese mit einer anderen kollidiert. Das heißt jetzt geht unsere Funktion zurück zur 2.Spalte von links (Farbig markiert) ->

Der Wert von x der auf dem Stack gespeichert wurde betrug 6 also wird dieser wieder um 1 erhöht und es geht in Zeile 7 weiter. Dort kollidiert unsere Funktion wieder. In Zeile 8 ebenfalls wieder. Also gibt unsere 2.Spalte von links an Ihrem Aufrufer der 3.Spalte von links den Wert 0 zurück. Unser Programm nimmt also wieder die Ausführung in der 3. Spalte von links und der Zeile 4 (Wert von x) auf und läuft nun die 5.,6.,7.,8.Zeile durch, da überall eine Dame in Gefahr ist. Somit gibt unsere 3. Spalte an Ihrem Ausrufer den Wert 0 zurück. Das wäre somit die 4. Spalte in der 2. Zeile. Somit sieht es auf unserem Schachbrett folgendermaßen aus.....

Dieses Hin.-und Her geht solange bis unsere Abfrage...

if(position)  

....unwahr wird. Das heißt wir sind ans Ende gekommen sind. Dies könnten wir nun mit einem return 1 bestätigen.......

if(position)
      {
       if(dame(schachbrett,position-1))//die Nächste Dame
         return 1; //Dame in dieser Position setzten
       }
else
     return 1;  //Wir sind fertig wir haben 1 Lösung  

..oder aber auch wenn wir alle 92 Möglichkeiten Ausgeben wollen. Wir benutzten letzteres. Ich empfehle Ihnen um das ganze Programm besser zu verstehen real Schritt für Schritt auf einem Schachbrett nachzuspielen. Hier nun die komplette Funktion mit der Funktion dame_in_gefahr und der main - Funktion.....

/*Download:eightd.c*/ #include <stdio.h> #include <stdlib.h> int dame_in_gefahr(int *schachbrett) { int x,y; /*x==nach unten; y==nach rechts*/ for(x=0; x<7; x++) if(schachbrett[x]) /*Ist auf feld[x] eine Dame?*/ for(y=x+1; y<=7; y++) if(schachbrett[y]) /*Ist auf feld[y] eine Dame?*/ { /*Wir überprüfen ob sich die beiden Damen kollidieren?*/ if(schachbrett[x]==schachbrett[y])/*beide Damen in der selben Zeile?*/ return 1;/*Kollision in gleicher Zeile*/ if(abs(x-y)==abs(schachbrett[x]-schachbrett[y]))//diagonal? return 2;/*Kollision in der diagonalen*/ } return 0; /*kein Kollision!*/ } int dame(int *schachbrett, int position) { int x=1; static int counter=1,c=1; while(x<=8) { schachbrett[position]=x;/*Wir setzten die Dame mit der*/ /*Nummer x an feld[position]*/ if(!dame_in_gefahr(schachbrett)) { if(position) { if(dame(schachbrett,position-1))//die Nächste Dame return 1; /*Dame in dieser Position setzten*/ } else { int i; printf("Lösungs-Nr.%2d : ",counter++); for(i=0; i<8; i++) printf("(%d,%d)",i+1,schachbrett[i]); printf("\n"); } } x++; }/*Ende while*/ schachbrett[position]=0; return 0; } int main() { int schachbrett[8],x; for(x=0;x<8;x++) schachbrett[x]=0; dame(schachbrett,7); return 0; }

Zur Zeile....

if(abs(x-y)==abs(schachbrett[x]-schachbrett[y]))  

...berechnen wir die Absolute Zahl (abs) das heißt zum Beispiel der Absolute Wert von 2-6 wäre 4 nicht -4. Diese if - Abfrage testet ob sich in der Diagonalen eine Gefährdung einer Dame befindet. Testen sie es einfach in der Praxis und sie wissen was ich meine. Hier noch zur Demonstration eine Lösung von dem 8 Dame Problem...