✔ 8-Damen-Problem

D

Dorschty

Erfahrenes Mitglied
Hey,

ich hab ne Aufgabe bekommen das 8-Damen-Problem in C zu programmieren! Leider hab ich absolut keine Ahnung wo ich auch nur Anfangen kann! Ich hab jetzt schon stundenlang gegoogelt und da reden die ständig irgendwas von "backtracking" usw. Kann jemand mal in einfachen Worten erklären was backtracking bedeutet und mir evtl. einen Denkanstoß für das Problem geben? Wär echt ne feine Sache, komm leider kein Stück weiter! :confused:
Gruß
Dorschty
 
Oh, das is schon ne Weile her, seitdem wir das beim Studium gemacht haben...

Du brauchst einen Stack (Liste, Tabelle, Whatever)

Nimm eine Dame und platziere sie in der n-ten Reihe auf die m-te Spalte und gucke, ob es Kollisionen gibt, wenn ja: wiederhole das für n mit m+1, wenn nein, wiederhole das für n+1 mit m=1; Speichere die Position jeder erfolgreich plazierten Dame, lösche die Position wieder wenn die Position verändert werden muss!

Es geht letztendlich darum, daß Du Schritt für Schritt alle möglichen Kombinationen durchgehst und bei jedem Schritt prüfst, ob die Bedingungen erfüllt sind. Je nach Aufgabenstellung kannst Du dann ja alle Lösungen oder alle Lösungen ohne Drehung und Spiegelungen des Feldes aufzeigen.

HTH
 
Hallo,

am besten für ein solches Problem ist der Entscheidungsbaum. Hab gerade leider keinen Beispielquelltext da.

Ds ganze kann man dann rekursiv lösen. Dann brauchst du dich auch nur im die Lösung von einem Stein zu kümmern und er Rest passiert von alleine. :)
Der Ansatz von Navy ist schon der richtige.

MFG

zEriX
 
Ich bin leider in C noch ein ziehmlicher Anfänger, von daher überleg ich grad... muss ich dann wenn ich eine Dame plaziert habe und dann abfrage, ob es kollisionen gibt jede Zelle, in der es Kollisionen geben könnte einzeln abfragen, oder gibt es da einen eleganteren Weg?
Also wenn ich jetzt zB.

1 | X |__|__|__|__|__|__|
2 |__|__|__|__|__|__|__|
3 |__|__|__|__|__|__|__|
4 |__|__|__|__|__|__|__|
5 |__|__|__|__|__|__|__|
6 |__|__|__|__|__|__|__|
7 |__|__|__|__|__|__|__|
8 |__|__|__|__|__|__|__|
a b c d e f g

Die Dame oben gesetzt habe, muss ich dann die Zellen: b1,c1,d1,e1,f1,g1,a1,a2,a3,a4,a5,a6,a7,a8,b2,c3,d4,e5,f6 und g7 einzeln abfragen?
 
Ja, musst du. Wenn du das ganze in einem 2d-Array hast ist es einfacher weil du die Indizes nur hochzählen, bzw runterzählen musst.

So brauchst du dich auch nicht mehr drum zu kümmern was rechts von dir ist. Wenn du von klein nach groß (Index) arbeitest, brauchst du dann nur noch zu schauen, welche Steine sind im kleineren Indexbereich im Weg.
Ich hoffe ich hab mich verständlich ausgedrückt.

MFG

zEriX
 
Du musst nicht jede Zelle abfragen, Du musst nur gucken, ob die Zeile, Spalte oder Diagonale schon referenziert ist.

Am schnellsten (aber umständlichsten) geht es über einen Zeilen und Reihenindex in dem Du beim Setzen einder Dame in ein Feld eben diese Reihe und Zeile markierst.

Minimier den Aufwand, mach das ganze erstmal auf dem Papier und überlege, wie Du effizient an die Sache rangehen kannst (vor dem Setzen prüfen u.Ä.)
 
@Navy
Seine Frage war ja ob er in der Zeile, Spalte und Diagonale jede Zelle abfragen muss.

Ich müsste das ganze noch als Ada-Source-Code haben, den könnte ich ja später mal posten.

Das ganze ist mit dem Entscheidungsbaum gelöst. Finde diese Variante nicht schlecht.


MFG

zEriX
 
> Seine Frage war ja ob er in der Zeile, Spalte und Diagonale jede Zelle abfragen muss.

Ja, das war die Frage, und meine Antwort dementsprechend. Er *muss* es nicht, man kann es über Indizierung der jeweiligen Reihen und Spalten und Diagonalen machen, das ergibt 32 Indizes, von denen aber immer nur 4 abgefragt werden müssen.

Bei der Datengröße ist Effizienz eigentlich zu vernachlässigen, Neulinge müssen ja aber nicht gleich anfangen rumzuaasen.
 
Ok, ich hatte deine Antwort anders verstanden. :)

Aber ehrlich gesagt, verstehe ich im moment nicht so ganz was du meinst. Also mit dem ersten Teil schon, aber warum müssen immer nur 4 abgefragt werden?

MFG

zEriX
 
Zuletzt bearbeitet:
hi,
die Spalte kannst du dir sogar sparen, wenn du in jede Spalte
einfach nur eine Dame setzt. Als ich das Damenproblem gelöst
hab hab ich eine rekursive Funktion benutzt, kann ich nur empfehlen ;)

Benny
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück