Diskussion:Damenproblem

Dieser Artikel war am 6. Februar 2009 der Artikel des Tages.

Was ist eine "nicht-dominierende Dame" ?

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)

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

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)

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: $D(n)\approx n!\cdot p^{(n-1)}$ mit $p\approx 0.3885$. 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)

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)

Hab' mir die 12 eindeutigen Lösungen des 8x8-Feldes auf der englischen Wiki-Seite ([queens puzzle]) mal angesehen. Interessant, dass 'jeweils 4 Figuren auf schwarzen und weißen Feldern stehen - ein "netter" Beweis, dass eine Denksportaufgabe eines Dozenten 'unlösbar ist (nur weiße oder nur schwarze Felder)! Wird ihn ein Frühstück kosten :-) --91.19.52.178 15:23, 11. Nov. 2016 (CET)

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)

6x6-Brett

Warum gibt es auf einem 6x6-Brett so wenige Lösungen? Was ist auf dieser Art Brett so speziell?--Alexmagnus 14:30, 19. Jan. 2008 (CET)

Meine Erklärung dafür, dass es auf dem 6x6-Brett so wenige Lösungen gibt, geht wie folgt: Man kann Lösungen unterscheiden, die auch Torus-Lösungen sind, und solche, die es nicht sind. Die allermeisten Lösungen sind keine Torus-Lösungen; ich spreche hier auch von Lösungen mit Konflikten, die allerdings aufgelöst sind. "Konflikt" bedeutet dabei, dass zwei Damen auf derselben Torus-Diagonale stehen; eine solche Torus-Diagonale wird jeweils - wenn es nicht gerade eine Haupt-Diagonale (von Ecke zu Ecke) ist - in zwei Zweige geteilt, und wenn die beiden Damen in verschiedenen Zweigen stehen, dann ist der Konflikt aufgelöst.

Generell steigt die Zahl der Lösungen mit n an; dies gilt vor allem für die Lösungen mit Konflikten. Dieses Verhalten ist bei größeren Zahlen dominierend.

Bei den Torus-Lösungen gibt es "Ausfälle", also keine Lösung, wenn n durch 2 oder durch 3 teilbar ist. In der Folge ergibt das ein Auf und Ab. Die Folge beginnt früher zu wachsen, aber insgesamt ist sie viel kleiner. Dieses Auf und Ab ist bei der 6 noch zu sehen, danach geht es völlig unter.

Anschaulich wird dies eventuell, wenn man die Folge einmal aufteilt in Torus-Lösungen und Lösungen mit Konflikten.

n || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14.

Alle Lösungen: (Folge A000170) || 1 || 0 || 0 || 2 || 10 || 4 || 40 || 92 || 352 || 724 || 2680 || 14200 || 73712 || 365596.

Torus (Folge A007705) || 1 || 0 || 0 || 0 || 10 || 0 || 28 || 0 || 0 || 0 || 88 || 0 || 4524 || 0.

Lösungen mit Konflikten || 0 || 0 || 0 || 2 || 0 || 4 || 12 || 92 || 352 || 724 || 2592 || 14200 || 69188 || 365596.

(Leider ist es mir nicht gelungen, dies hier als Tabelle hinzukriegen)

So gesehen sind die zwei Lösungen bei n = 4 fast noch erstaunlicher.

--MatEngel 21:26, 11. Mär. 2008 (CET)

Lieber MatEngel, deine Erklärungen verstehe ich überhaupt nicht. Was soll denn eine Torus-Lösung sein? In der Tat gibt es aber mehrere Auffälligkeiten bei der Zahl der Lösungen als Funktion der Größe des „Schachbretts“. Ich habe daher mein eigenes Programm zur Berechnung dieser Zahlen geschrieben, um zu sehen, ob die Zahlen wirklich stimmen. Bis N=15 stimmen sie aber offenbar. Für die Zahlen N = 5,6,7,8,9,10,11 lässt sich die Sache noch einigermaßen verstehen, wenn man postuliert, dass es für ungerade Zahlen aus irgend einem Grund mehr Lösungen gibt oder anders formuliert für die geraden wie die 6 weniger. Korrigiert ich die geraden etwa nach oben und die ungeraden etwa nach unten steigen die Zahlen etwa immer um den gleichen Faktor an, wobei dieser Faktor der Zunahme leicht steigt. Die „12“ fällt dann aber total aus dem Rahmen, weil sie scheinbar viel zu hoch liegt. Als gerade Zahl sollte sie ja nach unten und nicht nach oben korrigiert werden. Ab der 12 sind aber keine Sprünge mehr zwischen geraden und ungeraden Zahlen zu erkennen. Viel leichter zu verstehen ist der Unterschied zwischen symmetrischen und allen Lösungen. Der Unterschied nähert sich immer mehr dem Faktor 8, was bedeutet, dass es zunehmend weniger symmetrische Lösungen gibt. Wer kann mir das jetzt alles mal genauer erklären.

--84.59.62.31 16:51, 8. Feb. 2009 (CET)

Lieber Unbekannter, lange habe ich hier nicht mehr hingeschaut, deswegen so spät. Eine Torus-Lösung ist eine Lösung, bei der Damen sich auch nicht schlagen, wenn sie über den Rand wandern. Weiter unten im Artikel, bei "Verwandte Problemstellungen" - "Andere Brett-Geometrie" ist erwähnt, dass Pólya dies untersucht hat. Dies ist meines Erachtens als nächst-verwandte Problemstellung zu betrachten. Es führt wohl zu weit, dies hier weiter zu erläutern; stattdessen möchte ich auf die Seite http://www.soundandsystem.de/nqueens/sub/Conflicts.en.html verweisen, wo ich dies weiter erläutert habe.

Die Beobachtung, dass das Verhältnis von allen Lösungen zu den kongruenten Lösungen im Brett (ich spreche da gerne von "unter Wirkung der Dieder-Gruppe") sich stark der Acht nähert, ist vollkommen richtig. Ich sehe zwei Gründe dafür:

