Backtracing oder Der Springer auf dem Schachfeld

[Nikolas]

N'abend allerseits. Ich hab in meiner Mathe-AG die Aufgabe bekommen folgendes Rätsel zu lösen:
Finde einen Weg den ein Springer auf einem 8*8 Schachfeld gehen kann, um alle Felder einmal zu besuchen und wieder auf das Startfeld zu kommen. (Geschlossener Hamillton-Graph).
Das war kein so großes Problem, da hab ich eine Lösung.
Aber natürlich ist 8*8 ein Spezialfall und ich würde das gerne auf x*y Erweitern. Bis jetzt hab ich mir überlegt das mit Backtracing (ich hoffe das heisst wirklich so) zu lösen. Also wenn ich in einer Sackgasse stehe, gehe ich einegn Schritt rückwärts und versuchs nochmal. Nun hab ich aber das Problem, dass es auf machen Brettern (z.B.: 2*3) keine Lösung gibt.

Jetzt kommt endlich meine Frage:
Hat jemand eine Idee, wie eine Abfrage machen kann, die mir ausgeben kann, ob es auf diesem Brett einen geschlossenen Graph gibt ??? :gruebel:

Oder hat jemand eine ganz andere Idee wie ich an das Problem herangehen soll? Ich habe ausser dem Backtracing noch keine andere Strategie auf Lager und will mich nicht darauf stürzen bevor ich nicht sicher bin, dass es nicht noch eine einfachere Nethode gibt.

Vielen Dank schon mal

THXbyTOX

[MrSpock]

Hallo Toxman,

wenn du das Problem durch Rekursion löst, was im Prinzip deinem Backtracking entspricht, weil, wenn es keine Lösung mit dem aktuellen Zug auf Stufe n gibt, wird ein andere Zug auf Stufe n-1 versucht, dann gibt es genau dann keine Lösung, wenn der letzte Zug auf Stufe 1 keine Lösung erzeugt.

[Nikolas]

Da hst du recht, sowas hab ich mir schon halber gedacht. Kennt noch jemand eine andere Strategie? Ich hab mir das Ganze nämlich so vorgestellt, dass man die Größe eingeben kann und dann das Ergebniss (& Zeit, Aufwand) verschiedener Strategien vergleichen kann.

[DP-Maintenance]

Dieses Thema wurde von "Christian Seehase" von "Object-Pascal / Delphi-Language" nach "Programmieren allgemein" verschoben.
Allgemeine Algorithmen gehören auch nach Programmieren allgemein ;-)

[neolithos]

Über die Seite ist, die folgende Anw. herausgekommen.

[dizzy]

:cyclops: Alter Falter! Die gehen mal richtig zur Sache da auf der Seite. Hulla! Und Respekt!

[MrSpock]

Wow, jetzt bin ich aber von den Socken. :shock: Und das als Vilkanier :mrgreen: . Das ist ja gigantisch! Ich habe das Problem schon mit meinem ATARI 1040 ST in etwa 3 Tagen mit Backtracking in Jahre 1986 gelöst. Aber die Seite, auf die du da verweist zieht mir die Schuhe aus. :thuimb:

[neolithos]

Ich war selbst erstaunt, wie schnell dieser Algo das eigentlich riesige Problem löst!

[Nikolas]

Ich hab den Tip mit der Idee von Warnsdorf schon gehabt und das 8*8 kann ich damit in ein paar msec lösen. Ich wollte eigentlich nur das Backtracking mit Warnsdorf kombinieren und dann auf größere Bretter loslassen. Jetzt kann ich schon mal Backtracking allein, mit Warnsdorf, oder Warnsdorf allein versuchen und dann noch versuchen, das mit den Königswegen zu versuchen, obwohl man dabei keinen schön geschlossenen Weg hinbekommt.
Aber danke für diese tolle Seite, das hilft mir echt weiter.

Tox