Ankündigung

Einklappen
Keine Ankündigung bisher.

Schach 8-Damen-Problem

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Schach 8-Damen-Problem

    Ich habe mich heute mit dem 8-Damen-Problem beschäftigt. Siehe https://de.wikipedia.org/wiki/Damenproblem

    Mein Ergebnis schaut folgendermaßen aus:
    PHP-Code:
    <?php
       error_reporting
    (~0);
       
       class 
    ChessQueens
       
    {
          private 
    $n// Anzahl Felder in Länge und Breite
          
    private $queens// Stack für positionierte Damen
          
    private $results// Sammlung der Endergebnisse
          
          /**
           * @param int $n > 0 Anzahl der Felder in der Länge und Breite.
           *    Ein Schachbrett hat normalerweise 8 Felder in Länge und Breite.
           */
          
    function __construct($n 8)
          {
             
    $this->$n;
             
    $this->queens $this->results = [];
             
    $this->row(0);
          }
          
    /**
           * Ob es auf diesem Feld noch keine Dame gibt und das Feld von keiner
           * Dame bedroht wird.
           * @param int $i Zeile
           *    Anzahl Zeilen > $i >= 0 
           * @param int $h Spalte
           *    Anzahl Spalten > $h >= 0 
           * @return bool
           */
          
    private function isFree($i$h)
          {
             foreach(
    $this->queens as $queenI => $queenH)
             {
                if
                (
                   (
    $dI $queenI $i) == || // Kontrolle auf gleiche Zeile
                   
    ($dH $queenH $h) == || // Kontrolle auf gleiche Spalte
                   
    abs($dI) == abs($dH// Kontrolle auf gleiche Diagonale
                
    )
                {
                   return 
    false;
                }
             }
             return 
    true;
          }
          
    /**
           * In einer Zeile nach einer Position für eine Dame suchen.
           * @param int $i Zeile
           *    Anzahl Zeilen > $i >= 0
           */
          
    private function row($i)
          {
             for(
    $h 0$h $this->n; ++$h// Spalten
             
    {
                if(
    $this->isFree($i$h)) // ob Feld unbedroht ist
                
    {
                   
    $this->queens[] = $h// Dame setzen (auf Stack legen)
                   
    if($i == $this->1// ob letzte Zeile
                   
    {
                      
    // Lösung gefunden. Positionen der Damen speichern.
                      
    $this->results[] =  $this->queens;
                   }
                   else
                   {
                      
    $this->row($i 1); // rekursiv in die nächste Zeile
                   
    }
                   
    // Ab hier bewegt man sich im Baum rekursiv rückwärts.
                   
    $queen array_pop($this->queens); // Dame entfernen (von Stack holen)
                
    }
             }
          }
          
    /**
           * Liefert die Positionen der Damen für alle Lösungen.
           * @return array mehrdimensionales Array
           *    [] array eine Lösung
           *    [][] array die Position einer Dame
           *    [][] key int Zeile
           *    [][] value int Spalte
           */
          
    function getResults()
          {
             return 
    $this->results;
          }
       }
       
       
    $chessQueens = new ChessQueens(8);
       
    $results $chessQueens->getResults();
       echo 
    "Anzahl: ",count($results),"<br />",PHP_EOL;
       echo 
    "===<br />",PHP_EOL;
       foreach(
    $results as $result)
       {
          foreach(
    $result as $i => $h)
          {
             echo 
    $i,"/",$h,"<br />",PHP_EOL;
          }
          echo 
    "---<br />",PHP_EOL;
       }
    ?>
    Kann man das in PHP noch irgendwie besser programmieren?

    Ausgangsbasis war ein Algorithmus aus dem Buch "Algorithmen und Datenstrukturen" vom dpunkt.verlag.

  • #2
    Warum glaubst du das?
    Das ?> am Ende kannst du hier weglassen...

    Kommentar


    • #3
      Kann man das in PHP noch irgendwie besser programmieren?
      Wenn du "besser" sagst, was gefällt dir denn nicht an der aktuellen Lösung?
      Über 90% aller Gewaltverbrechen passieren innerhalb von 24 Stunden nach dem Konsum von Brot.

      Kommentar


      • #4
        Ich bin bei Rekursion noch immer etwas unsicher, weil in PHP immer ein Speicherüberlauf stattfindet, wenn man Funktionen zu oft mit zu vielen Parametern rekursiv aufruft. Darum kämpfe ich fast immer damit herum, hier die beste Lösung zu finden, damit das möglichst nicht passieren kann.

        Außerdem wollte ich ursprünglich eine ganz allgemeine Klasse Chess programmieren, die dann eine statische Methode hat, die alle möglichen Damen-Positionen liefert. Aber da hatte ich wieder die Befürchtung, dass ein Überlauf stattfindet, wenn ich der rekursiven Methode zu viele Parameter übergeben.

        Bei einem normalen Schachbrett mit 8x8 Feldern wird das alles vermutlich kein Problem sein. Aber wie man in der Programmierung sieht, könnte man die Berechnungen auch mit weniger oder mehr Feldern durchführen. D. h. das Programm sollte auch bei mehr als 8x8 Feldern noch funktionieren.

        Zur Methode isFree gab es keine Vorlage im Buch. Diese Methode habe ich selbst erfunden. Wäre auch die Frage, ob das die eleganteste Lösung ist. Auch war es meine Idee, die Damen auf einen Stack abzulegen. Auf einer anderen Webseite hatte ich gesehen, dass die Damen in ein Array eingetragen wurden, das die Felder des Schachbretts repräsentiert. Dadurch wurde die Kontrolle in der Methode isFree, ob ein Feld unbedroht ist, relativ komplex. Auch das im Backtracking erforderliche Entfernen der Damen wäre vermutlich komplexer geworden.

        Kommentar


        • #5
          Willst du das später irgendwo einsetzen oder gehts für dich nur darum eine bessere Lösung zu finden?

          Kommentar


          • #6
            Ab welcher Zahl geht PHP denn der Speicher aus?
            Dieser Algorithmus braucht eigentlich recht wenig Speicher. (Wenn man es jetzt mal mit dem Standardbeispiel der Fibonacci-Folge vergelicht)

            PS: Du hast noch nen kleinen Speicherfresser eingebaut
            PHP-Code:
            $this->results[] =  $this->queens
            Das braucht exponentiell viel Speicher für größere Zahlen.

            Auch wenn es vllt. etwas gegen das EVA-Prinzip verstößt, solltest du hier schon das Ergebnis ausgeben, sei es in eine Datei, oder eben zum Browser.
            Fürs Zwischenspeichern braucht PHP z.B. für n=17 mindestens
            95 815 104 * 16Byte >1Gb Speicher!!

            PS2: Also dein IsFree() würde ich mal als optimal Programmiert sehen, was Speicher und Geschwindigkeit angeht.
            [URL="http://php.net/manual/en/migration55.deprecated.php"]mysql ist veraltet[/URL] [URL="http://php-de.github.io/jumpto/mail-class/"]Mails senden: Ohne Probleme und ohne mail()[/URL]
            [PHP]echo 'PS: <b>Meine Antwort ist keine Lösung, sondern nur eine Hilfe zur Lösung.</b>';[/PHP]

            Kommentar


            • #7
              Ich bin jetzt ein wenig neugierig geworden und die Sache mit dem Dameproblem geht mir nicht mehr aus dem Kopf. Ich bin kein Informatikstudent und in Mathe bin ich auch kein Genie , aber ich habe mir jetzt Gedanken über eine Umsetzung gemacht. Bitte erschlagt mich nicht wenn sich das, was jetzt kommt, total lächerlich anhört.

              Bei einer tatsächlichen Umsetzung wurde ich das mit Bildern und Pixeln zum Beispiel machen.

              Eine Dame würde ich als Objekt festlegen das ein Image enthält, dass größer als 8x8 Pixel ist. Hauptsache man kann genau in der Mitte ein Pixel platzieren, dass die Dame repräsentieren soll und zum Beispiel die Farbe Grün hat. Nun müsste man von der Dame aus, als vom Mittelpunkt, 2 Diagonale Linien, 1 Waagerechte und 1 Senkrechte Linie zeichnen. Die Linien bekommen dann die Farbe Rot. Der Rest des Bildes ist Transparent.

              Das Feld würde ich ebenfalls als Objekt festlegen mit einem Image, dass aber genau 8x8 Pixel groß ist.

              Jetzt würde ich das Image der Dame einfach "auf" das Image des Feldes legen, unzwar so, das die Dame(der grüne Punkt in der Mitte) auf dem Pixel 1x1 des Feldes liegt.

              Nun könnte ich überprüfen wieviele grüne Punkte ich auf dem überlappenden Gesamtbild habe. Das wäre in dem Fall 1 und würde mit der Anzahl der Objekte an Damen übereinstimmen. Als nächstes könnte ich die Position 1x1 Pixel im Dame Objekt speichern.

              Der nächste Schritt wäre ein 2. Dameobjekt zu erzeugen und das Image auf die anderen beiden Images zulegen. Wenn ich jetzt überprüfe wieviele Pixel auf dem überlappendem Gesamtbild grün sind, dann kommt als Ergebnis wieder 1 raus. Da das 2. Dameobjekt sich momentan auch an Position 1x1 Pixel befindet. Da das Ergebnis nicht stimmt zum nächsten Schritt.

              Jetzt verschiebe ich das Image einfach um 1 Pixel nach rechts. Nun überprüfe ich wieder wieviele grüne Pixel vorhanden sind und als Ergebnis kommt wieder 1 raus. Nämlich weil die roten Linien des 2. Dameobjektes den grünen Punkt des 1. Dameobjektes verdecken.

              Im Prinzip muss ich das Image nur solange verschieben bis das Ergebnis der grünen Punkte des überlappenden Gesamtbildes gleich der Anzahl meiner Dameobjekte ist.



              Wäre es Sinnvoll das ganze vielleicht auch so zu lösen oder macht es überhaupt keinen Sinn?

              Kommentar

              Lädt...
              X