• bei kleinen Brettern sind es am ehesten regelmäßige Anordnungen, die die geforderten Eigenschaften haben.
• Eine größere symmetrische Lösung erlaubt vielleicht eine kleine, lokale Änderung - und produziert damit unsymmetrische Lösungen. Ein kleiner "Web-Fehler" macht eine große symmetrische Lösung asymmetrisch. - Eventuell it es in Zukunft interessant, die "fast symmetrischen Lösungen" genauer zu betrachten.

-- MatEngel 19:56, 26. Dez. 2010 (CET)

Interessant ist das mit der Abnahme der Anzahl Lösungen des 6²-Feldes (1 eindeutige / 4 gesamt) gegenüber dem 5²-Feld (2/10) allemal - v.a. weil es offensichtich im Widerspruch zu der Prämisse des weiter unten angegebenen Backtracking-Algorithmus steht, dass nämlich JEDE Lösung eines kleinen Feldes eine ECHTE Teillösung des n²-Feldes sei..!? --91.19.52.178 13:58, 11. Nov. 2016 (CET)

Weblinks

Nachdem jetzt ein achter (an sich guter) Weblink eingefügt wurde, scheint eine Überprüfung angebracht, welche die besten sind... wahrscheinlich ist es besser, sich auch hier auf 5 zu beschränken. --KnightMove 10:23, 28. Sep. 2008 (CEST)

Über die Auswahl sollte noch einmal nachgedacht werden. Gestrichen wurde der Hinweis auf eine interaktive Seite, bei der man das Aufstellen der acht Damen ausprobieren kann. Dieser spielerische Weblink erschien mir entbehrlich, zumal es beim Damenproblem mathematisch nicht um eine einzelne Lösung geht, sondern um die Anzahl aller möglichen Lösungen. --DaQuirin 16:16, 17. Okt. 2008 (CEST)

gudn tach!

ich habe jetzt mal die anzahl der links deutlich reduziert.

hbmeyer.de habe ich nicht aufgenommen. da wird zu wenig erklaert. aehnliches gilt fuer [2], [3], [4] und [5]. da steht kaum was, was nicht auch im hiesigen artikel steht oder stehen sollte.

durch die angabe von rosettacode eruebrigen sich zudem wohl die angaben expliziter loesungen in bestimmten programmiersprachen.

wenn ich zu viel geloescht haben sollte, bitte ich um verzeihnung. in diesem fall bitte einfach wiederherstellen und hier kurz begruenden.

grundsaetzlich finde ich [6] (war/ist noch nicht verlinkt) nicht schlecht, weil es den code-verlauf visualisiert. gibt es dazu meinungen? -- seth 19:30, 9. Feb. 2019 (CET)

Artikel des Tages

Hallo, der lesenswerte Artikel wurde soeben von mir als Artikel des Tages für den 06.02.2009 vorgeschlagen. Der Termin war noch frei und das Datum scheint mir flexibel. Eien Diskussion darüber findet hier statt. --Vux 21:14, 2. Feb. 2009 (CET)

konnte => kann ? (erl.)

"dass es nicht mehr Lösungen geben konnte". Ist die Zahl der Lösungen nicht zeitunabhängig? Präsens wäre angebracht, oder? Sonst: warum nicht Futur? ("dass es nie jemals - wann auch immer - mehr Lösungen geben wird!!"). --Grey Geezer ^{nil nisi bene} 09:21, 6. Feb. 2009 (CET)

Zusatzfrage: Wieviele Damen kann man auf einem 8x8-Brett unterbringen, sodass jede die andere bedroht und wieviel Möglichkeiten gibt es dafür?

Punkt 1 wurde geändert, zu Punkt 2 würde ich mal ganz stark vermuten dass es unabhängig von der Brettgröße 4 Damen in quadratförmiger Anordnung sind. --Tinz 17:09, 8. Feb. 2009 (CET)

(1) Danke. (2) Wohl wahr, aber auch auf der Spitze stehend. --Grey Geezer ^{nil nisi bene} 09:51, 9. Feb. 2009 (CET)

Professor Layton

in dem nintendo ds spiel professor layton und das geheimnisvolle dorf kommt dieses rätsel in verschiedenen varianten vor wobei die standardvariante die schwierigste ist.es gibt außerdem eine variante in der schon figurenpositionen vorgegeben sind und mehrere auf einem kleineren feld mit weniger damen. diese information könnte hier doch auch noch rein,oder?

Ergänzung des Python Programms

Es erscheint mir sinnvoll, die folgenden 3 Zeilen dem Programm voranzustellen, oder ?:

 #!/usr/bin/python
 # -*- coding: iso-8859-15 -*-
 import os, sys

kannst Du das näher ausführen? Ich bin kein Python-Experte, aber der Sinn hier im Artikel ist ja nicht, ein möglichst "sauber programmiertes" Python-Programm zu haben, sondern eines, das auch für Leute ohne Python-Kenntnisse gut verständlich ist. Nach den Zeilen oben würden geschätzte 20% davon zu lesen aufhören, und das Programm scheint doch auch so korrekt zu laufen. --Tinz 17:51, 8. Feb. 2009 (CET)

Verständlichkeit

Ich hätte hier ein wenig Kritik:

• sollte man die Tabelle mit den Lösungen zu verschiedenen n viellleicht senkrecht einbauen? Das wäre denke ich übersichtlicher.
• ... Äquivalenz zwischen magischen Quadraten und Damenproblemen. Ja und welche?
• explizite Lösung: Den ganzen Absatz finde ich unverständlich, das sollte man überarbeiten. Unter anderem wäre eine Erklärung für die n+1-te Spalte auf einem Brett mit n Spalten angebracht. Auch sinnvoll wäre ein Beispielbild, auf dem eine funktionierende Lösung mit Startdame in der 2. Spalte zu sehen ist. Zudem sollte man das zweite Bild im richtigen Absatz positionieren.
• das N-Superdamenproblem würde ich n-Superdamenproblem schreiben.
• in Toroidales Schach steht, dass es dort keine Lösung gebe. Im Artikel finde ich anderes. Was stimmt, und wie ist das bei Zylinderschach?

--Bergi Noch Fragen? 17:38, 6. Feb. 2009 (CET)

