L'énoncé

Le problème du cavalier sur un jeu d'échec est très célèbre. L'énoncé est extrêmement simple. Quelle que soit la position initiale d'un cavalier sur un échiquier (8x8), celui-ci peut parcourir toutes les cases en suivant le déplacement d'un cavalier (un saut droit puis un saut en diagonale) et en empruntant une et une seule fois chacune des cases. Il s'agit alors de trouver l'ordre des 63 "sauts" du cavalier qui permettent, à partir d'une case donnée de trouver ce chemin.

Démonstration par l'exemple

Pour vérifier cet énoncé, il suffit d'écrire un programme qui, à partir d'une case donnée, essaye toutes les possibilités de chemin. L'algorithme du programme est très simple. Chaque case au début du parcours possède entre 2 et 8 cases "destination" sur lesquelles il est possible d'aller. Une case au centre de l'échiquier, c'est à dire à plus de 2 lignes et de 2 colonnes du bord en possède 8.  Chacun des 4 coins n'en possède que deux. Sur les lignes ou les colonnes proches du bord de l'échiquier, les cases possèdent  3, 4 ou 6 destinations. Au fur et à mesure du parcours, les cases sont marquées occupées. Lorsqu'il n'est plus possible d'avancer, le cavalier recule et essaye une autre case. Si toutes les cases destination sont prises, il recule encore ...avant d'avancer à nouveau vers une autre direction.