Hallo Carsten und Andreas,

jetzt möchte ich doch mal ein paar eigene Informationen zu dem Thema beisteuern. Schon in meiner Schulzeit hatte ich mich mit dem 8-Damen-Problem auf dem regulären Schachbrett beschäftigt und einen bekannte Algorithmus auf einem TI-58 Taschenrechner implementiert. Fragt bitte nicht, wie lange das schon her ist.

Nach meinem Studium habe ich dann rekursiven Standardalgorithmus von Niklaus Wirth (in Pascal) mit Turbo Prolog 2.0 implementiert und nach algorithmischen Verbesserungen gesucht, sodass auch für "größere" n (d. h. damals n= 20 bis 100) Lösungen gefunden wurden, allerdings auf Kosten der Vollständigkeit.

Ich hatte mit der von Andreas skizzierten Strategie Erfolg und bin zu einem selektiven Algotihmus gekommen, der direkt auf eine Lösung zusteuert und danach viele weitere Lösungen ausgibt. Es wird dabei aber nur ein geringer Prozentsatz der tatsächlich möglichen Lösungen gefunden.

Schließlich ist es mir gelungen, für die eine direkt angesteuerte Lösung eine Formel zu entwickeln. Ich werde mal auf dem Speicher nach den Unterlagen dazu suchen. Dann gebe ich euch eine Lösung für das 1000-Damen-Problem.

Für das wissenschaftliche Problem (P = NP?) sollte das aber irrelevant sein.

Grüße von Detlef