Antwort zu Torus-Schach und Zylinder-Schach: das ist nicht wirklich ein Widerspruch. Im Artikel zum Torus-Schach (= toroidales Schach - ich bevorzuge die kürzere Version, zumal sie analog zu Zylinder-Schach gebildet ist) geht es nur um n=8, und für n=8 gibt es wirklich keine Lösung, da 8 durch 2 teilbar ist. Für das Damenproblem sind Torus-Schach und Zylinder-Schach äquivalent. Wohlgemerkt: für das Damenproblem - für ein "echtes" Spiel oder andere Probleme muss das nicht gelten. Dass diese Äquivalenz gilt, sieht man am besten daran, dass schon auf dem Zylinder alle Diagonalen die Länge n haben, wie die Reihen und Linien auch. Beim Übergang zum Torus kommt kein weiteres Feld hinzu.

-- MatEngel 19:35, 26. Dez. 2010 (CET)

Pseudocode Implementierungen Nonsence

Der mit wissenschaftlich klingenden Begriffen angereicherte Pseudocode (oder was soll das für eine Programmiersprache sein?) ist doch einfach Käse. Es wird überhaupt nicht klar, wie die Lösung berechnet wird und wieso alle Lösungen gefunden werden. Ich habe hier mal eine Implementierung in der Programmiersprache C eingefügt. Im konkreten Beispiel wird die Zahl der Lösung für 14 Damen berechnet. --84.59.227.46 11:55, 8. Feb. 2009 (CET)

#include<stdio.h>

int d(int a, int b, int c, int d){
   return (a-b)*(a-b) == (c-d)*(c-d);
}

int frei(int *x, int z, int s){
   int i;
   for (i=0; i<z; i++)
     if (x[i] == s || d(i,z,x[i],s)) return 0;
   return 1;
}

main(){
  int z=0, s=0;
  long long cnt = 0;
  int N = 14;
  int x[25];

  while (z >= 0 && s < N){
     x[z] = s;
     if ( frei(x,z,s) ) {
        z++;
        s = 0;
        if (z == N) {
           cnt++;
        }
     } else {
        s = x[z] + 1;
        while (s == N && z>0 ) {
           z--;
           s = x[z] + 1;
        }
     }
  }

   printf ("cnt = %d\n", cnt);
}

Ich habe den Code nochmals optimiert und in den Artikel geschrieben (Entwurf). --84.59.249.111 13:48, 8. Feb. 2009 (CET)

Das ist python, nicht Pseudocode. Dein Programm ist um Längen unleserlicher und unverständlicher als der Python-Code, deshalb habe ich es wieder entfernt. Außerdem reicht ein Programm völlig aus. --Tinz 17:21, 8. Feb. 2009 (CET)

python

Lieber Tinz,

ich habe Deinen „Quellcode“ hier noch einmal aufgeführt:

# Erzeuge eine Liste von Lösung auf einem Brett mit
# reihen und spalten.
# Eine Lösung wird durch eine Liste der Spaltenpositionen,
# indiziert durch die Reihennummer, angegeben.
# Die Indizes beginnen mit Null.
def damenproblem( reihen, spalten ):
    if reihen == 0:
        return [[]] # Problem nicht definiert, eine Dame auf dem nicht-existierenden Brett
    else:
        return eine_dame_dazu( reihen-1, spalten , damenproblem( reihen-1, spalten ))
 
# Probiere alle Spalten, in denen für eine gegebene Teilloesung
# eine Dame in "neue_reihe" gestellt werden kann.
# Wenn kein Konflikt mit der Teilloesung auftritt,
# ist eine neue Loesung des um eine Reihe erweiterten
# Bretts gefunden.
def eine_dame_dazu( neue_reihe, spalten, vorherige_loesungen ):
    neue_loesungen = []
    for loesung in vorherige_loesungen:
        # Versuche, eine Dame in jeder Spalte von neue_reihe einzufügen.
        for neue_spalte in range(spalten):
            # print 'Versuch: ', neue_spalte, ' in Reihe ', neue_reihe
            if kein_konflikt( neue_reihe, neue_spalte, loesung ):
                # Kein Konflikte, also ist dieser Versuch eine Loesung.
                neue_loesungen.append( loesung + [neue_spalte] )
    return neue_loesungen
 
# Kann eine Dame in neu_Spalte in neue_reihe gestellt werden,
# ohne dass sie eine der schon stehenden Damen schlagen kann?
def kein_konflikt( neue_reihe, neue_spalte, loesung ):
    # Stelle sicher, dass die neue Dame mit keiner der existierenden
    # Damen auf einer Spalte oder Diagonalen steht.
    for reihe in range(neue_reihe):
        if ( loesung[reihe]         == neue_spalte              or  # Gleiche Spalte
             loesung[reihe] + reihe == neue_spalte + neue_reihe or  # Gleiche Diagonale
             loesung[reihe] - reihe == neue_spalte - neue_reihe ):  # Gleiche Diagonale
                return 0
    return 1
 
for loesung in damenproblem( 8, 8 ):
    print loesung

Eine genaue Betrachtung zeigt, dass dieser Text weder ein sinnvoller Pseudocode noch Quellcode einer konkreten Programmiersprache ist. Dies wird rasch deutlich, wenn der Kommentar mal weggelassen wird.

def damenproblem( reihen, spalten ):
    if reihen == 0:
        return [[]] 
    else:
        return eine_dame_dazu( reihen-1, spalten , damenproblem( reihen-1, spalten ))
 

def eine_dame_dazu( neue_reihe, spalten, vorherige_loesungen ):
    neue_loesungen = []
    for loesung in vorherige_loesungen:
        for neue_spalte in range(spalten):
            if kein_konflikt( neue_reihe, neue_spalte, loesung ):
                neue_loesungen.append( loesung + [neue_spalte] )
    return neue_loesungen
 
def kein_konflikt( neue_reihe, neue_spalte, loesung ):
    for reihe in range(neue_reihe):
        if ( loesung[reihe]         == neue_spalte              or  
             loesung[reihe] + reihe == neue_spalte + neue_reihe or  
             loesung[reihe] - reihe == neue_spalte - neue_reihe ):  
                return 0
    return 1
 
