Récréation

Problème du Cavalier :

Le cavalier du jeu d'échec peut-il parcourir toutes les cases de l'échiquier en ne passant qu'une seule fois sur chaque case ?
De nombreux mathématiciens ont étudié ce probléme sans trouver de réponse générale.
Le programme de cette page montre qu'il existe des solutions.
Une recherche exhaustive n'étant pas envisageable, on utilise ici un algorithme proposé en 1883 par le mathématicien Warnsdorff.

On déplace toujours le cavalier vers la case qui offre le moins de possibilités de mouvements ultérieurs vers les cases libres.

Si le cheval est dans la case A, on cherche les cases B1, B2, Bi non visitées qu'il peut atteindre.
Pour chaque case Bi, on cherche le nombre Ni de cases permises. On fera le choix de la case Bi pour laquelle Ni est le plus petit.
Si pour plusieurs cases Bi la valeur de Ni est la même, on fera un choix aléatoire entre ces cases.
Cet algorithme donne souvent à une solution mais le fait qu'il conduise à un blocage ne signifie pas qu'il n'existe pas de solution pour la case de départ utilisée

Il existe une variante dans laquelle on cherche à faire un dernier saut vers la case initiale. Ce problème porte le nom de "Tour du cavalier".

Utilisation
Avec les listes, choisir la taille de l'échiquier et la vitesse de l'animation.
Cliquer sur la case choisie comme point de départ pour lancer le cheminement du cavalier sur l'échiquier.
Le programme affiche le mouvement du cavalier et indique sur l'échiquier l'ordre des mouvements.
Le choix entre les cases ayant la même valeur de Ni étant aléatoire, le parcours est en général différent à chaque fois.