N-Damen Problem Vereinfachung

Computer: Software & Programmierung C/C++
#1

Hallo liebe Wissende, und zwar programmiere ich grade das N-Damen Problem. D.h. auf einem Schachbrett mit der Größe N (normalerweise 8) N Damen so zu positionieren, dass sie sich gegenseitig nicht schlagen.

Wir haben den Tipp bekommen ein Schachbrett mit einem zweidimensionalen Array zu erstellen und überall dort, wo eine Dame steht eine 1 reinzuschreiben.
Nun habe ich mir aber gedacht, dass es ja wohl besser ist, wenn man ein eindimensionales Array nimmt und nur die Koordinaten abspeichert, da man da sich Speicher erspart.
Zudem könnte man ja schnell überprüfen, ob sie sich schlagen, wenn man mit HIlfe der Koordinaten ein Steigungsdreieck zu allen anderen Damen berechnet. Wäre doch bestimmt sehr viel schneller, als alle Felder durchzuforsten.

Nur leider hängts bei mir beim unsetzen. Eine Lösung für ein zweidimensionales Array hab ich schon, sieht wie folgt aus:

 for(col;(col

Weiß jemand, Rat?
Vielen Dank

<sub>MOD: pre-Tags hinzugefügt</sub>
#2

Hallo,

Wir haben den Tipp bekommen ein Schachbrett mit einem
zweidimensionalen Array zu erstellen und überall dort, wo eine
Dame steht eine 1 reinzuschreiben.
Nun habe ich mir aber gedacht, dass es ja wohl besser ist,
wenn man ein eindimensionales Array nimmt und nur die
Koordinaten abspeichert, da man da sich Speicher erspart.

Richtig.

Zudem könnte man ja schnell überprüfen, ob sie sich schlagen,
wenn man mit HIlfe der Koordinaten ein Steigungsdreieck zu
allen anderen Damen berechnet. Wäre doch bestimmt sehr viel
schneller, als alle Felder durchzuforsten.

Noch schneller ist es, zusätzlich ein zweidimensionales Array mit Integern zu nehmen, und darin für jede Position zu speichern, von wie vielen Damen sie im Moment bedroht ist.
Beim setzen einer Dame kann man dann sehr viel schneller testen, ob man diese Möglichkeit überhaupt ausprobieren muss.
Beim setzen und entfernen einer Dame läuft man dann alle Felder ab, die diese Dame bedroht und erhöht bzw. erniedrigt den Wert dieser Felder um eins.

Nur leider hängts bei mir beim unsetzen.

Ich habe hier Beispielcode: http://moritz.faui2k3.org/de/backtracking (ein wenig herunterscrollen muss man schon).

Grüße,
Moritz

#3

Ist es auch möglich bei deinem Algorithmus jedes Ergebnis einzeln ausgeben zu lassen,also dass nicht alles einfach so durchläuft

#4

Hallo,

Ist es auch möglich bei deinem Algorithmus jedes Ergebnis
einzeln ausgeben zu lassen,also dass nicht alles einfach so
durchläuft

natürlich, und schwer ist das auch nicht. Hast du es mal probiert?

Grüße,
Moritz

#5

Hi, also ich hab jetzt mal probiert deinen Code etwas anzupassen, indem ich eine Struct verwende. Aber irgendwie schein ich mich damit nun aufgehängt zu haben. Kannst du dir das mal anschauen, wo ich’s versaut hab?
Startwerte:

control.iSize = 8;
control.cKeyboard = ‚0‘;

Und die eigentliche Funktion ruf ich so auf:

control.iSolutions = 0;
control.iRow = 0;
control.iBoard[0] = 0;
calc(&control,‚0‘);

#include „header.h“

void calc(struct queen *control,char cKeyboard)
{
int i = 0;
if ((*control).iRow == (*control).iSize)
{
(*control).iSolutions++;
return;
}

for (i = 0; i Und das die Überprüfung

int isbeating (struct queen *control)
{
int i = 0;
int temp = 0;

for(i = 0; i

#6

Ok, habs nun hinbekommen. Waren nur ein paar kleine Fehler drin.
Hab aber noch 2 kleine Fragen!

1.Ich dachte ich hätte gewusst, wie man bei deinem Beispiel nach der ersten Lösung abbricht, bzw. das Ergebnis ausgibt, doch leider schaff ich da doch irgendwie nicht. Kannst du mir da helfen?

  1. (Nicht so wichtig) Du hast geschrieben, dass man für gerade N sich ja die Hälfte der Zeit sparen kann, wegen Spiegelung. Bei ungeraden N ginge das auch, wenn man bis zur Spaltevor der Hälfte berechnet. Leider schaffe ich das bei deinem Quelltext nicht, das Ergebnis ist immer falsch.

Danke für deine Mühe

#7

Ok, habs nun hinbekommen. Waren nur ein paar kleine Fehler
drin.
Hab aber noch 2 kleine Fragen!

1.Ich dachte ich hätte gewusst, wie man bei deinem Beispiel
nach der ersten Lösung abbricht, bzw. das Ergebnis ausgibt,
doch leider schaff ich da doch irgendwie nicht. Kannst du mir
da helfen?

Dazu musst den Rückgabewert der Funktion search benutzen (bzw. erst mal einen definieren), und z.B. bei Erfolg (also hinter Count++) eine 1 zurückliefern, bei Mißerfolg eine 0, und dann beim rekursiven Aufruf abbrechen, sobald der erste Erfolg aufgetreten ist (und den erfolgreichen Rückgabewert nach unten durchgeben).

  1. (Nicht so wichtig) Du hast geschrieben, dass man für gerade
    N sich ja die Hälfte der Zeit sparen kann, wegen Spiegelung.
    Bei ungeraden N ginge das auch, wenn man bis zur Spaltevor der
    Hälfte berechnet. Leider schaffe ich das bei deinem Quelltext
    nicht, das Ergebnis ist immer falsch.

Ich habs jetzt nicht getested, aber so müsste dann die Funktion main aussehen:

int main(int argc, char\*\* argv){
 /\* Initialisiere Array \*/
 field\_type field[N];
 field\_type i = 0;
 for (i = 0; i 

Das benutzt die Tatasache, dass bei Integerarithmetik abgerundet wird.

Grüße,
Moritz