for loesung in damenproblem( 8, 8 ):
    print loesung

Die deutschen Wörter in diesem Programm haben für den Compiler keine definierte Bedeutung. Eine Bedeutung wird jedoch auch nicht wirklich definiert. Der Text kann daher keineswegs eindeutig in ein Programm überführt werden. Offenbar ist Dein Text völlig sinnlos. Ich denke ich werden ihn mal löschen. --84.59.133.61 18:01, 8. Feb. 2009 (CET)

Wow, Du bist nicht zufällig der Vierfarbentroll? 1.) das ist nicht mein Programm. Ich programmiere in C, nicht in python, und trotzdem kann ich das python-Programm besser verstehen als Deines. 2.) Die deutschen Wörter sind offensichtlich Variablen/Funktionsbezeichnungen, die dürfen nämlich auch mehr als einen Buchstaben lang sein, sowas erhöht die Lesbarkeit. 3.)Schreibe den text in eine Datei "queens.py", installiere Python und führe das Programm aus, wenn Du den Code für sinnlos hältst. --Tinz 18:12, 8. Feb. 2009 (CET)

Kommentierte C-Implementierung

Das nachfolgende Programm arbeitet entsprechend dem Algorithmus, der durch die Animation auf der rechten Seite für den Spezialfall N=8 (klassisches Damenproblem) erläutert wird.

Animation des rekursiven Backtracking-Algorithmus

/**
 * Loesung des verallgemeinerten Damenproblems
 * 8 Damen im Schach auf dem Brett verteilen, die
 * sich nicht schlagen koennen.
 * Brettgroesse: 5x5, 6x6, 7x7, ..., 15x15
 */

/* benutzt Standardbibliothek zur Ein- und Ausgabe */

#include<stdio.h>

/*
 * Kann die Dame von Zeile (Reihe) a und Spalte (Linie) c
 * nach  Zeile (Reihe) b nach Spalte (Linie) d ziehen?
 * 1 = wahr, 0 = falsch
 */
int schlagbar(int a, int b, int c, int d){
   if ( c == d ) return 1;
   return (a-b)*(a-b) == (c-d)*(c-d);
}

/*
 * Wird eine Dame in Zeile z und Spalte s
 * von einer Dame in einer kleineren Zeile
 * bedroht?
 * 0 keine Bedrohung (frei)
 * 1 Bedrohung (nicht frei)
 */
int frei(int *x, int z, int s){
   int i;
   for (i=0; i<z; i++)
     if ( schlagbar(i,z,x[i],s) ) return 0;
   return 1;
}

main(){
  int i, z, s;       /* var. Zeile i, Zeile z, Spalte s */
  long long cnt = 0; /* Zaehler für Loesungen           */
  int N;             /* Brettgroesse NxN                */
  int x[25];         /* Position der Dame in Zeilen     */


  for (N=5; N<18; N++){   /* Verschiedene Brettgroessen */
  z = s = cnt = 0;        /* Anfangsbedingungen         */

  while (z >= 0 && s < N){   /* bis Dame in der oberen Zeile 0 rechts steht */
     /* Nach rechts schieben bis Feld nicht bedroht. */
     while ( (!frei(x,z,s)) && s < N-1) s++;

     x[z] = s;
     if ( frei(x,z,s) ){
        /* Wenn z gleich groesste Zeile, wurde Loesung gefunden */
        if (z == N-1) {
           cnt++;           /* Zaehler raufzaehlen              */
           x[N-1] = -1;     /* Spalte links neben dem Brett     */
           z = N-2;         /* in vorletzter Zeile fortsetzen   */
        } else {            /* letzte Zeile noch nicht erreicht */
           z++;             /* Zeile um eins erhoehen           */
           x[z] = -1;       /* Spalte linker Rand               */
        }
     }
     s = x[z] + 1;          /* Spalte eins nach rechts schieben */
     while ( s == N && z>0 ) {  /* Solange Spalte rechter Rand */
           x[z] = -1;           /* Spalte nach ganz links      */
           z--;                 /* Zeile eins vermindert       */
           s = x[z] + 1;        /* Spalte eins nach rechts     */
     }
  }
  printf ("N X N = %2d x %2d Lösungen  %7d\n", N, N, cnt);

  } /* for N */
}

--84.59.247.139 20:34, 8. Feb. 2009 (CET)

Auch nach dem Einfärben der C-Syntax bleibt das Programm hinreichen unverständlich. Ja, man kann sich erarbeiten, was diese Variablen und Funktionen sein sollen, aber der Trend geht zu "sprechenden" Variablen- und Funktionsnamen. Das erlaubt C übrigens auch. Ich mag zwar Python überhaupt nicht, aber der Code ist um Längen besser lesbar als der Zeichensalat im C-Programm da. Guandalug 14:18, 9. Feb. 2009 (CET)

Stimmt. Abgesehen davon ist das Beispiel offenbar iterativ und nicht rekursiv. Ersteres mag schneller/stack-schonender sein, und vielleicht kann man auch darüber diskutieren, ob ein iterativer Algorithmus geeigneter wäre, bzw. ob der Artikel überhaupt Codebeispiele braucht. Aber wenn die Diskussion sich auf dem Niveau "Die Variablen haben deutsche Namen, deshalb kann der Compiler (!) das Python-Programm nicht verstehen" bewegt (s.o.) sehe ich da eher schwarz. --Tinz 14:41, 9. Feb. 2009 (CET)

Du willst es nicht verstehen: Ein Bezeichner in deutscher Sprache hat in Python sicher keine vordefinierte Bedeutung. Was dieser Bezeichner bedeutet, muss daher durch den Quelltext definiert werden. Die Wahl des Bezeichner als deutsches Wort hilft vielleicht dem Leser das Programm zu verstehen, für den Compiler ist die Wahl des Bezeichners weitgehend egal, solange alle Bezeichner eindeutig benannt sind und einigen Regeln genügen. Was soll zum Beispiel "neue_loesungen.append" bedeuten?--84.59.35.104 14:03, 10. Feb. 2009 (CET)

