Javascript, Springerproblem via Backtracking

[Forjo90]

Hallo,

ich muss für eine Arbeit ein Programm(Javascript) schreiben, welches das Springerproblem(Route, sodass jedes Feld genau einmal betreten wurde) via Backtracking löst.
Ich hab das Programm jetzt soweit, dass der "Springer" soweit springt, dass kein weiterer Zug möglich ist und dann soweit zurück geht, bis er den ersten Alternativweg nehmen kann. Jetzt muss sich das Programm ja jeden Alternativweg merken, sodass er diese nicht immer wieder durchläuft.
Hätte da einer eine Idee wie ich das umsetzen könnte?

Danke

 

[e_Lap]

Bitte einmal etwas verstaendlicher formulieren. Leg auch deinen Ansatz zum Algorithmus mal dar. Ich kann dir hier nicht folgen

 

[Hancock]

Hinweis: Rekursion, mit Divide and Conquer. Mehr sag ich nicht. (Hausaufgabenregel!)

 

[mambokurt]

Hallo,

ich muss für eine Arbeit ein Programm(Javascript) schreiben, welches das Springerproblem(Route, sodass jedes Feld genau einmal betreten wurde) via Backtracking löst.
Ich hab das Programm jetzt soweit, dass der "Springer" soweit springt, dass kein weiterer Zug möglich ist und dann soweit zurück geht, bis er den ersten Alternativweg nehmen kann. Jetzt muss sich das Programm ja jeden Alternativweg merken, sodass er diese nicht immer wieder durchläuft.
Hätte da einer eine Idee wie ich das umsetzen könnte?

Danke

Beim klassischen Backtracking benutzt man eigentlich Rekursion, damit hättest du das Problem nicht dir irgendwelche Pfade merken zu müssen (die besuchten Felder müsstest du aber bei jedem rekursiven Aufruf mitgeben). Das geht dann allerdings zu Lasten des Arbeitsspeichers. Wenn du es iterativ machst wird das Programm umfangreicher und du müsstest die besuchten Pfade mit speichern, wäre sicherlich dann klassisch als Baum umsetzbar.

IMHO fährst du mit Rekursion erstmal den idiotensicheren Weg, wenn das zu heftig wird was Ram angeht kannst du immer noch auf iterativ machen. Zu Beginn würde ich übrigens eher erstmal mit einem 4x4 Felder großem Schachbrett starten und erst wenn das klappt die Feldzahl erhöhen.