Stoppt die Vorratsdatenspeicherung! Jetzt klicken && handeln!Willst du auch bei der Aktion teilnehmen? Hier findest du alle relevanten Infos und Materialien:
 
8-Damen-Problem
von Plapperkatze am 26.November 2006 um 16:23
zurück zur Kategorie "Tutorials"

Diesmal möchte ich euch eine Lösung des sogenannten 8-Damen-Problems vorstellen. Es gibt sicher noch kürzere und elegantere Wege zur Lösung, die ich aber nur am Rande aufzeigen will.

Die Aufgabe lautet etwa folgendermassen:
Man finde alle Möglichkeiten, 8 Damen auf einem Schachbrett so zu platzieren, dass keine eine andere bedroht.

Oder, etwas allgemeiner formuliert:
Man finde alle Möglichkeiten, N Damen auf einem N*N großen Schachbrett so zu platzieren, dass keine eine andere bedroht.

Wie man weiß, können sich Damen horizontal, vertikal und diagonal auf dem Spielfeld bewegen. Das bedeutet logischerweise, dass sich immer nur genau eine Dame pro Zeile und Spalte befinden kann - sonst würden sie sich ja direkt bedrohen. Zum speichern eines Spielfeldes genügt also ein Array mit N Elementen, bei N=8 zum Beispiel folgendes (0 entspricht dem ersten Feld von links):
array[8]={4,6,1,5,2,0,3,7}



Versuchen wir es der Einfachheit halber mit einem 4-Damen-Problem, wobei hier die Damen von oben nach unten zeilenweise gesetzt werden:



Bei diesem Vorgehen versuchen wir zuerst in jeder Zeile, die Damen auf das erste mögliche Feld zu setzen. Wenn das nicht möglich ist, wird der letzte Zug zurückgenommen und das nächste mögliche Feld verwendet. Sind auch hier alle Möglichkeiten ausgeschöpft, wird um einen weiteren Zug zurückgegangen und auch hier das nächstmögliche Feld verwendet.

Wir benötigen also eine Funktion, die überprüft, ob das untersuchte Feld unter Berücksichtigung der bisherigen Züge gültig (valid) ist:
int valid(int N,int *field,int pos) // 1 = valid
{
 int depth=0,d,t;
 while(depth<N&&*(field+depth)!=-1)depth++;
 for(d=0;d<depth;d++)
 {
   if(*(field+d)==pos)return 0;
   if(pos+(depth-d)<N&&*(field+d)==pos+depth-d)return 0;
   if(pos-(depth-d)>-1&&*(field+d)==pos-(depth-d))return 0;
 }
 return 1;
}

Es werden die Breite N des Spielfeldes (die der gesuchten Anzahl N Damen entspricht), das aktuelle Spielfeld, und die zu prüfende Position übergeben. Dann wird die derzeitige Zugtiefe (die Anzahl belegter Zeilen) ermittelt, und geprüft, ob sich eine Dame vertikal oder diagonal darüber befindet. Ist das nicht der Fall, gilt die angegebene Position als gültig.

Weiterhin benötigen wir eine Funktion, die sämtliche Positionen der aktuellen Zeile durchläuft und mit valid() auf Gültigkeit überprüft. Ist eine solche Position gefunden, wird die Dame dort plaziert, und die Funktion durch sich selbst erneut aufgerufen (Rekursion). Scheitert dagegen der Versuch, eine Dame in dieser Zeile zu setzen, springt die Funktion zurück zur aufrufenden Funktion, und versucht dort eine andere gültige Position zu finden. Gibt es auch dort keine Zugmöglichkeit mehr, wird abermals zur der Funktion zurückgesprungen, durch die der Aufruf erfolgt ist. Gelingt es dagegen, alle N Damen zu positionieren, wurde eine gültige Lösung gefunden. Diese Funktion habe ich Solve() genannt:
void solve(int N,int *field) // recursion
{
 int pos,*field2;
 int queens=0;

 while(queens<N&&*(field+queens)!=-1)queens++;
 if(queens==N)
 {
   printf("%dte Loesung\n",solutions+1);
   draw(N,field);  
   solutions++;
 }  
 else
 {
   for(pos=0;pos<N;pos++)
   {
     field2=malloc(N*sizeof(int));
     memcpy(field2,field,N*sizeof(int));
     if(valid(N,field2,pos))
     {
       *(field2+queens)=pos;
       solve(N,field2);  
     }
     free(field2);
   }
 }
 return;
}

Auch dieser Funktion wird die Brettgröße N und das bisher gültige Spielfeld übergeben.

Nun ist noch eine Funktion nötig, die bei Erfolg das Spielfeld anzeigt:
void draw(int N,int *field)
{
 int m,n;
 for(n = 0; n<N; n++)
 {
   for(m = 0; m<N; m++)
   {
     if(m==*(field+n)) printf("D");
     else if( (N%2==0) && ((n*N+n%2+m)%2==0) ) printf("%c",178);
     else if( (n%2+m)%2==0 )printf("%c",178);
     else printf(" ");
   }
   printf("\n");
 }
}

Hier ein Dankeschön an Surfmaster23, der diese Funktion für mich optimiert hat.

Als letztes fehlt noch die Hauptfunktion, die ein leeres Spielfeld der gewünschten Größe N (alle Felder haben den Wert -1) erzeugt und solve() aufruft. Die Anzahl der gefundenen Lösungen wird am Ende ausgegeben.
int main(void)  
{
 int N,*field,n;
 printf("spielfeldgroesse (8 entspricht einen klassischen schachbrett) ?");
 scanf("%d",&N);
 field=malloc(N*sizeof(int));
 for(n=0;n<N;n++)
 {
   *(field+n)=-1;
 }
 solve(N,field);
 free(field);
 printf("%d loesungen gefunden.\n",solutions);
 getch();
 return 0;
}

Auf einem Schachbrett (N=8) werden 92 Lösungsmöglichkeiten gefunden. Nur 12 davon sind wirklich verschieden, der Rest kann durch drehen/spiegeln des Feldes daraus abgeleitet werden.

Hier ist der Code und das Windows-Executable als .rar Archiv zum download:
http://katze.dead-men.de/upload/49_8damen.rar

Bei Fragen oder Hinweisen bitte die Kommentarfunktion benutzen.

Gruesse von der Plapperkatze

zurück zur Kategorie "Tutorials"
[0 Kommentare]

Name


Kommentar




Bitte abtippen


 
(C) 2006-20012 Plapperkatze - 221061 Besucher seit dem 23.01.2012 Login