Ich glaube, DU verstehst es nicht. NATÜRLICH hat der keine Bedeutung. Kein Variablenbezeichner DARF eine vorgegebene Bedeutung haben, sonst wäre es eine ungültige Variable. Ein paar Zeilen drüber wird allerding neue_loesung als Array/Feld definiert (neue_loesung = []). Dass danach Python weiss, was '.append' macht (nämlich anhängen), sollte doch wohl eigentlich klar sein. (Und das schreibe ich als absoluter Python-Noob - ich hab noch nie 'ne Zeile Python-Code selbst geschrieben.) Guandalug 14:15, 10. Feb. 2009 (CET)

Also versuch ich mal das nachzuvollziehen: Für jede Lösung steht in jeder Reihe eine Dame. Eine Lösung des Problems könnte durch die Angabe der Spalte für jede Reihe erfolgen. Eine Lösung wäre [0,4,7,5,2,6,1,3], wobei 0 bedeutet, dass die Dame ganz links steht. Das Python-Programm soll offenbar alle Lösungen finden. Offenbar wird die Lösung allgemein für eine feste Zahl S an Spalten und 0 bis S Reihen gesucht. Die Lösungen für eine zusätzliche Reihe neue_loesungen, wird gesucht indem zu allen Lösungen eine weitere Reihe mit der Dame in neue_spalte hinzugefügt wird. neue_loesungen ist jedoch nicht eine Lösung sondern es sind am Ende alle Lösungen (Mehrzahl) mit einer bestimmten Zahl an Reihen. Die Initialisierung sollte daher neue_loesungen == [[]] mit doppelten Klammern lauten. Interessant sind am Ende natürlich nur die Lösungen mit acht Reihen. Vor dem print sollte so etwas wie if (loesung.lenght == 8) (oder wie immer dies in Python formuliert wird) stehen. Naja, vielleicht könnte der Code dann sogar funktionieren. --88.68.96.127 11:05, 11. Feb. 2009 (CET)

Diese Algorithmus lässt sich wie folgt beschreiben: Löse das Problem P(s,r) für s Spalten und r Reihen mit r kleiner oder gleich s indem zu allen Lösungen (mit je einer Dame in jeder Reihe) in jeder der s Spalten, sofern konfliktfrei möglich, eine weitere Dame in Reihe r hinzugefügt wird, also die Lösungen P(s,r) aus den Lösungen von P(s,r-1) berechnet werden. Die Lösungsmenge für r=0 Reihen ist per Definition leer. Dieser rekursive Algorithmus kann nicht allein mit Python sondern zum Beispiel auch mit Pascal, C, C++, PHP oder Java. Allerdings ist diese rekursive Programmierung sicher nicht die effizienteste Lösung. Die hier aufgeführte C-Implementierung benötigt jedenfalls weit weniger Speicher, weil etwa die Lösungen für 5 Damen in den ersten 5 Reihen (weit mehr als 92!), die ja eigentlich niemand interessieren, nicht alle gespeichert werden. --88.68.122.99 13:28, 14. Feb. 2009 (CET)

Auffallend richtig. Wobei ich sagen muss, das Prolog-Programm im Abschnitt "Constraintprogrammierung" hat was. Kostet mich zwar auch wieder etwas Mühe, mich in die Prolog-Programmierung zurückzudenken, aber elegant ist es ;) Guandalug 14:45, 9. Feb. 2009 (CET)

Vielen Dank an Guandalug und Tinz für die Moderation. Mir wäre dies nicht so gelassen gelungen :-)

Ich fasse mal zusammen:

Ich verstehe das nicht - muss also falsch sein

Nach einigen Erläuterungen des Codes

Ändert noch dies und das am korrekten Code, dann könnte es funktionieren

Da fehlen mir die Worte - Leute gibt es 93.128.81.124 12:03, 11. Jun. 2014 (CEST)

Was bringt das Damenproblem?

Die Frage ob und wie viele Lösungen es zu diesem Problem gibt, ist zunächst ziemlich sinnfrei. Trotzdem liefert die Beschäftigung mit dem Problem Antworten auf grundlegende Fragen. Etwa die Frage, ob mit dem Computer mathematische Fragen beantwortet werden können, die ein Mensch mit Bleistift und Papier und eventuell mit einem Schachbrett inklusive Figuren nicht beantworten könnte (Computerbeweis). Die Antwort lautet eindeutig ja. Die Zahl der Lösungsmöglichkeiten für N größer 15 dürfte manuell kaum berechenbar sein. Wenn unterschiedliche Programme, unterschiedliche Algorithmen und unterschiedliche Programmiersprachen zu identischen Ergebnissen führen, können die Ergebnisse kaum bezweifelt werden. Es gibt aber offenbar auch Fragen, die mit einem Computer praktisch nicht beantwortet werden können, so etwa die Frage nach der Zahl der Lösungsmöglichkeiten für N größer 30. Die Frage nach den Lösungen für N größer 30, kann offenbar nur mit Vermutungen beantwortet werden. Scheinbar nimmt die Zahl der Lösungen mit N stark zu. Es kann aber auch nicht ausgeschlossen werden, dass die Zahl für N größer 100 wieder abnimmt. Ok, das erscheint ziemlich abwegig, aber mathematisch eindeutig zu widerlegen ist das nicht so einfach. Ebenso wie der absurde Vierfarbensatz oder die verrücke Behauptung, beim Sudoku gäbe es mehr als $6,7\times 10^{21}$ Lösungen, gar nicht so einfach zu widerlegen sind. --84.59.242.239 16:07, 8. Feb. 2009 (CET)

N-Superdamenproblem

Das folgende Programm findet die Zahl der Lösungen für das N-Superdamenproblem unter Ausnutzung der Rechts-Link-Symmetrie des Problems. --84.59.39.89 16:48, 9. Feb. 2009 (CET)

int schlagbar(int a, int b, int c, int d){

 /*
  * Superdamen koennen auch wie Springer ziehen.
  */
  if ( (c-d)*(c-d) == 1 && (a-b)*(a-b) == 4) return 1;
  if ( (c-d)*(c-d) == 4 && (a-b)*(a-b) == 1) return 1;
  if ( c == d ) return 1;
  return (a-b)*(a-b) == (c-d)*(c-d);

}

