| Au lancement du programme, chaque case connaît
le nombre de cases "nborigine",
à partir desquelles elle est susceptible d'être atteinte. C'est
également le nombre de destinations que possède une case.
A chaque itération (avance d'un saut du cavalier), la case atteinte
devient occupée et ne peut plus servir d'origine pour les autres cases.
La valeur "nborigine" de toutes les cases (entre 2 et
8) qui référençaient cette case atteinte, est décrémentée de 1.
Lorsqu'une case possède "nborigine = 0" elle est
inatteignable. Le cavalier doit donc reculer même s'il lui est encore
possible d'avancer.
Typiquement, cet algorithme détecte les trous du parcours c'est à
dire les cases vides entourées de cases occupées. Le gain en nombre de coups de recherche et en temps est très
important.
Une autre amélioration, qui n'est pas prise en compte ici consiste
à favoriser les cases excentrées.
|
|
L'échiquier suivant présente une
solution de chemin à partir de la case F2.
Le temps de recherche est de 1 minute 8 secondes
en utilisant la détection précoce du blocage(1).
Sans détection, le chemin trouvé est identique mais en 1
heure 1 minute et 24 secondes. Dans ces conditions avance =
718 237 849 et recule = 320 348 900
(1) Pentium II / 233Mhz.
|
