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.html

    bis 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.


Log in to reply