int frei(int *x, int z, int s){

  int i;
  for (i=0; i<z; i++)
    if ( schlagbar(i,z,x[i],s) ) return 0;
  return 1;

}

main(){

 int stop;          /* Kennzeichen für Ende der Berechnung */
 int i, z, s;       /* var. Zeile i, Zeile z, Spalte s */
 long long cnt = 0; /* Zaehler für Loesungen           */
 int N;             /* Brettgroesse NxN                */
 int x[25];         /* Position der Dame in Zeilen     */

 for (N=6; N<14; N++){        /* Verschiedene Brettgroessen */
 stop = z = s = cnt = 0;      /* Anfangsbedingungen         */

 while (z >= 0 && s < N){   /* bis Dame in Zeile 0. rechts steht */
    /* Nach rechts schieben bis Feld nicht bedroht. */
    while ( (!frei(x,z,s)) && s < N-1) s++;

    x[z] = s;
    if ( frei(x,z,s) ){
       /* Wenn z gleich groesste Zeile, wurde Loesung gefunden */
       if (z == N-1) {
          cnt++;
          if (x[0] < (N)/2) cnt++;
          x[N-1] = -1;     /* Spalte links neben dem Brett   */
          z = N-2;         /* in vorletzter Zeile fortsetzen */
       } else {            /* letzte Zeile noch nicht erreicht */
          z++;             /* Zeile um eins erhoehen */
          x[z] = -1;       /* Spalte ganz links */
       }
    }
    s = x[z] + 1;          /* Spalte eins nach rechts schieben */
    while ( s == N && z>0 ) {  /* Solange Spalte ganz rechts */
          x[z] = -1;           /* Spalte nach ganz links     */
          z--;                 /* Zeile eins vermindert      */
          if ( z == 0 && x[z] >= (N-1)/2 ) stop = 1;
          s = x[z] + 1;        /* Spalte eins nach rechts    */
    }
    if (stop) break;
 }
 printf ("N X N = %2d x %2d Lösungen  %7d\n", N, N, cnt);

}

Explizite Lösung

Der Abschnitt ist ziemlich unverständlich für mich. Hat vielleicht jemand Zugriff zu dem Paper von Bernhardsson? [7] --Tinz 14:33, 10. Feb. 2009 (CET)

Ich glaube, ich weiss, wie der funktionieren soll. Da fehlt aber auf jeden Fall die Erwähnung des "Wraparound" an der Kante (rechts -> links). Ist aber schlecht beschrieben. Guandalug 14:52, 10. Feb. 2009 (CET)

ok, danke, ich denke ich weiß es jetzt auch. Die Diagramme dazu sind auch noch verbessernswert, die hatten mich in die Irre geleitet zumal die jeweilige Anzahl der Damen (4/8, 6/8) so erstmal keinen Sinn macht. --Tinz 19:41, 10. Feb. 2009 (CET)

Die Ergänzung macht's klarer, ja. Müsste so stimmen. Guandalug 19:46, 10. Feb. 2009 (CET)

Hallo zusammen. Stimmt leider nicht. Es gibt überhauptkeinen "Algorithmus von Bernhardsson"!. In der zitierten Quelle hat Bernhardsson lediglich in einem Letter to the Editor auf eine Veröffentlichung aus dem Jahr 1969 aufmerksam gemacht. Zudem ist das Verfahren hier im Artikel auch falsch dargestellt, was man sich am gängingen 8-Damen Problem auch leicht veranschaulichen kann, es kommt keine gültige Lösung raus. (Edit: Naja, wenn man den "schlägt dies fehl" Absatz befolgt schon. Allerdings ist das etwas schwammig formuliert. Das eingangs erklärte Verfahren gilt dann, wenn n != 6k + 2 ist). Man sollte den Absatz in dieser Form entfernen. Nebenbeibemerkt: Wie kann ein Artikel mit derart gravierenden Fehlern als "Lesenswert" gekennzeichnet sein? --DownAnUp 17:13, 8. Aug. 2011 (CEST)

Wurde 2005 lesenswert. Damals waren sowohl die Kriterien als auch die durchschnittliche Wikipedia-Artikelqualität auf deutlich geringerem Niveau. Ich glaube nicht, dass eine Wiederwahl gelingen würde. --Con^structor 23:13, 8. Aug. 2011 (CEST)

Ich habe es mal überarbeitet. Den Fall n = 6k+2 muss man m.E. nicht unbedingt hier aufführen, kann man ja bei Interesse in den Papern nachlesen. --Tinz 16:59, 19. Aug. 2011 (CEST)

Wo ist das Problem?

Für n=26 sollte es etwa 10 mal so viele Lösungen geben wie für n=25. Die Zahl der Lösungen wurde für n=25 bereits 2005 gefunden. Die Leistung eines handelsüblichen Rechners hat sich in dieser Zeit ebenfalls fast verzehnfacht. Warum wurde die Lösung für n=26 nicht schon längst gefunden. Dies sollte doch kein Problem sein, selbst wenn die Software nicht wesentlich verbessert wurde. --88.68.126.248 21:48, 14. Feb. 2009 (CET)

Das Problem ist wohl, dass es eine Menge wichtigere und sinnvollere Probleme gibt, die man mit viel Rechenzeit lösen kann. --Tinz 14:32, 11. Mai 2009 (CEST)

Och, wenn es "kein Problem" für dich ist, tipp einen der hier angegebenen Codes ab und gib' für n 30, 50 o 100 ein. Viel Spaß :-) ! Melde dich bitte hier, wenn der Rechner fertig ist - so in 5-10 Jahren (Schätzung)... ^^ --91.19.52.178 15:05, 11. Nov. 2016 (CET)

Superdamenproblem - Lösungen

Hallo,

eigentlich müsste doch die Lösung für n = 1 Dame = 64 sein, weil man sie auf jedem Feld platzieren kann. Im Artikel steht allerdings 1. Habe ich mich geirrt oder ist es tatsächlich ein Fehler?

MfG 93.213.49.110 11:06, 30. Apr. 2009 (CEST)

Kein Fehler, es sind immer n Damen auf einem nxn-Feld, 64 Felder hat das Brett nur für n=8. --Tinz 11:14, 30. Apr. 2009 (CEST)

(BK) Das n=1 - Brett hat nur ein einziges Feld. Da würde es für 64 Damen aber sehr eng ;-)) --tsor 11:16, 30. Apr. 2009 (CEST)

