Das 8-Damen Problem
-
Tag zusammen.
Ich habe ein Problem und hoffe, dass ihr mir helfen könnt. Es geht um das 8-Damen Problem. Kennt mit Sicherheit fast jeder von euch.
Für die, die es nicht kennen:
Es geht darum 8 Damen auf einem 8x8-Schachbrettfeld so zu platzieren, dass keine Dame von einer anderen geschlagen werden kann.Und um dieses Problem zu lösen hat der Herr Gauß 1850 das Backtracking-Verfahren angegeben.
Das Prinzip von diesem Verfahren lautet wie folgt:
"Man setze von links nach rechts fortschreitend, in jede Spalte des Schachbretts eine Dame, und zwar
jedes Mal an die tiefst mögliche Stelle. Kann man in einer Spalte keine Dame mehr aufstellen, so
erhöht man den Platz der Dame in der vorhergehenden Spalte."So, und jetzt zu meinem Problem:
Ich habe schon den Code geschrieben, aber der ist anscheind nicht wirklich Fehlerfrei.Hier erstmal der Code:
bool ph(int x0,int y0) { while(x0>=0){ if(Dame[x0][y0]){ return true; } else{ x0--; } } return false; } //--------------------------------------------------------------------------- bool pd(int x1,int y1) { while(x1>=0&&y1>=0){ if(Dame[x1][y1]){ return true; } else{ x1--; y1--; } } return false; } //--------------------------------------------------------------------------- bool pd2(int x2,int y2) { while(x2>=0&&y2<=MAX){ if(Dame[x2][y2]){ return true; } else{ x2--; y2++; } } return false; } //--------------------------------------------------------------------------- bool Bedroht(int x,int y) { if(ph(x,y)||pd(x,y)||pd2(x,y)){ return true; } else{ return false; } } //--------------------------------------------------------------------------- bool Setze(int x,int y,bool &gesetzt) { if(x<MAX){ do{ while((y<MAX)&&Bedroht(x,y)){ y++; } if(y<MAX){ Dame[x][y] = true; gesetzt = true; AnsiString Ausg = "Dame "+IntToStr(x+1)+": ("+IntToStr(x)+"/"+IntToStr(y)+")"; Form1->Memo1->Lines->Add(Ausg); Setze(x+1,0,gesetzt); if(!gesetzt){ Dame[x][y] = false; y++; } } else{ gesetzt = false; Ende = true; } } while(!Ende&&gesetzt); } }
Die ersten 3 Funktionen sind die Funktionen zum Überprüfen, ob die Dame die als nächstes gesetzt werden soll von links(ph), von links unten(pd) oder von links oben(pd2) von einer anderen Dame bedroht wird. Die Ausgabe erfolgt in einem MemoFeld. Wenn ich das jetzt so durchlaufen lasse, dann bekomme ich nur die Positionen (Koordinaten) von 5 Damen ausgegeben.
Und dann würde ich gerne auch noch die anderen Möglichkeiten ausgeben lassen. Vielleicht kann man hier jemand sagen wie ich das noch machen kann.
Danke schon mal im Voraus.
mfG
-
Hallo
du kannst ja selber mal debuggen, den Ablauf des Programms Schritt für Schritt durchgehen und die Werte der Variablen überprüfen. Hier ist eine Anleitung :
http://www.junix.ch/bcb/help/debug.htmlbis bald
akari
-
Ich habe auch kein bock deinen Code zu debugen sorry .
Aber vieleicht hilft dir das.//--------------------------------------------------------------------------- #include <vcl.h> #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused #include <stdio.h> #include <stdlib.h> #define _BrettGroesse_ 16 #define _BilschirmZeilen_ 25 int LS = 1; bool Continue = true; // Prüft, ob die zuletzt positionierte Dame // von den anderen geschlagen werden kann bool DameKannSchlagen(int *Brett) { for(int Spalte = LS - 1; Spalte >= 0; Spalte--) { // Zwei Damen in der gleichen Zeile ? if (Brett[Spalte] == Brett[LS]) { return true; } // Zwei Damen auf der gleichen Diagonalen ? if (abs(Brett[Spalte] - Brett[LS]) + Spalte == LS) { return true; } } return false; } // Ermittelt die nächste Spielstellung void NeueStellung(int *Brett) { // Dame ein Feld nach oben verschieben. // Falls Brettrand erreicht, letzte Dame verschieben while ((++Brett[LS] >= _BrettGroesse_) && (LS > 0)) { LS--; } // Alle Stellungen erprobt ? Continue = (Brett[0] != _BrettGroesse_) || (LS != 0); } // Zeichnet eine Line mit Anfangs- und Endzeichen void LinieZeichnen(char AnfZn, char EndZn) { printf(" %c", AnfZn); for (int Spalte = 0; Spalte < _BrettGroesse_; Spalte++) { printf("\xC4\xC4\xC4"); } printf("%c\n", EndZn); } // Druckt ein Schachbrett aus void Drucken(int *Brett, int AnzL) { int Zeile, Spalte; // Lösung numerieren printf("\n\nLoesung Nr. %3i\n\n", AnzL); // Oberen Rand zeichnen LinieZeichnen('\xDA', '\xBF'); // Spielfeld zeichnen - Beginn for(Spalte = 0; Spalte < _BrettGroesse_; Spalte++) { printf(" %C \xB3", 'a' + _BrettGroesse_ - Spalte - 1); // Zeile zeichnen for(Zeile = 0; Zeile < _BrettGroesse_; Zeile++) { if (Brett[Zeile] == Spalte) { printf(" O "); } else if ((Zeile + Spalte) & 1) { printf("\xDB\xDB\xDB"); } else { printf("\xB0\xB0\xB0"); } } printf("\xB3\n"); } // Spielfeld zeichnen - Ende // Unteren Rand zeichnen LinieZeichnen('\xC0', '\xD9'); // Numerierung ausgeben printf(" "); for (Spalte = 1; Spalte <= _BrettGroesse_; Spalte++) { printf("%2i ", Spalte); } // Brett auf dem Bildschirm nach oben schieben for(Zeile = _BrettGroesse_ + 6; Zeile < _BilschirmZeilen_; Zeile++) { printf("\n"); } } void main(void) { int AnzLoesungen = 0; int SchachBrett[_BrettGroesse_]; // Brett aufräumen for(int Spalte = 0; Spalte < _BrettGroesse_; ) { SchachBrett[Spalte++] = 0; } // Positionen ausprobieren while (Continue) { while (DameKannSchlagen(SchachBrett)) { NeueStellung(SchachBrett); } if (LS == _BrettGroesse_ - 1) { // Eine Lösung gefunden ! AnzLoesungen++; Drucken(SchachBrett, AnzLoesungen); printf("\n RETURN fuer naechste Loesung"); while (getchar() != '\n') { /* Tastaturpuffer löschen */ }; NeueStellung(SchachBrett); } else { SchachBrett[++LS] = 0; } } printf("\nEnde der Ausgabe.\nAuf einem %ix%i-Brett existieren %i Loesungen\n", _BrettGroesse_, _BrettGroesse_, AnzLoesungen); }
P.S. Ich habe das auch nicht selber geschrieben aber es funzt (danke an den Verfasser :p )
-
Dieser Thread wurde von Moderator/in Jansen aus dem Forum Borland C++ Builder (VCL/CLX) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.