Backtracking anhand des 8-Damen-Problems erklärt

Backtracking ist das Schweizer Taschenmesser der Programmierers: Alle Probleme, für die man keine gute andere Lösung findet, kann man mehr oder weniger gut mit Backtracking lösen.

Deswegen möchte ich Backtracking anhand eines einfachen Beispiels vorstellen.

Ein Beispiel für ein etwas komplizierteres Problem ist das Lösen von Sudokus, das ich in meinem Sudoku-Solver "YaSSS" anwende.

Das Acht-Damen-Problem

Beim Acht-Damen-Problem fragt man danach, wie man acht Damen auf ein Schachbrett stellen kann, ohne dass sich zwei oder mehr der Damen gegenseitig schlagen können.

Dabei sollte man wissen, dass ein Schachbrett aus 8x8-Feldern besteht, und dass Damen beim Schach beliebig viele Schritte nach oben oder unten oder diagonal gehen dürfen.

Uns interessiert hier nicht die genaue Stellung der Damen, sondern nur, wie viele Möglichkeiten es gibt, die Damen zu platzieren.

Verallgemeinerung: Das n-Damen-Problem

Das oben gestellte Problem kann man schön auf beliebig viele Damen verallgemeinern, man muss allerdings die Größe des Feldes anpassen.

Unsere Aufgabe lautet also, ein Programm zu schreiben, das folgende Frage beantwortet:

Wie viele Möglichkeiten gibt es, N Damen auf ein NxN großes Schachfeld zu stellen, ohne dass sich zwei oder mehr schlagen können?

Backtracking - was ist das?

Backtracking heißt, kurz gesagt, alle Möglichkeiten durchprobieren - besser gesagt, alle sinnvollen.

Meistens funktioniert das so: man sucht die Lösung für ein Problem schrittweise. Wenn man in einer Sackgasse steckt, geht man wieder einen Schritt zurück, und versucht dort einen andere Möglichkeit. Das wiederholt man so lange, bis man entweder eine Lösung gefunden hat, oder alle Möglichkeiten durchprobiert hat.

Das Prinzip lässt sich sehr gut an einem Labyrinth veranschaulichen:

Ein Labyrinth. Dieses Bild ist der Wikimedia Commons entnommen und steht unter der GFDL. Damit stehen auch alle folgenden Bilder, die auf diesem Bild beruhen, unter dieser Lizenz

Stellen wir uns vor, ein kleiner Gnom will durch diese Labyrinth. Er ist ziemlich dumm, aber er hat sich vorgenommen, an Kreuzungen immer links zu gehen. Außer natürlich, er hat einen Weg schon einmal genommen, dann nimmt er die Abzweigung, die am weitesten links ist und die er noch nicht genommen hat.

Er markiert seinen Weg mit seinen "Duftstoffen", sodass er immer weiß, welchen Weg er wann gegangen ist.

Er läuft also los, und natürlich gleich nach links:

Unser Gnom läuft los. Der Rote Punkt markiert seinen Aufenthaltsort, der grüne Streifen die Schleimspur, die er hinter sich herzieht.

Mist, eine Sackgasse. Also umdrehen, zum Anfang zurückkaufen, und die nächste Möglichkeit nehmen:

Der Gnom erreicht die nächste Kreuzung.

Schon wieder eine Kreuzung. Wo wird er wohl langgehen? links natürlich:

Wieder eine Sackgasse

... landet wieder in einer Sackgasse. Also wieder umdrehen, an der vorherigen Kreuzung die nächste Möglichkeit nehmen, und wieder bis zur nächsten Kreuzung:

Der Gnom erreicht die nächste Kreuzung

Und dort geht er wieder links, diesmal ist das eine gute Entscheidung...

Und schon wieder eine Kreuzung

Und wieder links...

Die vorletzte Kreuzung

Ein letztes Mal noch verläuft er sich...

Die letzte Sackgasse

Und erreicht endlich das Ziel:

Endlich das Ziel erreicht