Achso. Okay 93.213.49.110 12:29, 30. Apr. 2009 (CEST)

Eine weitere Lösung in SWI-Prolog,

Hallo Welt.

Nachdem ich mir Eure Lösungen angesenen habe, hier noch eine weitere Lösung. Sie basiert auf der Überlegung, daß man die Damen ohne weiteres so auf dem Brett anordnen kann, daß sie sich auf den Spalten und Zeilen nicht schlagen. Dies erreicht man zunächst durch Anordnung auf der Diagonalen (als Liste dargestellt als [1, 2, 3 ...]). Bildet man diese Liste auf ein Schachbrett ab, so entspricht der ListenIndex (ab 1 gezählt) der einen Achse, der Wert der jeweiligen Zelle der anderen Achse. Dort kommt dann die Dame hin.

Permutiert man diese Liste, so erhält man alle möglichen Stellungen, in denen sich die Damen auf Zeilen und Spalten nicht schlagen würden. Filtert man jene Stellungen heraus, auf denen sich die Damen auf den Diagonalen schlagen, verbleiben die Lösungs-Stellungen des Problems.

 % Prüfung der Kollisionen der Liste:
 
 collides( [_]) :- fail.
 collides( [H | T]) :- nth1( IDX, T, I), ( 0 is IDX - abs( H - I), !; collides( T), !).
 
 % Permutation der Schachbrettstellungen (hier fuer das 5-Damen Problem)
 
 permutation( [1, 2, 3, 4, 5], SOLUTION), not( collides( SOLUTION)).
 
 % und fertig.

Programmausführung: Wer linux hat, kann weitestgehend Stressfrei SWI-Prolog nutzen, unter gentoo heist das binary pl , unter debian swipl (auf der Konsole). Unter anderen Prolog-Implementationen sind geringfügige Anpassungen notwendig.

Los gehts, wir starten pl oder swipl:

 $ pl
 Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.62)
 Copyright (c) 1990-2008 University of Amsterdam.
 SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
 and you are welcome to redistribute it under certain conditions.
 Please visit http://www.swi-prolog.org for details.
 
 For help, use ?- help(Topic). or ?- apropos(Word).
 
 ?- [user].
 |: collides( [_]) :- fail.
 |: collides( [H | T]) :- nth1( IDX, T, I), ( 0 is IDX - abs( H - I), !; collides( T), !). % Enter und Ctrl-D eingeben
 |: % user://1 compiled 0.01 sec, 656 bytes
 true.
 
 ?- permutation( [1, 2, 3, 4, 5], SOLUTION), not( collides( SOLUTION)).
 SOLUTION = [3, 1, 4, 2, 5] ; % für jede Lösung ein semikolon eingeben
 SOLUTION = [2, 4, 1, 3, 5] ;
 SOLUTION = [4, 1, 3, 5, 2] ;
 SOLUTION = [1, 4, 2, 5, 3] ;
 SOLUTION = [4, 2, 5, 3, 1] ;
 SOLUTION = [1, 3, 5, 2, 4] ;
 SOLUTION = [3, 5, 2, 4, 1] ;
 SOLUTION = [2, 5, 3, 1, 4] ;
 SOLUTION = [5, 3, 1, 4, 2] ;
 SOLUTION = [5, 2, 4, 1, 3] ;
 false.
 
 ?-

Wer eine bequemere Bedienung haben möchte, programmiert sich noch ein Prädikat, dem man nur noch die Problemgrösse als Zahl übergeben muss:

 solve_the_dame_problem( NUM, SOLUTION) :-
  numlist( 1, NUM, DAMES),
  permutation( DAMES, SOLUTION),
  not( collides( SOLUTION)).

Und startet wie folgt:

 ?- solve_the_dame_problem( 6, S).
 S = [4, 1, 5, 2, 6, 3] ;
 S = [5, 3, 1, 6, 4, 2] ;
 S = [2, 4, 6, 1, 3, 5] ;
 S = [3, 6, 2, 5, 1, 4] ;
 false.

Das wars für heute. (nicht signierter Beitrag von Schmofarz2 (Diskussion | Beiträge) 13:37, 2. Aug. 2009 (CEST))

Code in Java

Wie wäre es denn, wenn man den Code in Java programmieren würde? --Jobu0101 17:38, 16. Nov. 2009 (CET)

Gelöschter c# code

Hey!

Wollte nur mal nachfragen, warum mein C# geklöscht bzw. nicht übernommen wurde? Hier ist meine Implementierung nochmal zum "nachlesen":

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Damen_Problem
{
class Program
{
static int[] x = new int[8];
static int glob_aufruf = 0;
public static void Main(string[] args)
{
call_try(0);
Console.WriteLine("\n\nEs gibt im 8er System insgesamt {0} Lösungen!\n",glob_aufruf);
}

/* prints field */
public static void call_print()
{
int i,j;
Console.Write ("+----------------+\n");

for (i=0; i<8; i++)
{
Console.Write ("|");
for (j=0; j<8; j++)
{
if (j == x[i])
{
Console.Write("<>");
}

else
{
Console.Write(" ");
}
}
Console.Write("|\n");
}
Console.Write("+----------------+\n\n");
}

/* tests, whether (ix, iy) is beaten by queens 0...(iy-1) */
public static int is_free (int ix, int iy)
{
int i;
for (i = 0; i < iy; i++)
{
if ((x[i] == ix) || (Math.Abs(x[i] - ix) == Math.Abs(i - iy))) return 0;
}
return 1;
}

/* tries to place queen n on row n */
public static void call_try (int n)
{
int i;
if (n==8)
{
call_print();
glob_aufruf++;
}

else
{
for (i=0; i<8; i++)
{
if (is_free(i,n)==1)
{
x[n]=i;
call_try (n+1);
}
}
}
}
}
}

