Hallo,
... es geht um das Springerproblem (Ein Springer soll auf einem Schachfeld jedes Feld genau einmal besucht haben), wobei bei meinem Lösungsversuch Fehler aufgetreten sind und ich nicht genau weiß wie man die behebt:
Also zu Beginn bin ich mal Schritt für Schritt durchgegangen (z.B. bei Feldgröße 6 mal 6). Am Anfang gab es keine Probleme. Doch als ich zurück gelaufen bin (-->backtracking), da der Springer in einer Sackgasse landete, habe ich das Feld markiert und hab auf der einen anderen Weg (nicht den markierten Weg auf der nächsthöheren Ebene) gewählt und hab von da an das Backtracking gemacht. Nur leider endet der Algorithmus von mir in einer Endlosschleife ("stack Überlauf"). Ich glaube ich setze die Markierung nicht richtig, sodass er immer den gleichen falschen Weg geht. Blöderweise bin ich nicht in der Lage das Problem zu beheben.
Könnt ihr mir vielleicht helfen?
Ich wäre euch sehr sehr dankbar.
(Ich hoffe ihr kommt mit dem umständlichen Quelltext zu Rande...)

Guten morgen,

Du machst da was völlig falsch, uups schlecht geschlafen ....

Was deinen Pogram fehlt ist die Speicherung von Zaehler1 zu jedem Feldpunkt.
Du benutzt Zaehler1 global, bei jeden Schritt zurück wird nicht ein neuer Weg versucht sondern wieder bei 1 begonnen..
Feld: array of array of boolean sollte statt boolean einfach die Zaehler1 beherbergen.
Wenn das Feld 0 ist war dort noch kein Springer, sonst steht dank Zaehler1 in welche der 8 Richtungen er gesprungen ist.
Dein Array of char ist eigentlich doppelt gemoppelt, da diese Information schon in Feld ist.

Um einigermassen vernünftig damit klar zu kommen, mußt Du Dir auch den Weg selber merken.
Du brauchst also eine Liste (array) der Grösse der Anzahl der Spielfelder=sqr(Anzahl2) in der die Koordinaten des x-ten Zuges gespeichert sind.
Der erste Zug kann ja immer 1/1 sein, der Starpunkt sein.
Jetzt zum vorgehen.


Ich hoffe das ist unverständlih genug

Gruß Horst

Moin Jake,
das Springerproblem läßt sich iterativ nach a) der Warnsdorff-Regel lösen oder b) rekursiv.

a)Im Jahr 1823 schlug H. C. Warnsdorff eine heuristische Regel vor,
die das Finden einer Lösung stark vereinfacht. Nach der Wansdorffregel
zieht der Springer immer auf das Feld, von dem aus er für seinen nächsten
Zug am wenigsten freie (d.h. noch nicht besuchte) Felder zur Verfügung hat.
Diese Regel ist unmittelbar einleuchtend, sie verhindert beispielsweise,
dass eines der beiden Felder, die der Springer von einer Ecke aus erreichen
kann, frühzeitig besucht wird, so dass der Springer später nicht mehr aus der
Ecke entkommen kann.
Die Warnsdorffsregel gibt keine Anweisung, was zu tun ist, wenn es mehrere
Felder gibt, von denen es gleich wenige im nächsten Zug erreichbare Felder gibt.

b)Auf dem Brett wird vom Startfeld in allen 8 Richtungen ein mögliches Zielfeld berechnet,
ist das Zielfeld leer, wird die Zugnummer reingespeichert und die Suche geht mit dem nächsten Wert weiter.
Gibt es kein leeres Zielfeld wird der Zug rückgängig gemacht.

procedure TSpringerRek.Springe(Zug,XAlt,YAlt:Integer);
var K,XNeu,Yneu:Integer;
begin
if Abbruch then exit; // Aussprung aus der Rekursion
inc(Versuch);
for K:=1 to 8 do
begin
XNeu:=XAlt+WA[K];Yneu:=YAlt+SE[K];
if Brett[XNeu,Yneu]=0 then
begin
Brett[XNeu,Yneu]:=Zug; // Zug ausführen
if Zug=NSqr then Ausgeben
else Springe(Zug+1,XNeu,Yneu);
Brett[XNeu,Yneu]:=0; // Zug rückgängig machen
end
end;
end;

Die dritte Variante gilt für Bretter der Länge 4K+1: immer an der Wand lang (s.Anhang)

Gruß, Fiete