Lorsqu'une solution de carré magique est trouvée, le chemin inverse ayant pour origine la case finale du chemin trouvé donne aussi un carré magique. En essayant les 10 départs indépendants de la zone départ, chaque solution est trouvée deux fois.

Il est possible de réduire le temps de recherche total (tous les carrés magiques à partir de toutes les origines possibles de la zone de départ). Lors d'une recherche, il arrive fréquement que la case d'arrivée soit connue par avance. En effet, lorsqu'on arrive sur une case qui posède deux voisins a et b et dont chacun de ces deux voisins n'a qu'un seul autre voisin (hormis la case courante), il est nécessaire pour poursuivre le chemin, d'aller soit vers a et dans ce cas b est la fin du parcours, ou soit vers b et dans ce cas a est la fin du parcours. Si la fin est déjà fixée, on ne peut aller ni vers a, ni vers b et il faut donc reculer.

Quand tous les chemins sont trouvés à partir d'un départ donnée, on peut dans les autres recherches ayant pour origine un autre départ, s'interdire comme case d'arrivée toutes les cases qui ont déjà été utilisées comme départ. Ainsi, l'arbre de recherche est plus petit.

Le tableau 10x10 suivant indique en ligne et en colonne les 10 cases de départ permettant d'obtenir toutes les solutions. Pour chaque départ, le nombre de solutions par cases d'arrivée ramenées dans la zone de départ est indiquée. Une solution peut être trouvée soit par le chemin direct, soit en utilisant le chemin inverse.

Le principe de recherche optimisé est le suivant : on cherche toute les solutions à partir du premier départ D1. On cherche ensuite toutes les solutions à partir du départ D2 en laissant de cotés dans ces recherches les solutions qui fournissent D1 comme arrivée. Puis on recherche les solutions à partir du troisième départ D3 en laissant les arrivées donnant D1 et D2 ... et comme cela jusqu'au dixième départ.

Il n'est pas évident de trouver l'ordre dans lequel les différentes recherches doivent être effectuées pour minimiser le temps total. Sur la figure suivante, l'ordre des départs est indiqué. Cet ordre n'est pas forcément le meilleur, c'est à dire celui qui produit un temps de recherche minimum. Il y a en théorie 10! combinaisons possibles. Dans notre choix, la première recherche est effectuée à partir de la case 0, c'est à dire un coin de l'échiquier. Ainsi, dans les recherches suivantes, toutes les solutions aboutissant à une case en coin ne seront pas recherchées. La deuxième recherche est effectuée à partir de la case 18 (C3 sur un échiquier). La suite est constituée des cases 27 puis 9 puis 19 puis 10 puis 11 puis 2, 3 et finalement 1.

La figure suivante se lit ainsi. Chaque ligne représente une case de départ. La somme des nombres sur chaque ligne indique le nombre de carrés magiques obtenus à partir de ce départ. Il y en a 280. Les cases d'arrivées possibles sont présentées en colonne. Lorsqu'un nombre est présent dans une case, il indique le nombre de solutions pour un départ donné, indiqué par le numéro de ligne et pour une arrivée donnée -ramenée dans la zone de départ - indiqué par le numéro de colonne. Un nombre sur fond vert indique une solution trouvée dans le chemin direct et un nombre sur fond violet indique une solution qui a été précédement trouvée sur un autre chemin direct ayant le départ courant comme arrivée.

Tous les chemins ayant leur arrivée sur la même case que le départ (après rotation et symétrie bien sûr) sont directement obtenus.

Les recherches sont réalisées sur une machine pentium 4, 2,4 Ghz. Les temps sont exprimés en secondes. La ligne #Solutions indique, pour chaque départ le nombre de solutions trouvées en utilisant cet algorithme optimisé suivi du nombre de solutions obtenues avec l'algotithme initial. Les temps de recherches, obtenus par l'algorithme initial (prévisibles sur un pentium 4 2,4 Ghz) sont indiqués à titre de comparaison. On voit que plus l'ordre de recherche est grand, plus le gain est important.

La première recherche est effectuée à partir de la case 0, c'est à dire un angle de l'échiquier. Elle dure près de 10 jours. On pourrait envisager de terminer la recherche par ce départ. Cependant, en commençant par cette case, toutes les recherches suivantes à partir des 9 autres départs durent beaucoup moins longtemps car on s'interdit alors les chemins pouvant aboutir dans un coin de l'échiquier. Ces recherches sont très nombreuses car elles se produisent dès que le cavalier arrive à un saut d'un coin, sans poursuivre par ce coin.

Cependant, il est probable que cet ordre de recherche puisse être optimisé afin d'optenir, en final, un temps global inférieur à 26 jours. De plus des améliorations au niveau du codage de l'algorithme sont surement possibles.

L'algorithme exécuté sur une pentium 4 - 2,4 Ghz trouve 158 solutions en 26,4 jours. Il y en a plus que les 140 solutions attendues car les chemins ayant le départ à l'arrivée sur la même case (aux rotations et symétries près) sont toujours comptés deux fois. Il y a 36 solutions dans ce cas. Ces 36 solutions ne constituent que 18 solutions indépendantes.

Le nombre corrigé est donc de 158 - 18. On retrouve bien les 140 solutions indépendantes.