-- Kallinger 08:49, 21. Okt. 2010 (CEST)

Ich habe den Text gelöscht, weil es nicht Aufgabe des Artikels ist, Programme in allen Programmiersprachen der Welt darzustellen. Die aktuellen Beispiele sind da mehr als ausreichend, vielleicht sollte man sogar sie entfernen und stattdessen Links setzen auf eine der vielen Webseiten im Netz. So hat es die englische Wikipedia gelöst, die früher auch mal die Beispiele im Artikel hatte. Denn in dem Artikel geht es nunmal primär um das Problem, und nicht darum, möglichst viele Implementationen eines rekursiven Algorithmus in speziellen Programmiersprachen darzustellen. --Tinz 21:18, 19. Okt. 2010 (CEST)

Laufzeitkomplexität

Welche Laufzeitkomplexität hat das Backtracking-Verfahren zur Lösungssuche? --MartinThoma 09:39, 23. Mär. 2011 (CET)

Die Laufzeit bis zum Finden einer Lösung (bis zum Finden aller sowieso) wächst exponentiell mit N, siehe z.B. [8]. --Tinz 20:53, 22. Aug. 2011 (CEST)

Darstellung "Geschichte" unrichtig?

Im Abschnitt "Geschichte" heißt es:

Erstmals formuliert wurde das Damenproblem von dem bayerischen Schachmeister Max Bezzel. In der Berliner Schachzeitung fragte er 1848 nach der Anzahl der möglichen Lösungen.

1. In der Berliner Schachzeitung 1848 (S. 363) wurde jedoch nicht nach der Anzahl der möglichen Lösungen gefragt, sondern nach der Höchstzahl der Damen (also acht).

2. Der Name Bezzel wird nicht genannt.

Der Redakteur der Schachzeitung leitete die Frage mit dieser Bemerkung ein: "Vor einiger Zeit wurden uns von einem Schachfreunde zwei Fragen vorgelegt, die wir, weil sie in das Fach der Probleme gehören, unsern Lesern mittheilen."

(Die zweite Frage betrifft dann ein anderes Problem, nämlich wie die acht Figuren derselben Partei so aufzustellen seien, dass sie die höchstmögliche Zügezahl zur Auswahl hätten.)AndreasLangeSCK 01:38, 1. Mai 2011 (CEST)

Max Bezzel publizierte das Problem bekanntlich unter Pseudonym, das später (von Max Lange?) offengelegt wurde. Die Frage lautete, auf welche Weisen "es möglich sei, acht Schachfiguren, von denen jede den Rang einer Königin hat, auf dem Brett so aufzustellen, dass keine von der anderen geschlagen werden kann" (zitiert nach Ganter [9]). Es wäre interessant zu wissen, ob die originale Formulierung davon abweicht. Erst als definitiv alle Lösungen gefunden waren (bzw. mathematisch bewiesen war, dass es darüber hinaus keine weiteren geben könne), war das "Achtköniginnenproblem" gelöst. --DaQuirin 16:10, 10. Aug. 2011 (CEST)

PS zur Urheberschaft: "nach einer directen persönlichen Mittheilung" (von Bezzel), so Max Lange (Handbuch der Schachaufgaben, S.30). So ist es dann in die mathematische und Schachliteratur eingegangen. --DaQuirin 16:40, 10. Aug. 2011 (CEST)

Ein Widerspruch ?

Im Abschnitt "Geschichte" lese ich: 1991 wurde von B. Bernhardsson eine explizite Lösung des n-Damen-Problems für jede beliebige Brettgröße im ACM SIGART Bulletin, Vol. 2, No. 7, angegeben. Weiter unten freut man sich, dass die Lösungszahl für n=26 wurde am 11. Juli 2009 ... bestimmt wurde. Wie das? Die Lösung gab es doch bereits 1991? --tsor (Diskussion) 21:09, 9. Okt. 2012 (CEST)

Berechtigte Frage. So wie ich die Sache verstanden habe, gibt es einen Unterschied zwischen "Lösungen" und "expliziten Lösungen". Diesen Unterschied müsste jemand erläutern, der sich auskennt. --Echoray (Diskussion) 22:54, 9. Okt. 2012 (CEST)

gemeint ist, dass es viele verschiedene Lösungen gibt fürs Damenproblem auf einem Brett fester Größer. Nun kann man entweder deren Anzahl bestimmen, oder man kann eine einzige der vielen Lösungen (Damenproblem#Explizite_L.C3.B6sung) beschreiben, also kein Widerspruch. Aber der Satz zu Bernhardson ist noch aus einem anderen Grund fehl am Platze (Diskussion:Damenproblem#Explizite_L.C3.B6sung), der entsprechende Abschnitt ist schon länger nicht mehr da, nur in der Einleitung wurde das vergessen. Deshalb entferne ich das mal. --Tinz (Diskussion) 23:07, 9. Okt. 2012 (CEST)

Clay-Preis

Im Text steht „Für diese Problemstellung haben Mathematiker des Clay Mathematics Institutes 1 Million Dollar für denjenigen ausgelobt, der einen Lösungsalgorithmus findet. Prof. Ian Gent (University of St Andrews) formuliert die Problemstellung: Wenn einige Damen bereits auf einem n-zu-n-Schachbrett gesetzt sind, kannst du das n-Damenproblem dann lösen, ohne die gesetzten zu bewegen?“. Naja, da schreibt die „WeLT“ doch ein wenig reißerisch. Gemeint ist der Preis für die Klärung der Frage, ob P=NP ist oder (wie fast alle theoretischen Informatiker heutzutage vermuten) eben nicht. Der Gesprächspartner der WELT hat wohl lediglich vorgetragen, dass dieses Problem beweisbar NP-vollständig ist. Und imho darf die Aussage dann in den Artikel, zur Not mit diesem Beitrag der WeLT als erläutertem Einzelnachweis. --Himbeerbläuling (Diskussion) 19:25, 13. Mai 2021 (CEST)