8-Damen-Problem

- WebmasterWork »
- Grafik & Programmierung »
- Sonstige Programmiersprachen »
- 8-Damen-Problem »

Hilti

unregistriert

Sonntag, 21. Februar 2010, 15:46

Guten Tag

wie der Titel schon sagt, geht es in diesem Thread um das 8-Damen-Problem. Wer nicht weiß, was das ist, hier eine kleine Erklärung des Grundprinzips:

Zitat

Es sollen jeweils acht Damen auf einem Schachbrett so aufgestellt werden, dass keine zwei Damen einander nach den Schachregeln schlagen können. Die Figurenfarbe wird dabei ignoriert, und es wird angenommen, dass jede Figur jede andere angreifen könnte. Oder anders ausgedrückt: Es sollen sich keine zwei Damen die gleiche Reihe, Linie oder Diagonale teilen. Im Mittelpunkt steht die Frage nach der Anzahl der möglichen Lösungen. [Wikipedia]

Ich soll dieses Problem in Form eines Programmes lösen, wobei lösen die falsche Wortwahl ist. Gelöst ist es schon, bei einem 8x8 Spielbrett gibt es 96 Lösungen, wobei es, wenn man alle Spiegelungen abzieht, nur noch 24 Lösungen sind. Ich soll das Problem also vielmehr in Form eines Programmes aufarbeiten und wiedergeben. Leider bin ich absolut kein Programmierer, sondern eher der Hardwaremensch, von daher wollte ich um eure Hilfe bitten. Programmiert werden soll das ganze vorzugsweise in Delphi.
Ich möchte ja nicht unbedingt schon ein fertiges Programm geschickt bekommen (ablehnen würde ich es aufkeinenfall

), bin bereit wirklich mitzuarbeiten, aber alleine bekomme ich es einfach nicht hin. Falls nun jemand Einwende hat, dass es ja für die Schule sei, den kann ich etwas beruhigen, ich bin in der 13 und es ist das aller letzte was ich machen muss. Informatik ist auch "nur" ein Nebenfach und bei mir fangen ab Freitag die Vorabiklausuren an, wodurch ich meine Prioritäten schon ein wenig anders setzen möchte, nur damit ihr versteht, warum ich um Hilfe bitte.

Also lange Rede, kurzer Sinn. Hier nochmal die Kurzform:

* 8-Damen-Problem
* suche Hilfe bei Programmierung
* Programmiersprache: Delphi (kann aber vielleicht auch von C++ konvertieren, oder Pascal ist dem auch sehr nahe)

Ich bedanke mich jetzt schonmal für jede Antwort.

Mit freundlichem Gruß
Hilti

ivanhoe

Eroberer

Dabei seit: 09.06.2009

Beiträge: 69

Sonntag, 21. Februar 2010, 20:00

Ich denke zuerst müsstest du das Schachbrett in einem Mehrdimensionalen Array abbilden, deren Werte aussagen ob sich eine Dame an der Position befindet oder nicht.
Wenn du die Damen dann an ihre Startpositionen gestellt hast, veränderst du deren Positionen in einer Schleife und zählst bei jeder iteration eine Varaible hoch, wenn sich auf einer Reihe, Linie und Diagonal nur eine Dame befindet.
Dann hättest du die Anzahl der Möglichkeiten, wenn das reicht.

dienstdrk

Routinier

Dabei seit: 02.01.2010

Beiträge: 356

Sonntag, 21. Februar 2010, 20:05

dann brauchst du am Besten noch ne Funktion, die dir liefert, ob die gerade aufgestellte
Dame geschlagen werden kann. Denn die "Anderen" stehen ja schon richtig.
Du musst also immer nur Bezug auf die letzte aufgestellte nehmen. Kommt die
aufgestellte Dame im letzten Feld an und kann dort nicht platziert werden, muss wieder mit
der Startfigur begonnen werden...

Hilti

unregistriert

Sonntag, 21. Februar 2010, 20:35

ok, also theoretisch habe ich das Problem auch verstanden, weiß auch dass ich es rekursiv mittels Backtracking lösen muss, ist ja auch das was ihr gesagt habt.
Nur praktisch bekomme ich das nicht umgesetzt, also programmiert.

jperl

Super Moderator

Dabei seit: 09.04.2003

Beiträge: 3 453

Montag, 22. Februar 2010, 01:36

Zitat von »Hilti«

ok, also theoretisch habe ich das Problem auch verstanden, weiß auch dass ich es rekursiv mittels Backtracking lösen muss, ist ja auch das was ihr gesagt habt.
Nur praktisch bekomme ich das nicht umgesetzt, also programmiert.

naja im internet findet sich eine ganze reihe von bereits umgesetzten algorithmen und hilfen.
http://www.ijon.de/comp/programme/damen/damen_de.html

im grund funktioniert das ganze so:
du versuchst eine dame auf einem feld zu platzieren, dann eine zweite dazu und schaust ob sich ein problem ergibt. passt sie kannst du eine weitere hinzufügen. passt sie nicht kannst du den gesamten teilbaum verwerfen, da es egal wäre wie die anderen damen stehen würfen.
somit versuchst du alle möglichkeiten die damen auf dem feld zu platzieren (brute force) allerdings kannst du teilbäume bereits früh verwerfen.

du brauchst also eine methode mit der du prüfen kannst ob auf dem aktuellen feld eine dame geschlagen werden kann.

da in jeder spalte natürlich immer nur eine dame stehen kann, solltest du versuchen die damen einfach spaltenweise anzuordnen. kann die dame geschlagen werden, setzt du sie in der spalte ein feld weiter nach unten (for schleife von 1 bis

, kann die dame nicht geschlagen werden, gehst du eine rekursion nach innen. bist du in der innersten rekursion (parameter der rekursiven methode mit jeder stufe inkrementieren) und es kann keine dame geschlagen werden, hast du eine lösung.
somit erhälst du dann alle validen lösungen.

jperl

Konfuzius [chinesischer Philosoph (551 - 479 v. Chr.)]
Das Entscheidende am Wissen ist, daß man es beherzigt und anwendet.

Ego

Routinier