Énigme de la semaine 29

Labyrinthe.

(Extrait du forum des énigmes mathématiques du site « l’île des mathématiques »)

Le départ se fait sur la case 1. On passe d’une case à une autre par un côté adjacent (donc pas en diagonale). On peut passer autant de fois qu’on veut sur chaque case.
Mais lorsqu’on a sauté de la case x à la case y, toutes les cases dont le numéro est un diviseur de la quantité |x²-y²| (valeur absolue de la différence des carrés) sont interdites pour le saut suivant (elles redeviennent éventuellement accessibles ensuite).

 
 
 
 
 
 
Par exemple, si on a sauté de 7 à 11, les cases 2, 3, 4, 6, 8, 9 et 12 sont alors interdites pour le saut suivant car |7²-11²| = 72.
En pratique, à partir de la case 11, on ne peut aller qu’en 10 ou en 15, ou bien retourner en 7.
Pour le départ, il n’y a pas de condition. À partir de 1, on peut aller librement en 2 ou en 5.
 
 
Quel est le chemin nécessitant un nombre minimal de sauts qui permet de passer au moins une fois sur chaque case ?
Donner la suite des cases visitées dans l’ordre en commençant par 1.
S’il existe plusieurs solutions, une seule suffira.

Solution

Voici un cheminement en 16 sauts :
1-5-9-13-14-15-16-12-11-10-6-7-6-2-3-4-8

Un cheminement « idéal » en 15 sauts permettrait de visiter toutes les cases sans passer deux fois sur une même case.
Mais un tel chemin n’existe pas, du fait principalement des contraintes d’accès aux cases 2, 3 et 4.

Il faut donc au moins 16 sauts, et dans ce cas, la solution proposée est bien minimale.