Cavaliers et graphes

Immédiatement, je prends conscience des difficultés pratiques: si chaque case de l’échiquier est un nœud dans un graphe, alors la matrice d’adjacence est d’ordre…64. L’exercice qui sera proposé aux élève se devra donc d’être simplifié, par exemple sur un échiquier de 4 ou 5 cases de côté.

Cependant, rien ne m’empêche en attendant de s’amuser un peu et de tâter le terrain avec le véritable échiquier et je me fixe le double objectif suivant: déterminer le plus petit nombre de coups pour aller d’une case à une autre, puis fournir un chemin qui réalise ce plus petit nombre de coups.

Puisque l’idée de saisir la matrice dans une calculatrice est incongrue, j’opte pour un programme en Python.
J’exporte mon tableau en .csv et l’importe dans mon programme à l’aide de la fonction loadtxt de la bibliothèque numpy:

#importe numpy sous le nom de np
import numpy as np
#création de la matrice originale des déplacements
arr=[] 
#import du fichier CSV
arr = np.loadtxt("echikCSV.csv", delimiter=";", dtype=int)

Dans un premier temps, j’ai besoin d’une fonction qui renvoie le nombre de chemins de longueur $n$ allant d’une case à une autre, cases codées comme sur un plateau.
Il faut donc convertir le code d’une case en sa ligne ou sa colonne dans la matrice d’adjacence $M$.
Du fait de mon choix original de codage des sommets de mon graphe, je suis obligé d’opérer comme suit:

• L’opérateur saisit le code d’une case au format LC (pour Lettre-Chiffre).
• La lettre L est convertie en chiffre à travers son code ASCII par la fonction ord à qui je retire 64 (65 est le code de la lettre A).
• Je soustrais 1 au chiffre C puis je multiplie par 8, pour me rendre au début de la série de lettres correspondantes, puis j’ajoute le résultat précédent.

Par exemple:

• L’opérateur saisit G3,
• La fonction ord appliquée à G renvoie 71 à qui on enlève 64 ce qui donne 7,
• L’opération $(3-1)\times 8=16$ nous amène jusqu’à H2,
• L’ajout de 7 donne 23, c’est à dire le numéro de ligne ou colonne correspondant à G3.

Enfin, la fonction np.linalg.matrix_power élève une matrice donnée à une puissance donnée et nous avons:

#Donne le nombre de chemin de longueur allant du départ à l'arrivée codés en plateau d'échecs
def convert(depart: str, arrive: str, longueur: int):
    x_dep = ord(depart[0])-64
    y_dep = int(depart[1])
    ligne = x_dep+8*(y_dep-1)
    x_arr = ord(arrive[0])-64
    y_arr = int(arrive[1])
    colonne = x_arr+8*(y_arr-1)
    mat = np.linalg.matrix_power(arr, longueur)
    result = int(mat[ligne-1, colonne-1])
    return result

Par exemple, il n’y a qu’un seul chemin en 2 coups qui va de A1 à E3

In [1]: convert('A1','E3',2)
Out[1]: 1

Mais il y a 198364 chemins en 10 coups qui rejoignent les deux coins opposés du plateau.

In [4]: convert('A1','H8',10)
Out[4]: 198364

Reste à minimiser le nombre de coups, ce qu’une boucle fait très bien:

#Donne le nombre minimal de coup à jouer pour aller de dela à adela codés en plateau d'échecs
def minimal(dela: str, adela: str):
    n = 1
    while convert(dela, adela, n) < 1:
        n += 1
    return n

Par exemple, 6 coups suffisent à joindre les coins opposés du plateau:

In [5]: minimal('A1','H8')
Out[5]: 6

Reste désormais à fournir un chemin en utilisant un algorithme d’optimisation. Nous pourrions coder un Dijkstra mais pourquoi ne pas utiliser le pouvoir de la bibliothèque Scipy et sa fonction shortest_path ?
Je le ferai ici dès que j’aurai un peu de temps mais n’hésitez pas à me proposer vos programmes dans les commentaires.

À toutes fins utiles, ci-dessous le fichier .csv de la matrice d’adjacence.