8 Damen

Tutorials.at
Verfügbare Informationen zu "8 Damen"

  • Qualität des Beitrags: 0 Sterne
  • Beteiligte Poster: dani93 - Xin - Metamorph - wirthi
  • Forum: Tutorials.at
  • Forenbeschreibung: Programmierforum
  • aus dem Unterforum: C / C++
  • Antworten: 11
  • Forum gestartet am: Mittwoch 19.04.2006
  • Sprache: deutsch
  • Link zum Originaltopic: 8 Damen
  • Letzte Antwort: vor 14 Jahren, 8 Monaten, 27 Tagen, 5 Stunden, 5 Minuten
  • Alle Beiträge und Antworten zu "8 Damen"

    Re: 8 Damen

    dani93 - 20.04.2008, 13:54

    8 Damen
    Hallo
    Ich muss ein Programm schreiben, dass eine Lösung des 8 Damen Problems ausgibt. Nur ich habe da irgendwie ein kleines Problem mit dem Backtracking

    Mein Code sieht so asu:

    Code:
    #include <stdio.h>
    #include <conio.h>

    int main()
    {

     int spfeld [8] [8]={{0}}, i, c, a, b, x, y, z=0, f, cc, ii;
     char ch;

     while (z<8)
     {

      for (i=0; i<8; i++)
      {

       y=0;

       for (c=0; c<8&&y==0; c++)
       {

        x=0;

        for (a=0, b=c; a<8; a++)                //senkrecht
         if (spfeld [a] [b]==1)
          x=1;


        for (a=i, b=0; b<8; b++)                //waagrecht
         if (spfeld [a] [b]==1)
          x=1;


        if (i<7&&c<7)
         for (a=i, b=c; a<8&&b<8; a++, b++)  //nach rechts unten
          if (spfeld [a] [b]==1)
           x=1;


        if (i>0&&c>0)
         for (a=i, b=c; a>=0&&b>=0; a--, b--)     //nach links oben
          if (spfeld [a] [b]==1)
           x=1;


        if (i>0&&c<7)
         for (a=i, b=c; b<8&&a>=0; a--, b++)      //nach rechts oben
          if (spfeld [a] [b]==1)
           x=1;


        if (i<7&&c>0)
         for (a=i, b=c; b>=0&&a<8; a++, b--)     //nach links unten
          if (spfeld [a] [b]==1)
           x=1;


        if (x==0&&spfeld [i] [c]==0)
        {

         spfeld [i] [c]=1;
         y=1;
         z++;

         ii=i;       //speichert Koordinaten der letzten unbedrohten Dame
         cc=c;

        }


       }


       if (y==0)               //Das --soll-- das Backtracking sein ...
       {                           //Hier vermute ich auch den Fehler...

         spfeld [ii] [cc]=2;

        if (i>1)
         i-=2;       
                                                           
       }


      }


     }



     printf ("\n\n  ");        //Da kommt nur mehr die Ausgabe

     for (ch=65; ch<73; ch++)
       printf ("%c ", ch);

     printf ("\n");

     for (i=0; i<8; i++)
     {

      printf ("%d ", i+1);

      for (c=0; c<8; c++)
      {

       if (spfeld [i] [c]==1)
         textcolor (YELLOW);

          else
            textcolor (WHITE);

        cprintf ("X ");

      }

      printf ("\n");

     }


     getch();
     return 0;

    }

    Was mache ich falsch? Ich nehme an, dass ein Fehler in meinem (versuchten) Backtracking ist. Da ich solch einen Algorithmus aber das 1. Mal verwende, kann ich keinen Fehler finden. Dabei habe ich versucht mich an diese Anleitung zu halten:
    http://books.google.at/books?id=7uwZWOMiji0C&pg=PA106&lpg=PA106&dq=8+damen+algorithmus&source=web&ots=3JlVGjqUwS&sig=42caBQyVQuVrLOFszLTFdDWozWA&hl=de#PPA106,M1



    Re: 8 Damen

    Xin - 25.04.2008, 23:26

    Re: 8 Damen
    dani93 hat folgendes geschrieben: Hallo
    Ich muss ein Programm schreiben, dass eine Lösung des 8 Damen Problems ausgibt. Nur ich habe da irgendwie ein kleines Problem mit dem Backtracking


    Moin, ich komme in letzter Zeit nicht wirklich zu was und bei deinem Problem muss ich vermutlich denken oder wenigstens kompilieren, deswegen schiebe ich das etwas vor mir her.

    Vorsichtshalber frage ich mal an, ob sich das überhaupt noch lohnt, ansonsten setz' ich's morgen für's WE mal auf die Todo-List.



    Re: 8 Damen

    dani93 - 26.04.2008, 11:40


    Es muss nicht unbedingt sein, da wir das Beispiel in der kommenden Woche noch in der Schule besprechen werden (weil es keiner einziger zustande brachte).
    Ich werde dann die korrekte Lösung hier posten.



    Re: 8 Damen

    Xin - 26.04.2008, 14:00


    dani93 hat folgendes geschrieben: Es muss nicht unbedingt sein, da wir das Beispiel in der kommenden Woche noch in der Schule besprechen werden (weil es keiner einziger zustande brachte).
    Ich werde dann die korrekte Lösung hier posten.
    Ich habe den Code grade mal auf Linux kompiliert und stelle zwei Dinge fest:
    1.) Du hast nicht bei mir programmieren gelernt. Die Formatierung ist eine Katastrophe nur gekrönt durch die Wahl der Variablennamen. Auf Deutsch: der Code ist echt scheiße zu lesen.
    Sieh es nicht als Beleidigung, sondern als Aufforderung darauf mehr zu achten, es hilft nicht nur mir beim Lesen, sondern vor allem Dir beim programmieren.

    2.) Ich habe bisher nur zwei Printfs zugefügt:
    Code:   while (z<8)
      {
        printf( "z: %d\n", z );
        for (i=0; i<8; i++)
        {
        printf( "i: %d\n", z );

    und das ist das resultat:
    Code:
    xin@morpheus:~/Personen/tutorials.at$ ./a.out
    z: 0
    i: 0
    i: 1
    i: 2
    i: 3
    i: 4
    i: 5
    i: 5
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    i: 6
    usw...


    Du hast Dir also offenbar eine Endlosschleife geschrieben.

    Ich gebe Dir erstmal zwei Tipps: Formatiere den Code sauber. 2 Leerzeichen Einrücken - immer. Zusammengehörende Klammern stehen genau untereinander.

    Suche Dir nachvollziehbare Namen. Gegen x und y spricht als Koordinaten nichts, gegan a und b aber schon. Was ist i und z? f, cc, ii...?
    Du benutzt x um zu kennzeichnen, dass Du eine Dame gefunden hast?
    Such Dir passende Namen. Kurze Namen sind super. Aber auch da gibt es ein paar Konventionen, wie i, j, k sind Integers, die man durch schleifen jagt, x,y,z sind in der Regel Koordinaten. a, b, c wird seltener verwendet, vorrangig in Berechnungen.
    Alles andere mach irgendwie lesbar. Entweder durch ausschreiben oder durch passende Kürzel oder durch überschreiben (durch Kommentare oder entsprechend benannte Funktionen).

    Anschließend lagerst Du Funktionalität in kleinen Funktionen aus. Diese vielen For-Schleifen in der Mitte Deines Algorithmus sind schlecht testbar. Du musst immer den kompletten Algorithmus testen, lagerst Du die Schleifen aus, kannst Du fragen stellen:

    Code:
    dameGefunden = dameWaagerecht( spielfeld, y )
                || dameSenkrecht( spielfeld, x )

    Pack den Algorithmus in eine eigene Funktion "damenProblem()", die Du von main aufrufst. Dann kannst Du den Algorithmus mal eben kurz auskommentieren und antesten, ob die anderen Funktionen tun, was Du von ihnen erwartest.

    PS: Wenn du den Editor Gobby hast, kann man den Code mal gemeinsam vom Ist-Zustand in einen lesbaren Zustand umbiegen. Dir wird das Programmieren und Verstehen von dem, was Du da tust dann auch leichter fallen.



    Re: 8 Damen

    dani93 - 26.04.2008, 14:45


    Ich hab inzwischen gemerkt, dass die äußerste Schleife nutzlos ist.

    Zuerst der neue Code:

    Code:
    int main()
    {

      int spfeld [8] [8]={{0}}, i, c, j, k, x, dplatziert, ldame_zeile, ldame_spalte;
     char ch;

      for (i=0; i<8; i++)
      {

       dplatziert=0;

       for (c=0; c<8&&dplatziert==0; c++)
       {

        x=0;

       
        for (j=0, k=c; j<8; j++)                //senkrecht
        {

         if (spfeld [j] [k]==1)
         {

          x=1;

         }

        }


        for (j=i, k=0; k<8; k++)                //waagrecht
        {

         if (spfeld [j] [k]==1)
         {

          x=1;

         }

        }


        if (i<7&&c<7)                                //nach rechts unten
        {

         for (j=i, k=c; j<8&&k<8; j++, k++)
         {

          if (spfeld [j] [k]==1)
          {

           x=1;

          }

         }

        }


        if (i>0&&c>0)                                      //nach links oben
        {

         for (j=i, k=c; j>=0&&k>=0; j--, k--)
         {

          if (spfeld [j] [k]==1)
          {

           x=1;

          }

         }

        }


        if (i>0&&c<7)
        {

         for (j=i, k=c; k<8&&j>=0; j--, k++)      //nach rechts oben
         {

          if (spfeld [j] [k]==1)
          {

           x=1;

          }

         }

        }


        if (i<7&&c>0)
        {

         for (j=i, k=c; k>=0&&j<8; j++, k--)     //nach links unten
         {

          if (spfeld [j] [k]==1)
          {

           x=1;

          }

         }

        }


        if (x==0&&spfeld [i] [c]==0)
        {

         spfeld [i] [c]=1;
         dplatziert=1;

         ldame_zeile=i;
         ldame_spalte=c;

        }


       }


       if (dplatziert==0)
       {

        spfeld [ldame_zeile] [ldame_spalte]=2;

        if (i>1)
        {
         i-=2;
        }

       }


      }



     printf ("  ");

     for (ch=65; ch<73; ch++)
     {
      printf ("%c ", ch);
     }

     printf ("\n");

     for (i=0; i<8; i++)
     {

      printf ("%d ", i+1);

      for (c=0; c<8; c++)
      {

       if (spfeld [i] [c]==1)
       {
        textcolor (YELLOW);
       }

          else
          {
           textcolor (WHITE);
          }

        cprintf ("X ");

      }

      printf ("\n");

     }

     getch();
     return 0;

    }

    Zu den Variablen:
    Durch die Veränderungen fielen f und z weg
    i und c sind die Koordinaten
    a und b die Koordinaten für die Überprüfung (Bedrohungen) (resetzt durch k und j)
    ii und cc speichern die Koorindaten der letzten platzierten Dame (ersetzt durch ldame_zeile und ldame_spalte)
    x prüft, ob die Dame auf den aktuellen Koordinaten bedroht ist
    y gibt an, ob in der aktuellen Zeile schon eine Dame platziert wurde (ersetzt durch dplatziert) ist ihr Wert 1 (Wahr) rückt das Programm in die nächste Zeile
    Das mit der Endlosschleife liegt am Teil den ich im ersten Beitrag mit "Backtracking" kommentiert habe. Lasse ich ihn weg, schafft das Programm 5 Damen (Was nach dem resultierenden Algorithmus auch die einzige Lösung ist).

    UND wenn du glaubst, dass irgendwas an meinem Code schei**e ist, schimpf einfach los. Aus Fehlern lernt man :roll: aber wenn mich keiner darauf aufmerksam macht, werde ich den Fehler nie erkennen. Und wenn man wie ich noch eher wenig Erfahrung mit Programmieren hat, kann man oft an kleinen Fehlern verzweifeln.



    Re: 8 Damen

    Xin - 26.04.2008, 15:33


    dani93 hat folgendes geschrieben: UND wenn du glaubst, dass irgendwas an meinem Code schei**e ist, schimpf einfach los. Aus Fehlern lernt man :roll: aber wenn mich keiner darauf aufmerksam macht, werde ich den Fehler nie erkennen. Und wenn man wie ich noch eher wenig Erfahrung mit Programmieren hat, kann man oft an kleinen Fehlern verzweifeln.
    Gute Einstellung - keine Sorge, werde ich schon machen. ;-)



    Re: 8 Damen

    dani93 - 30.05.2008, 14:14


    Die Lösung lässt auf sich warten, aber ich werde sie posten, sobald ich sie habe.



    Re: 8 Damen

    Metamorph - 30.05.2008, 15:56


    Die Einrücktiefen sollten größer sein. Standardmäßig sind 4 Leerzeichen, Linux-Quelltexte haben 8 Leerzeichen.

    So sollte es ungefähr aussehen:
    Code:
    short example(short value){
        value+=50;
        return value;
    }

    Oder so:
    Code:
    short example(short value)
    {
        value+=50;
        return value;
    }

    Das gilt auch für Schleifen und Wenn-dann-sonst-Anweisungen.
    Die Bezeichner sind immer noch schwert nachzuvollziehen. i, j und k solltest du, wie schon erwähnt, nur als Schleifenzähler benutzen.



    Re: 8 Damen

    dani93 - 30.05.2008, 16:35


    i, j, k sind schleifenzähler, da aber in den Schleifen die Koordinaten überpruft werden, dienen sie auch dazu einen Punkt festzulegen.



    Re: 8 Damen

    dani93 - 30.06.2008, 20:05


    OK, die Lösung wird es (wenn ich auf mich allein gestellt bin) wohl erst im September geben.
    Ich weiß, dass der Fehler im Backtracking lieg, aber wie genau dieser Algorithmus ausschaun soll, weiß ich nicht.



    Re: 8 Damen

    wirthi - 02.07.2008, 09:14


    Ich hacke hier schnell was hin, bitte beachten dass das Pseudocode ist und nicht getestet!
    Code: int DEPTH = 8;
    int a[DEPTH];

    void perm(int t) {
       if (t == DEPTH) {
          outputSolution();
       } else {
          perm(t+1);
          for (int i=t+1;i<DEPTH;i++) {
             int h = a[i];
             a[i] = a[t];
             a[t] = h;
             perm(t+1);   
             h = a[i];
             a[i] = a[t];
             a[t] = h;
          }
       }
    }

    int main() {
       for (int i=0;i<DEPTH;i++) a[i] = i;
       perm(0);
    }
    Das macht eine sogenannte Permutation der Einträge im Array a (d.h. sämtliche Reihenfolgen, wie die Elemente angeordnet sein könnten). Da dort (bei beispielsweise DEPTH=3) am Anfang [1,2,3] eingetragen wird, wird outputSolution 6 mal aufgerufen, mit folgenden Einträgen im Array a:
    1,2,3
    1,3,2
    2,1,3
    2,3,1
    3,1,2
    3,2,1

    Was bringt dir das? Nun, du darfst in jeder Spalte und in jeder Zeile nur eine Dame setzen. Wenn du den Array-Index als Zeilenindex des Schachbrettes und den Wert im Arrayelement als Spaltenindex ansiehst, hast du schon mal das sichergestellt. Wenn du also die Damen so positionierst wie die Permutation es verlangt, dann können sich die Damen schon nicht mehr vertikal oder horizontal schlagen. Du muss dann (nur) mehr prüfen, ob ein diagonales Schlagen möglich ist.

    Durch den rekursiven Aufruf bekommst du das Backtracking gratis mit.



    Mit folgendem Code, können Sie den Beitrag ganz bequem auf ihrer Homepage verlinken



    Weitere Beiträge aus dem Forum Tutorials.at

    Logische Verknüpfung - gepostet von Kimi am Dienstag 27.11.2007
    UPN - gepostet von niki1 am Montag 14.01.2008
    Demo Version machen ----> Wie? - gepostet von vpascal am Freitag 04.05.2007
    Client/Server - gepostet von d.d.d. am Sonntag 11.03.2007
    @DrPhil_Guth und andere Linux User - gepostet von vpascal am Montag 28.05.2007
    Schriftgrösse bei outtext im grafikmodus - gepostet von PeeDee_92 am Mittwoch 13.02.2008
    Feldinhalt löschen - gepostet von dani93 am Montag 03.03.2008
    C# ein Array von Main() ins PaintEvent kopieren - gepostet von :D am Montag 12.06.2006
    Ich Verstehe nicht was das ganze Variable ist - gepostet von Fro0zen am Sonntag 17.09.2006



    Ähnliche Beiträge wie "8 Damen"

    2.Satz (Schwierigkeitsgrad: hoch) - Kathi_Das Smiley (Dienstag 04.12.2007)
    schwierigkeitsgrad - Loku (Montag 27.11.2006)
    Schwierigkeitsgrad - raminka (Montag 19.02.2007)
    schwierigkeitsgrad - chrisi (Freitag 04.03.2005)
    Wie war der Schwierigkeitsgrad der Matheprüfung? - aushilfelehrer (Dienstag 04.04.2006)
    Schwierigkeitsgrad der missionen!?! - OG LOC (Sonntag 12.12.2004)
    Guild Wars mit erhöhtem Schwierigkeitsgrad - Lyra (Freitag 02.02.2007)
    Zunehmender Schwierigkeitsgrad! - Dux (Donnerstag 16.03.2006)
    Schwierigkeitsgrad Thermo - TobsenMH (Freitag 04.11.2005)