n-Damen-Problem mit rekursiver Funktion lösen

Hallo C++-Profis,

wie der Titel schon verrät, soll das n-Damen-Problem mit einem rekursiven Lösungsalgorithmus in Form einer sich selbst aufrufenden Funktion gelöst werden.

Natürlich findet man im WWW einiges dazu, jedoch kann ich nichts davon verwerten, da ich einerseits keine Klassen verwenden soll und andererseits keine für absolute Anfänger undgewöhnliche Pakete einbinden soll.

konkret heißt es:

Das Programm soll einen Backtracking-Algorithmus verwenden: Es wird jeweils eine Dame in die erste Zeile der nächsten freien Spalte gesetzt und überprüft, ob diese Dame eine andere schlagen kann. Wenn nicht, wird die nächste Dame in die nächste Spalte gesetzt und wieder geprüft. Sollte die zuletzt gesetzte Dame jedoch geschlagen werden können, dann wird sie eine Zeile tiefer gesetzt. Wenn sie schon in der untersten Zeile steht, dann wird sie entfernt und die Dame in der Spalte davor eine Zeile tiefer gesetzt. Wenn die n-te Dame gesetzt ist und diese keine andere schlagen kann, ist eine Lösung gefunden.
Diese Art der Lösungssuche kann rekursiv durch eine Funktion Versuch programmiert werden, die jeweils eine Dame setzt und sich dann selbst wieder aufruft. Schreiben Sie eine Funktion Versuch, die jeweils eine Dame in die nächste freie Spalte setzt und überprüft, ob sie sicher ist.

Das Einlesen der Dimension und Erzeugen des dynamisch allokierten Schachbretts habe ich schnell erledigen können, aber beim Algorithmus stecke ich schon die ganzen Ferien fest

Kann mir jemand aushelfen?

Natürlich machen wir deine Hausaufgaben, wenn du zuvor etwas guten Willen demonstrierst, deine bisherige Arbeit präsentierst und konkrete Fragen stellst.

Naja, was ich bis jetzt schon im Programm geschrieben habe ist eben nur das Drumherum:

- Einlesen der Dimension
- mit dynamischem Speicher das Schachbrett in dieser Dimension erstellen sowie es mit Nullen auffüllen

dann sollte der Algorithmus stattfinden, woraufhin ich im Programm dann:

- die (erste) Lösung grafisch ausgebe
- den Speicher freigebe

Wobei ich nun auch daran zweifle, ob ich damit auf dem richtigen Weg bin, da nicht nur eine, sondern alle Lösungen gefunden werden sollen. Und bei der echten Größe von 8x8 Feldern gibt es ja bereits 92 Lösungen, sodass es keinen Sinn macht, die alle (grafisch) anzugeben.

Bezüglich der Funktion habe ich mir natürlich auch schon Gedanken gemacht, landete jedoch immer wieder auf dem Holzweg.

Das Überprüfen, ob die Dame geschlagen werden kann, wollte ich erst durch eine Multiplikation der davor liegenden Feldinhalte (1 = Dame drin, 0 = leer) mit 1 realisieren, sodass die Dame nicht gesetzt werden darf, wenn etwas anderes als Null rauskommt. Da das zu aufwändig zum Umsetzen wurde, habe ich ein weiteres Feld angelegt, das einfach die Damen pro Zeile aufsummiert. Nun komme ich hier jedoch mit den Diagonalen und Nebendiagonalen nicht weiter.

Ich habe keine Ahnung, wie ich überhaupt "anfangen" soll... und mich damit nicht beschäftigt zu haben, kann ich mir auch nicht vorwerfen, schließlich hat mir das schon die ganzen Ferien verdorben.

unskilled

vll bringt dich ja ein link hier weiter:

http://de.wikipedia.org/wiki/Damenproblem#Rekursives_Backtracking

http://www.arstechnica.de/index.html?name=http://www.arstechnica.de/computer/JavaScript/JS11_04.html

http://fbim.fh-regensburg.de/~saj39122/vhb/NN-Script/script/gen/k02070106.html

Ich denke ja der Wikipedia-Artikel ist nicht all zu schlecht und sollte reichen, um halbwegs zu verstehen, was man selbst machen sollte!? Fang doch einfach mal an es zu versuchen und zeig dann, wie weit du gekommen bist - ich bin mir sicher, dass du 50% der Lösungen (wenn sie denn von allein kommen würden) nicht verstehen würdest weil 200mal irgendwelches algorithm-gedöns dabei wäre ^^
aber wenn du zeigst, wie in etwa du das machen willst, dann findet sich mit sicherheit jmd, der guckt, wo der fehler liegt (falls du ihn im debugger nicht findest) oder die nen denkanstoß gibt...

bb

die seiten kenn ich bereits alle, habe mittlerweile auch die englischen quellen durchschaut und werde einfach nicht schlau daraus...

ich programmiere erst seit kurzem und habe keine ahnung, wie ich die algorithmen (die inhaltlich ja an sich leicht verständlich sind) umsetzen soll.

cpp-newb schrieb:

ich programmiere erst seit kurzem und habe keine ahnung, wie ich die algorithmen (die inhaltlich ja an sich leicht verständlich sind) umsetzen soll.

Grundsätzlich würdest du damit beginnen den Algorithmus grob in Pseudocode oder zu Beginn vielleicht mit deinen eigenen Worten hinzuschreiben. Danach formulierst du die Schritte in c++ aus. Dabei lagerst du umfangreichere Formulierungen in Funktionen aus und formulierst diese auch wieder aus, bis zuletzt dein fertiges Programm erscheint. Ist doch ganz einfach, was?

Offenbar hast du dich bereits für eine Form entschieden das Spielfeld in c++ zu interpretieren. Wenn du das dem Forum mitteilst kann man basierend auf deinem Ansatz weiter Tipps zur Implementierung geben, mit denen du dann letztlich den Algorithmus vollständig umsetzen könntest.

Alternativ könnte jemand eine fertige, State of the Art - Lösung ins Forum stellen, aber das willst du ja sicher nicht.

Etwas mehr Kooperation, zeig dem Forum deinen Ansatz (Quelltext) und dir kann geholfen werden. Hier wurden schon schwierigere Fälle durchgebracht.

Hajo, Uni Karlsruhe lässt grüßen...

Hast das Problem inzwischen gelöst? Kann meine Hilfe anbieten. Bin leider krank und daher net an der Uni, aber übers Internet geht bestimmt au was...