Man kann also durch ausprobieren von Wegen und durch zurück laufen, wenn man einen Fehler gemacht hat, das Labyrinth erkunden.

Mit vielen Problemen ist das ähnlich - auch mit unserem Acht/N-Damen-Problem.

Das N-Damen-Problem gelöst

Ich möchte hier eine Lösung des N-Damen-Problems in der Programmiersprache C vorstellen.

Zu aller erst muss man sich überlegen, wie man das Spielfeld speichert.

Als erste Möglichkeit kommt man vermutlich auf die Idee, das Feld in einem zweidimensionalen Array zu speichern, für jede Stelle auf dem Feld eine Speicherzelle.

Wenn man etwas gründlicher überlegt, stellt man fest, dass man mit einem eindimensionalen Array auskommt. Dazu sollte man sich klar machen, dass auf jeder Zeile des Feldes genau eine Dame steht. Schließlich könnten sich zwei Damen, die in der gleichen Zeile stehen gegenseitig schlagen, und es gibt genauso viele Damen wie Zeilen.

Man speichert also in einem Array für jede Zeile, an welcher Position von links aus die Damen stehen.

Ein Schachbrett
	mit je einer Dame im dritten Feld der ersten Zeile, im ersten Feld der
	zweiten Zeile und im sechsten Feld der dritten Zeile
Ein Ausschnitt aus einem Schachfeld, bei dem die ersten drei Zeilen zu sehen sind.

In diesem Beispiel wären als die ersten drei Einträge in dem Array, das das Feld beschreibt, 1, 0 und 5 (Wir fangen bei Null das Zählen an, d.h. wir ziehen von der Position, an der sich die Dame befindet, eins ab).

Also fangen damit an, einen Typ für unser Feld zu und zwei globale Variablen zu definieren. (Ja, ich weiß, global Variablen sind böse[tm], aber hier geht es damit nun mal am einfachsten).

typedef signed short int field_type;

int N = 8;
unsigned long int Count = 0;

field_type ist signed, weil wir später Differenzen verwenden werden, die auch negativ sein können. Und short, weil das Feld nicht sehr groß ist (siehe weiter unten).

N ist die Größe des Feldes, Count die Anzahl der bisher gefunden Kombinationen.

Zeit für unsere eigentliche Suchfunktion:

void search(field_type *field, field_type row){
	field_type i = 0;
	if (row == N){
		/* Wir haben eine mögliche Kombination gefunden */
		Count++;
		return;
	}

Wenn schon N Damen platziert wurden, sind wir (für diesen Suchzweig) am Ziel. Wenn weniger platziert wurden, versuchen wir es einfach weiter:

	for (i = 0; i < N; i++){
		field[row] = i;
		if (! collision(field, row)){
			search(field, row + 1);
		}
	}
} /* Ende der Funktion */

In Worten: Platziere in der Zeile row eine Dame an der einer Stelle, fange an der Stelle 0 an. Wenn die Dame dort geschlagen werden kann, lohnt es sich nicht weiter zu suchen. Kann sie dort nicht geschlagen werden, Wiederhole das ganze in der nächsten Zeile.

Dann wiederhole den ganzen Vorgang an der Stelle 1 anstatt 0, und so weiter.

Wir haben hier die Funktion int collision(field_type*, field_type) verwendet, die wir noch nicht programmiert haben. Das müssen wir nachholen:

int collision(field_type *field, field_type row){
	field_type i = 0;
	field_type tmp = 0;
	for(i = 0; i < row; i++){
		tmp = field[i] - field[row];
		if (tmp == 0 || tmp == i - row || tmp == row - i){
			return 1;
		}
	}
	return 0;
}

Diese Funktion überprüft, ob die Dame in Zeile row von einer vorher platzierten Dame geschlagen werden kann.

Wenn die Dame in der gleichen Spalte steht, ist die Bedingung tmp == 0, also field[i] == field[row] erfüllt. Die anderen beiden Bedingungen sind dann erfüllt, wenn eine Dame diagonal links oder rechts diagonal über der neuen Dame steht.

