Problème du cavalier d'Euler

dgregory

Bonjour,
Je cherche à démontrer qu'on peut déplacer un cavalier sur un échiquier de $n \times n$ pour n = 401 en passant par toutes les cases une seule fois. J'ai commencé par regarder de plus petits cas. Pour n = 2, 3 ou 4, il n'y pas de solution. Pour n = 5, il y a au moins une solution. Je sais que c'est un cas particulier du problème de recherche d'un chemin hamiltonien dans un graphe biparti. Apparemment, ça peut se résoudre par récurrence en utilisant des bandes de largeur 4 cases. J'ai trouvé des solutions pour des longueurs de 5 ou 6 cases, mais je ne vois pas comment généraliser ça. Pourriez-vous m'aider s'il vous plaît ?

dgregory

J'ai trouvé la réponse à ma question dans cet article de Conrad et al (1994) en anglais : Solution of the knight's Hamiltonian path problem on chessboards.