La première stratégie que j’ai utilisé est un parcours en
profondeur, en marquant les cases visitées, et de retourner
en arrière si le chemin emprunté conduit à une impasse.
On parle alors d’algorithme de type "retour sur trace" ou
"retour arrière" (backtracking en anglais).
L’avantage de cette approche est qu’on est sûr de trouver
une solution s’il en existe une. Cependant, cet algorithme
a aussi un très gros point faible. Comme il consiste à
tester toutes les possibilités, il est donc extrêmement lent.
Ma seconde stratégie à été d’utiliser l’algorithme de Warnsdorf. Le cavalier est déplacé de façon à toujours se rendre sur la case à partir de laquelle il aura le moins de déplacements ultérieurs.
Lorsqu’on met les résultats des deux algorithmes côte à côte, la différence de temps d’exécution est significative. Sur cet échiquier de 5×5, l’algorithme de backtracking (à gauche) met 0.059 secondes, alors que celui de Warnsdorf (à droite) ne met que 0.001 secondes.
Sur un échiquier de taille 8×8, la différence de temps d’exécution est encore plus frappante. 33 secondes d’un côté, 0.003 de l’autre. La différence est d’un facteur 10 000.