Jetzt müssen wir eigentlich nur noch die Funktion mit einem leeren Array und row = 0 aufrufen.

Man kann jedoch die Geschwindigkeit des Programms verdoppeln, wenn man sich klar macht, dass es zu jeder Lösung eine an der Mitte gespiegelte Lösung geben muss. Wenn es also eine Lösung geben sollte, bei der die erste Dame in der ersten Spalte steht, so gibt es sicher auch eine, bei der die Dame in der letzten Spalte steht.

Wenn wir also die erste Dame nur in der ersten Hälfte des Feldes (field[i] = 0 ... 3 ) starten lassen, können wir uns die Hälfte der Laufzeit sparen und müssen nur noch am Ende unser Ergebnis mit 2 multiplizieren:

int main(int argc, char** argv){
	/* Initialisiere Array */
	field_type field[N];
	field_type i = 0;
	for (i = 0; i < N / 2; i++){
		field[0] = i;
		search(field, 1);
	}
	printf("Number of solutions: %ld (with %d queens)\n", 2 * Count, N);
	return 0;
}

Dieser Trick führt allerdings dazu, dass diese Programm nur für geradzahlige N funktioniert. Für ungeradzahlige N müsste man bis zur Spalte vor der Mitte gehen, dann den Wert von Count verdoppeln, und dann noch mit der mittleren Spalte die Funktion search durchlaufen lassen.

Jetzt bleiben nur noch ein paar Kleinigkeiten zu erledigen: Headerdateien einbinden, und vielleicht überprüfen, ob auf der Kommandozeile die Größe des Feldes als Argument übergeben wurde.

Hier noch einmal der ganze Quellcode:

/* Copyright by Moritz Lenz (C) 2006. */
/* You may use this file under the terms of the MIT license */
#include <stdio.h>
#include <stdlib.h>

typedef signed short int field_type;

int N = 8;
unsigned long int Count = 0;

int collision(field_type *field, field_type row){
	field_type i = 0;
	field_type tmp = 0;
	for(i = 0; i < row; i++){
		tmp = field[i] - field[row];
		if (tmp == 0 || tmp == i - row || tmp == row - i){
			return 1;
		}
	}
	return 0;
}

void search(field_type *field, field_type row){
	field_type i = 0;
	if (row == N){
		Count++;
		return;
	}

	for (i = 0; i < N; i++){
		field[row] = i;
		if (! collision(field, row)){
			search(field, row + 1);
		}
	}
}


int main(int argc, char** argv){
	if (argc == 2) {
		/* Die Groesse des Feldes wurde auf der Kommandozeile */
		/* angegeben */
		N = atoi(argv[1]);
		if (N < 4 || N % 2 == 1){
			printf("%s: Warning: Ignoring count '%d' since it " 
					"must be an event integer > 3", 
					argv[0], N);
			N = 8;
		}
	}

	field_type field[N];
	field_type i = 0;
	for (i = 0; i < N / 2; i++){
		field[0] = i;
		search(field, 1);
	}
	printf("Number of solutions: %ld (with %d queens)\n", 2 * Count, N);
	return 0;
}

Den Quellcode gibt es auch zum Herunterladen.

Ergebnisse

Die Ergebnisse des Programms, abgesehen davon, dass man nach dem lesen diese Textes hoffentlich Backtracking verstanden hat, sind die folgen:

Anzahl der Lösungen des N-Damen-Problems

FeldgrößeAnzahl der Lösungen
42
68
892
10724
1214200
14365596
1614772512
18666090624

Oder als Grafik (Halblogarithmisch:)

Klicke auf die Grafik, um eine größere Version zu sehen.

(Auch als PostScript-Datei erhältlich)

Man sieht, dass die Anzahl der Lösungen in halblogarithmischer Auftrag etwa eine Gerade ergibt, d.h. die Anzahl der Lösungen steigt exponentiell mit N.

Das Problem ist nur, das der Algorithmus mit großem N sehr lange braucht, die benötigte Zeit steigt ebenfalls ungefähr exponentiell mit N an.