Verständnisprobleme in Bezug auf Backtracking
-
Hallo, ich habe aus der Schule eine Aufgabe bekommen, in der in das Backtrackingverfahren anwenden soll.
Wir haben auch eine ungefähre Beschreibung des Algorithmus und eine Vorlage erhalten. Leider ist es bei mir so, dass ich damit überhaupt nicht zurecht komme.
Was ich bei der Aufgabe nicht verstehe, wie es mit der Vorlage möglich sein soll, bei sagen wir mal 4 auf 4 Feld auf die 2 lösungen zu kommen.
Ich habe hier noch ein 4 auf 4 Feld gezeichnet und eine Situation dargestellt, die ich icht verstehe.
http://www.siteupload.de/p611022-Feldjpg.html
Im ersten Zug wird die Dame links oben gesetzt.
Die zweite Dame wird durch die rekursive Funktion um eine Reihe nach unten befördert und findet erst nachdem sie 2mal bedroht wurde eine Stelle.
Aber was passiert jetzt mit der dritten Dame ???
Jedes Feld ist für sie gefährlich , also kann sie nicht gesetzt werden und jetzt tritt das backtracking ein, also das entfernen, der zweiten Dame, richtig ??
Aber wie kann ich das realisieren ?Hier ist die Vorlage,
http://www.siteupload.de/p610998-NDamenjpg.html
Wenn etwas schlecht lesbar ist, einfach runterladen, ich habe sie extra in einer hohen Auflösung angefertigt.
Wäre sehr dankbar, wenn ihr mir etwas unter die arme greifen könntet.
Gruss theflasher
-
theflasher schrieb:
http://www.siteupload.de/p611022-Feldjpg.html
Im ersten Zug wird die Dame links oben gesetzt.
Die zweite Dame wird durch die rekursive Funktion um eine Reihe nach unten befördert und findet erst nachdem sie 2mal bedroht wurde eine Stelle.
Aber was passiert jetzt mit der dritten Dame ???Sie findet kein nicht bedrohtes Feld. Es wird also keine Lösung ausgegeben oder gespeichert, die Funktion kehrt zurück. Die zweite Dame wird jetzt auf das nächste Feld gesetzt, und es wird wieder was für die dritte Dame gesucht.
Hier ist die Vorlage,
Die sieht auf den ersten Blick eigentlich so aus, als ob man sie eins zu eins implementieren kann. Hast du das mal probiert?
-
Jedes Feld ist für sie gefährlich , also kann sie nicht gesetzt werden und jetzt tritt das backtracking ein, also das entfernen, der zweiten Dame, richtig ??
Aber wie kann ich das realisieren ?Das Entfernen der Dame passiert direkt nach dem Backtracking-Aufruf (Reset Queen From Row and Col), d.h. du setzt einfach das entsprechende Feld wieder auf 0 (leer).
Und anschließend wird ja die Variable Col ("Spalte") um eins erhöht, d.h. im nächsten Schleifendurchgang wird die Dame in die nächste Spalte gesetzt, und dort dann überprüft etc.Am besten du zeigst uns mal deinen Code.
(Und wenn der funktioniert, dann kannst du ja dort Zug für Zug durchsteppen und versuchen es zu verstehen -)
-
Hi, also danke erst mal für die Tips.
Ich habe hier erst mal den Code von der Callnqueen
#include "nqueen.h" char callnqueen(NQUEEN *str_nqueen,int row) { char character; int column; int attacked; if(row < 0 || row >= str_nqueen->currentsize) // has row the right size?? { gotoxy(12,12); printf("Board is corrupted"); character = 's'; } else // row has the right size { column = 0; while(column < str_nqueen->currentsize && character != 'e' && character != 's') { str_nqueen->board[row][column] = 1; // queen has been set str_nqueen->lastqueen.ilastrow = row; // add row to ilastrow in struct str_nqueen->lastqueen.ilastcol = column; // add column to ilastcol in struct attacked = is_attacking(str_nqueen); if( attacked == 1) // queen attacked if 1 not attacked if 0 { while(kbhit()!= 0) { character = getch(); } str_nqueen->board[row][column] = 0; column++; } else // queen not attacked { if(row == str_nqueen->currentsize -1) // request if the queen is in the last row. information! the first queen will be set on position 0 not on position 1. { str_nqueen->isolution++; if(str_nqueen->esave == on) // is the save mod on or off { //savesol(); } if(str_nqueen->emode == automatic) // is the automatic or the step mode on? { while(kbhit()!= 0) // for the case, if someone has input anything during the process { character = getch(); // takes a character from the keyboardbuffer } } else // step mode { printboard(str_nqueen); character = getch(); } printstatus(str_nqueen); // prints the statusbar } else { character = callnqueen(str_nqueen,row +1); // set the next queen with a recursion } } // End of queen not attacked } // End of While } // End of row has right size return character; } // End of char callnqueenIch hatte das nach der Vorlage gemacht, aber bin jetzt nicht ganz sicher, ob das überhaupt stimmt. Weil so wie Th das sagt, müsste ja das Reset Queen from Row and Col nach der Rekursion möglich sein, was bei mir glaube ich nicht der Fall ist.
Aber im Grunde soll die Dame doch nur dann zurückgesetzt werden, wenn es am Ende keine Möglichkeit gibt, auf die Lösung zu kommen oder eine weitere Dame zu setzen.
Gruss theflasher
-
So wie es im Diagramm eingetragen ist, mußt du
str_nqueen->board[row][column] = 0; column++;immer am Ende der while-Schleife aufrufen.
Ansonsten würde ja nie zur nächsten Spalte gewechselt werden.Du mußt einfach den Sinn des Backtrackings (Rekursion) verstehen.
Je Row (Zeile) ruft das Programm die Funktion auf und je Zeile werden alle Columns (Spalten) abgearbeitet, um eine Lösung zu finden.
Und wenn das Programm aus der Funktion wieder zurückkehrt, muß ja die aktuelle Position der Dame verändert werden, d.h. die Dame wird gelöscht und dann auf die nächsten Spalte (falls Spalte < MaxSpalten) gesetzt.
-
Hallo danke für die Antwort, ich bin tatsächlich weitergekommen und fast vor dem Ziel.
Es gibt da aber noch einen Punkt, den ich nicht ganz verstehe.
Wenn ich mich an die Vorlage halte, dann wird ja zuerst die Dame gesetzt und dann wird überprüft, ob sie bedroht wird.
Wenn ich jetzt aber in der is_attacking eine Zeile überprüfe und die Dame bereits gesetzt war, dann habe ich schon beim ersten Aufruf eine Bedrohung.
Ich konnte das zwar umgehen, aber ob das optimal ist weiß cih nicht.Wo ich ziemliche Schwierigkeiten habe sind die Diagonalen.
Ich bekomme einfach keine Abfrage hin, die innerhalb der Brettgrenze liegt.
Denn jedesmal, wenn ich um ein Feld nach rechts gehe, muss ich ja ein Feld weniger überprüfen, weil es ja diagonal ist. Ganz rechts muss ich dann nichts überprüfen, aber ich bekomme keinen vernünftigen Ansatz dafür hin.Das habe ich bis jetzt
#include "nqueen.h" int is_attacking(NQUEEN *str_nqueen) { int attacked; int i; int j; int k; int l; int m; int diff; for(i=0; i < str_nqueen->lastqueen.ilastcol && i < str_nqueen->currentsize; i++) // horizonatle Abfrage, da wo die Dame steht,wird i übersprungen { if(str_nqueen->board[str_nqueen->lastqueen.ilastrow][i] == 1) { attacked = 1; if(attacked==1) { return 1; } } } for(j=0; j < str_nqueen->lastqueen.ilastrow && j < str_nqueen->currentsize; j++) // vertikale Abfrage { if(str_nqueen->board[j][str_nqueen->lastqueen.ilastcol] == 1) { attacked = 1; if(attacked==1) { return 1; } } } diff = str_nqueen->lastqueen.ilastcol - str_nqueen->lastqueen.ilastrow; // Differenz zwischen Zeile und Spalte, ist die Differenz 0, dann ist die Dame auf der Diagonalen von links oben nach rechts unten // ist die Differenz positiv dann ist die Dame rechts von der Diagonalen, negativ dann links von der Diagonalen if(diff >= 0) // wo ist die Dame links oder rechts von der Diagonalen von 0 aus ? { for(l=0; l < str_nqueen->lastqueen.ilastrow && l < str_nqueen->currentsize-diff; l++) { if(str_nqueen->board[l][l+diff] == 1) { attacked = 1; if(attacked==1) { return 1; } } } } else { } for(k=0; k < str_nqueen->lastqueen.ilastrow && k < str_nqueen->currentsize+diff; k++) { if(str_nqueen->board[k-diff][k] == 1) { attacked = 1; if(attacked==1) { return 1; } } } }Wäre sehr froh, wenn ihr mir nocheinmal helfen könntet
Gruss theflasher
-
Also zuerst einmal reicht ein einfaches "return 1" anstatt die Variable "attacked" zu setzen, abzufragen und dann sowieso "return 1" auszuführen.
Und zweitens ist deine if-else Klammerung falsch:
if(diff >= 0) // wo ist die Dame links oder rechts von der Diagonalen von 0 aus ? { for(...) ... } else { for(...) ... }Ansonsten mußt du einfach mit dem Debugger durchgehen und schauen, ob du noch evtl. einen Indexfehler hast.