Diskussion:Damenproblem

aus Wikipedia, der freien Enzyklopädie

Kann jemand bestätigen, dass das Damenproblem effizient rekursiv lösbar ist? Sonst werde ich den entsprechenden Abschnitt entfernen. -- Schewek 22:08, 20. Jun 2005 (CEST)

Abschitt Constraintprogrammierung: Es wäre sinnvoll bei Programmbeispielen die Sprache mitanzugeben. (Da es sich hier wohl nicht um Pseudocode handelt, würde man es selbst gerne Testen; ohne zu Wissen um Welche Sprache es sich handelt ist das aber kaum mögich. --85.181.39.222 20:28, 11. Sep 2006 (CEST)

Inhaltsverzeichnis 1 Lesenswert-Diskussion 2 Zählen aller Lösungen 3 Verhältnis zur Zahl der Türme 4 Alle Lösungen 5 APL

[Bearbeiten] Lesenswert-Diskussion

Das Damenproblem ist eine Denksportaufgabe: Man finde eine Stellung für acht Damen auf einem Schachbrett, derart dass keine zwei Damen sich gegenseitig nach den Regeln des Schach schlagen können.

• pro - sehr netter Artikel zu einem Problem, an dem sich fast jeder schonmal versucht hat.-- Achim Raschka 14:12, 25. Sep 2005 (CEST) sig nachgetragen Brummfuß
• Pro - ich folge Deinem Urteil. (Allenfalls - heißt, was hier "Superdame" genannt wird, im Feenschach nicht "Amazone"?) -- €pa 14:07, 26. Sep 2005 (CEST)
• pro - an der Grenze. Da ich mich an dem Problem noch nicht "versucht habe" und daher die Problematik nur ahnungsweise erfassen kann, fehlt mir ein Teil, der die Schwierigkeit des Problems/der Problemlösung darstellt. --Lienhard Schulz 14:27, 26. Sep 2005 (CEST)
• Pro norro 00:20, 28. Sep 2005 (CEST)
• Pro - interessant - vor allen Dingen wegen dem Python script. Ich habe es gegen mein eigenes Script getestet und (yeah) meines ist schneller! Warum? - Ich denke es liegt an der Art der Implementierung:
  • Queen als Objekt vermeidet, daß ständig benötigte Daten als Parameter an Funktionen weitergereicht werden - eben besonders zeitlastig bei Algortihmen!
  • Etwas, was ich nicht so recht bewerten kann: Mein Ansatz ist nicht die Betrachtung der Teillösungen, sondern die Überprüfung der besetzten Spalten und Diagonalen; wenn eine Position frei ist, dann wird sie besetzt! Ob das zeitlich ein besserer Ansatz ist, oder ob der vorige Punkt die bessere Zeit bringt - keine Ahnung!
  • Übrigens sollte bei der Betrachtung der Leistung des Algorithmus die Ausgabe weggelassen werden. In meiner Implementierung ist Berechnung (aller Lösungen) und Ausgabe getrennt! (natürlich habe ich zum Vergleich mit dem hiesigen Script die Zeitmessung für Berechnung+Ausgabe gemacht!

import time
# author      Thomas Lehmann
# file        Queen.py

OCCUPIED = 1  # constant
FREE     = 0  # constant

class Queen:
   def __init__(self, width = 8):
       self.m_iWidth           = width
       self.m_Columns          = self.m_iWidth * [ -1 ]

       self.m_CountOfDiagonals = 2 * self.m_iWidth - 1
       # locked diagonals
       self.m_Diagonals1       = self.m_CountOfDiagonals * [ 0 ]
       self.m_Diagonals2       = self.m_CountOfDiagonals * [ 0 ]
       # list of solutions
       self.m_Solutions        = []

   # searches for all possible solutions
   def calculate(self, iRow = 0):
       for iColumn in range(self.m_iWidth):
           # is column OCCUPIED by a queen?
           if self.m_Columns[iColumn] >= 0:
               continue

           # relating diagonale '/' depending on current row and column
           ixDiag1 = self.m_iWidth - 1 - iRow + iColumn
           # relating diagonale '\' depending on current row and column
           ixDiag2 =                     iRow + iColumn

           # is one of the relating diagonals OCCUPIED by a queen?
           if self.m_Diagonals1[ixDiag1] == OCCUPIED:
               continue
           if self.m_Diagonals2[ixDiag2] == OCCUPIED:
               continue

           # occupying column and diagonals depending on current row and column
           self.m_Columns   [iColumn] = iRow
           self.m_Diagonals1[ixDiag1] = OCCUPIED
           self.m_Diagonals2[ixDiag2] = OCCUPIED

           if iRow == self.m_iWidth-1:
               # all queens have been placed - remembering solution!
               self.m_Solutions.append(self.m_Columns[0:])
           else:
               # trying to place next queen...
               self.calculate(iRow + 1)

           # FREEing column and diagonals depending on current row and column
           self.m_Columns   [iColumn] = -1
           self.m_Diagonals1[ixDiag1] = FREE
           self.m_Diagonals2[ixDiag2] = FREE

if __name__ == '__main__':
   QueenInst = Queen(8)
   print "Queen raster (%dx%d)" % (QueenInst.m_iWidth, QueenInst.m_iWidth)
   Start = time.time()
   QueenInst.calculate()

   print "... calculation took %f seconds" % (time.time() - Start)
   print "... with %d solutions" % (len(QueenInst.m_Solutions))

   # output of solutions
   for Solution in QueenInst.m_Solutions:
       Line = ""
       for ix in range( len(Solution) ):
           Line += "(%d,%d)" % ( ix+1, Solution[ix]+1 )
       print Line

--Thomas Lehmann

[Bearbeiten] Zählen aller Lösungen

Mir kommt es komisch vor, daß es für ein 1x1-Brett eine Lösung gibt (klar, eine Dame auf dem einen Feld), nach der Tabelle aber für das 2x2 und 3x3-Feld keine. Da muß doch auch jeweils eine Dame möglich sein. Wenn das ein Fehler ist, bitte korrigieren, wenn nicht, bitte das Phänomen erklären. Danke. --Silberchen ••• 21:04, 9. Feb 2006 (CET)

Das Problem ist so definiert, dass man auf einem n x n großen Feld n Damen unterbringen kann, ohne dass es welche gibt, die sich schlagen können. Also auf 1x1 eine (trivial), auf 2x2 zwei (auch klar, dass es nicht geht) uns so weiter. Gruß, --Tinz 21:08, 9. Feb 2006 (CET)

Ah, ok... wer lesen kann, ist klar im Vorteil... danke für die schnelle Erklärung --Silberchen ••• 21:19, 9. Feb 2006 (CET)

[Bearbeiten] Verhältnis zur Zahl der Türme

Ich habe gerade eine Diskussion laufen, ob das in dem Artikel stehen darf. Würden bitte andere Leser des Artikels eine Stellungnahme abgeben, ob sie dieses Faktum für den Artikel interessant finden? --KnightMove 14:41, 10. Jul 2006 (CEST)

Für die Zahl der Türme ist die geschlossene Formel allgemein bekannt: n! Da eine Dame "mächtiger" ist als ein Turm, also zusätzlich zu den Turmbewegungen noch die des Läufers ausführen darf, stellt dies gleichzeitig eine (triviale!) obere Schranke für das Damenproblem dar. --Warnke 04:36, 9. Aug 2006 (CEST)

Hallo, der Artikel ist lesenswert. Wenn Du irgendwelche mathematischen Erkenntnisse da hereinbringen möchtest, dann bitte nur mit Quelle. Wieso das Verhältnis 0,39 sein soll, wird so nicht deutlich. --Tinz 00:29, 10. Jul 2006 (CEST)

Ich kann keine Quelle angeben, denn das ist eine Eigenbeobachtung. Warum das Verhältnis 0,39 ist, weiß ich nicht, ich habe nur festgestellt, DASS es so ist. Aber das ist ja keine unrelevante Information, oder? --KnightMove 10:54, 10. Jul 2006 (CEST)

Doch, leider schon. Das Thema, wie die Folge der Lösungen für große n asymptotisch verläuft, ist natürlich interessant und auch Gegenstand der Forschung. Aber dass sie einen Faktor n! enthält, dass gerade das Verhältnis zur Anzahl der Türme bedeutend sein soll, ist unklar. Aber ganz abgesehen davon, zu einem Problem über das sich so viele Mathematiker, von Euler bi zu heutigen [1], Gedanken gemacht haben, sind eigene Forschungen ganz besonders fehl am Platz in einer Enzyklopädie, siehe WP:WWNI Punkt 2. --Tinz 11:20, 10. Jul 2006 (CEST)

Warten wir noch die Diskussion aus Wikipedia:Verbesserungsvorschläge ab. --KnightMove 14:21, 10. Jul 2006 (CEST)

Es gibt tatsächlich eine Quelle für die 0,39, allerdings handelt es sich um eine unbewiesene Vermutung!!! Siehe hierzu http://www.research.att.com/~njas/sequences/A000170 dort findet sich das Conjecture: "there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n;" wenn man nun einfach 1/c^n anders darstellt, kommt man auf 1/c^n=(1/c)^n=(1/2,54)^n = (0,39)^n. Neuere Zahlen (n>=20, insb. n=25) lassen aber darauf hindeuten, dass dieses Conjecture nicht ganz stimmt, vgl. hierzu http://web.telecom.cz/vaclav.kotesovec/math.htm ; Da erscheint ein anderes Conjecture nach den aktuellen Zahlen glaubwürdiger: mit . Aber auch hierbei handelt es sich nur um eine Vermutung! Eine geschlossene Formel für die Anzahl der Lösungen zu finden, ist in der Tat eine offene Forschungsfrage! --Warnke 13:42, 9. Aug 2006 (CEST)

[Bearbeiten] Alle Lösungen

Mich würden ALLE eindeutigen Lösungen (ohne Drehungen und Spiegelungen) interessieren. Kennt die jemand und kann sie einbauen bitte? --KnightMove 16:00, 11. Dez. 2006 (CET)

Schau mal auf :en, da sind alle gelistet (Du meinst sicher n=8?!). Einbauen wäre also einfach... --Tinz 16:18, 11. Dez. 2006 (CET)

ok. --KnightMove 16:57, 11. Dez. 2006 (CET)

[Bearbeiten] APL

"Noch kompakter ist eine nicht-rekursive, non-skalare Lösung mit selbstmodifizierendem Code in der Programmiersprache APL. Sie benötigt nur 1 (!) Zeile, lässt sich hier aber aufgrund des besonderen APL-Zeichensatzes nicht darstellen."

Was für eine faule Ausrede. Kann jemand den Code als Bild abspeichern und hochladen? --192.108.114.19 16:26, 16. Dez. 2006 (CET)