[heise.de] 26-Damen-Problem gelöst

[-horn-]

26-Damen-Problem gelöst

Die Aufgabe, acht Damen so auf einem Schachbrett zu platzieren, dass sich keine davon gegenseitig schlagen können, läuft früher oder später jedem Informatik-Erstsemester über den Weg. 92 Möglichkeiten gibt es, und ein aktueller PC benötigt ungefähr null Sekunden, um sie alle auszurechnen. Doch wie bei vielen kombinatorischen Problemen werden die Zahlen und damit die Zeiten, sie zu ermitteln, schnell gigantisch, wenn man die Aufgabe größer macht: Wie viele Möglichkeiten gibt es, n Damen bedrohungsfrei auf einem n×n-Schachbrett zu platzieren?
...

Den Rest der Nwws gibt es hier http://www.heise.de/newsticker/26-Damen ... ung/142206

[Thommy3]

Interessanter Ansatz. Das Projekt NQueens rechnet ja noch daran.

[gardenone]

Es soll ja jeder rechnen was er möchte, aber dafür würde ich noch nicht ein einziges Watt zur Verfügung stellen!

Worin besteht der Nutzen eines solchen Projektes?
Was kann damit erreicht werden?

[Dennis Kautz]

Interessanter Ansatz. Das Projekt NQueens rechnet ja noch daran.

Dann sollten sie damit aufhören.

[-horn-]

moien,

Es soll ja jeder rechnen was er möchte, aber dafür würde ich noch nicht ein einziges Watt zur Verfügung stellen!

Worin besteht der Nutzen eines solchen Projektes?
Was kann damit erreicht werden?

ich berechne auch keine schachprobleme. es liegt aber nicht daran, dass ich das für sinnlos halte, interessieren tut mich das schon. nur wäge ich immer ab, wo ich mit mache, denn überall mitmachen kann ich ja auch schliesslich nicht. deswegen kommt zum interessieren noch der punkt hinzu, ob ich es für nützlich halte und da bin ich dann doch der meinung, dass ich zb. bei der krankheitsbekämpfung sinnvoller mitarbeiten kann.

Interessanter Ansatz. Das Projekt NQueens rechnet ja noch daran.

Dann sollten sie damit aufhören.

auf der halben strecke aufgeben? . ias dennoch zu ende rechnen lassen, denn man kann ja damit dann das andere ergbnis bestätigen.

grüße, Andreas

[LinuxFan]

Zum Bestätigen guckst du einfach auf die Lösung und musst sie nicht extra ein zweites Mal finden

[EdmundBlackadder]

Als Laie verstehe ich das so: Wenn ich das vom Schach abstrahiere, kann NQueens vielleicht bei der Logistik wie z.B. TSP oder anderen Fragen der Logik helfen. Natürlich sollte NQueens sofort den Durchlauf mit n=26 beenden. NQueens wäre somit komplett überflüssig, denn Queens@TUD bereitet bereits n=27 vor. Oft ist zweimal nachdenken (Queens@TUD) doch besser als brute force (NQueens). Mit anderen Worten: Das Problem ist nicht effizient mit BOINC zu lösen, sondern nur mit Spezial-HW.
Das Projekt Queens@TUD wurde von Studenten an der TU Dresden durchgeführt, und diente Linie Forschungs- und Schulungszwecken.

[LinuxFan]

Spezial-Hardware ist nicht der Punkt, denn damit gewinnst du nur einen konstanten Faktor. (z.B. 1000 FPGAs = Faktor 1000)

Erfolgversprechender sind Techniken aus der KI, so lässt sich das n-Damenproblem zum Beispiel gut als CSP (Constraint Satisfaction Problem, siehe http://de.wikipedia.org/wiki/Constraint ... on-Problem) formulieren. Allerdings muss man dann ziemlich viel Grips in die Parallelisierung stecken, vermute ich.

[nico]

Mit anderen Worten: Das Problem ist nicht effizient mit BOINC zu lösen, sondern nur mit Spezial-HW.

Das hast aber mit so gut wie allen Problemen...FPGAs sind für spezielle Probleme immer schneller als General Purpose CPUs allerdings kosten die auch eine ganze Stange Geld und Entwicklungszeit. Mal eben ein C Programm schreiben ist da nicht - da ist VHDL angesagt. Die "Compilierung" für den FPGA kann dann auch paar Stunden dauern (u.a. weil z.B. Xilinx es nicht fertig bringt das ganze auf einem SMP zu parallelisieren und es keine OpenSource Software gibt, die Interessierte optimieren könnten... afaik).

[nico]

CSP (Constraint Satisfaction Problem, siehe http://de.wikipedia.org/wiki/Constraint ... on-Problem) formulieren. Allerdings muss man dann ziemlich viel Grips in die Parallelisierung stecken, vermute ich.

Ist CSP nicht ==3SAT und damit NP-Vollständig und damit eigenltich egal wie implementiert immer schlecht zu lösen? (nicht schlagen, hatte nur TI1 und hab des nicht so gemocht... )

[LinuxFan]

Ist CSP nicht ==3SAT und damit NP-Vollständig und damit eigenltich egal wie implementiert immer schlecht zu lösen? (nicht schlagen, hatte nur TI1 und hab des nicht so gemocht... )

CSP hat halt den Vorteil, dass du mit heuristischen Suchverfahren relativ leicht eine Lösung finden kannst. Aber mir fällt gerade ein, dass die ja ALLE Lösungen finden wollen.

[EdmundBlackadder]

Natürlich sollte NQueens sofort den Durchlauf mit n=26 beenden.

Lieber Edmund, das ist völliger Quatsch. Nach Lektüre des Heise Forums komme ich zu der Meinung, NQueens soll n=26 noch fertig berechnen, damit man die Ergebnisse vergleichen kann. Wenn diese gleich sind, kann die BOINC-Methode guten Gewissens zu den Akten gelegt werden.