Hi,
ich denk mal das n damen problem (oder 8Queens) wird vielen hier ein begriff sein.
Für die, die es nicht kennen: Es geht darum, wie viele möglichkeiten es gibt n damen auf einem n mal n schachbrett so zu plazieren, dass keine eine andere schlägt.
Also angenommen n ist gleich 4, dann hat man also ein schachbrett mit 4x4, also mit 16 feldern und muss darauf nun 4 damen so aufstellen, dass sie sich nicht gegenseitig schlagen.
Ich habe mir folgende prozedur ausgedacht (rekursiv):
kurze erläuterung der verwendeten prozeduren:
function darf_test(x,y: integer): boolean; - prüft, ob an die position x,y eine dame gestellt werden darf
procedure entf_dame(x,y: integer); - entfernt die dame an der stelle x,y
function suche_dame(y: integer): integer; - gibt den entsprechenden x wert einer dame zu dem gelieferten y wert zurück
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
| procedure TForm1.start(x,y,l: integer);
var n: integer;
begin
n:=0;
if darf_test(x,y) then
begin
brett[x,y]:=true;
if y < max then start(1,y+1,l)
else
begin
inc(l);
le_lsg.Text:=inttostr(strtoint(le_lsg.Text)+1);
n:=suche_dame(y);
entf_dame(n,y);
start(n+1,y,l);
end;
end
else
begin
if x < max then start(x+1,y,l)
else
begin
n:=suche_dame(y-1);
entf_dame(n,y-1);
if n < max then start(n+1,y-1,l)
else
begin
if y > 2 then
begin
n:=suche_dame(y-2);
entf_dame(n,y-2);
start(n+1,y-2,l);
end;
end;
end;
end;
end; |
Ich habe mir überlegt das ganze durch ein array[1..n,1..n] zu realisieren, deswegen bekommt meine prozedur einen x- und einen y-wert, welche die koordinaten in dem array darstellen. Der letze wert l ist die anzahl der gefundenen lösungen. Er wird immer an einer ganz bestimmten stelle erhöht und am ende (bei einem klick auf einen button) ausgegeben). Jedoch gibts da ein problem: an der stelle wo das letzte kommentar im code eingefügt ist sollte eigentlich schluss sein (ich bin den code schritt für schritt mit f7 durchgegangen), jedoch läuft er irgendwie auf dem letzten end noch ne weile weiter, ruft dabei die prozedur mit irgendwelchen werten auf und verringert das l gleichzeitig wieder von 2 auf 0. Hab keine ahnung, warum das so ist, würds aber gern mal wissen.
Die prozedur funktioniert übrigends trotzdem, und da ich den wert der lösungen immer an der stelle erhöhe, wo ich auch die anzahl der lösungen erhöhe gibt er mir auch die richtigen lösungen an. Allerdings klappt das ganze nur bis n=8. Also mit einem 9x9 schachbrett kommt er z.B. nicht klar, da gibt er mir dann die fehlermeldung stack overflow.
also, wär echt nett, wenn mir jemand sagen könnte, warum er weiterläuft und die lösung wieder auf null bringt, wo eigentlich schluss sein sollte.
und kann man irgendwas gegen den stack überlauf tun? oder muss ich da am ende dann noch ne iterative variante schreiben?
wenn irgendwas noch unklar sein sollte fragt ruhig nach
Moderiert von 
Gausi: Code- durch Delphi-Tags ersetzt
