Énigme et retour sur trace

Une énigme

Tout démarre par une énigme. Pour celle-ci, il faut placer les entiers de 1 à 25 dans une grille de cinq cases sur cinq. On place librement le 1, puis il faut respecter les règles suivantes : soit on se déplace de 3 cases orthogonalement (horizontal ou vertical), soit on se déplace de 2 cases diagonalement.

Voici un exemple :

4
1
5
32
6

On démarre sur la deuxième case de la deuxième ligne. On se déplace diagonalement en bas à droite de deux cases, puis à gauche de trois cases et trois cases vers le haut. Enfin deux fois en diagonale en bas à droite.

La solution existe-t-elle ? Si oui est elle unique ?

Python, à l'aide!

Divulgâchage direct : Il existe plusieurs solutions. Mais combien au total?

L'idée est de tester tous les chemins possibles à partir de chacune des cases de la grille. Soit 25 points de départ et 24 déplacements dans 8 directions possibles donc 25×8²⁴ ≈ 1,18×10²³ chemins à tester. Cent-dix-huit-mille-milliards de milliards de possibilités.

On peut cependant réduire le nombre de possibilités en remarquant que :

Le nombre de chemins possibles devient 25×3²³×4 = 9 414 317 882 700. Il reste encore neuf milles milliards de possibilités.

On va donc essayer tous les chemins en passant ceux dont le début n'est pas valide. Par exemple, si on démarre par la case centrale, on ne garde que les chemins qui démarrent par un déplacement diagonal.

On va programmer du «Retour sur trace» («backtracking» en anglais) Le programme teste les déplacements toujours dans le même ordre si le chemin est correct, il continue de le construire. Sinon il essaie le déplacement suivant. S'il n'y a plus de déplacement possible, il revient à la case précédente et essaie un autre déplacement.

#!/usr/bin/python3
"""Recherche du nombre de solutions pour une enigme"""

# Les déplacements
#
#       2
#   3   .   1
#     . . .
# 4 . . x . . 0
#     . . .
#   5   .   7
#       6

def nv_lieu(lieu, dplt):
    """Retourne le lieu après déplacement"""
    x, y = lieu
    match dplt:
        case 0:
            x += 3
        case 1:
            x += 2
            y -= 2
        case 2:
            y -= 3
        case 3:
            x -= 2
            y -= 2
        case 4:
            x -= 3
        case 5:
            x -= 2
            y += 2
        case 6:
            y += 3
        case 7:
            x += 2
            y += 2

    return (x, y)


def ac_lieu(lieu, dplt):
    """Retourne le lieu avant déplacement"""
    x, y = lieu
    match dplt:
        case 0:
            x -= 3
        case 1:
            x -= 2
            y += 2
        case 2:
            y += 3
        case 3:
            x += 2
            y += 2
        case 4:
            x += 3
        case 5:
            x += 2
            y -= 2
        case 6:
            y -= 3
        case 7:
            x -= 2
            y -= 2

    return (x, y)


def test_lieu_dplt(lieu, dplt, grille):
    """Vérifie la validité du chemin
    à partir du lieu (x,y),
    du déplacement 0..7
    et des cases disponibles de la grille
    """
    x, y = nv_lieu(lieu, dplt)

    # En dehors de la grille
    if not (0 <= x <= 4 and 0 <= y <= 4):
        return False
    # Case pas disponible
    if (x, y) not in grille:
        return False
    # C'est valide
    return True


def chercher_solutions(lieu):
    """Cherche les solution pour un lieu de départ
    et les retourne sous forme de liste"""
    nbr = 0
    solutions = []
    grille = {(x, y) for x in range(5) for y in range(5)}
    grille.remove(lieu)
    chemin = []
    etape = 0
    dplt = 0

    def cul_de_sac(grille, lieu, chemin, dplt, etape):
        grille.add(lieu)
        lieu = ac_lieu(lieu, chemin[-1])
        dplt = chemin[-1] + 1
        chemin = chemin[:-1]
        etape -= 1

        return grille, lieu, chemin, dplt, etape

    while True:
        nbr += 1
        if etape == 24:
            solutions.append(chemin)
            grille, lieu, chemin, dplt, etape = cul_de_sac(
                grille, lieu, chemin, dplt, etape
            )
        if etape == len(chemin):
            if test_lieu_dplt(lieu, dplt, grille):
                chemin.append(dplt)
                etape += 1
                lieu = nv_lieu(lieu, dplt)
                grille.remove(lieu)
                dplt = 0
            elif dplt < 7:
                dplt += 1
            elif chemin != []:
                grille, lieu, chemin, dplt, etape = cul_de_sac(
                    grille, lieu, chemin, dplt, etape
                )
            else:
                return solutions,nbr

NBR_TOTAL = 0
NBR_SOLUTIONS_TOTAL = 0

for X in range(5):
    for Y in range(5):
        NBR_SOLUTIONS, NBR = chercher_solutions((X, Y))
        NBR_SOLUTIONS = len(NBR_SOLUTIONS)
        NBR_SOLUTIONS_TOTAL += NBR_SOLUTIONS
        NBR_TOTAL += NBR
        print(X, Y, NBR_SOLUTIONS, NBR)

print(NBR_SOLUTIONS_TOTAL, NBR_TOTAL)

Conclusion

Le programme n'effectue que 19 411 318 itérations pour trouver les 12 400 chemins possibles en 12 secondes. Si on avait testé tous les chemins possibles (1,18×10²³), le programme aurait dû tourner durant 2 312 714 116 années. Avec 9 414 317 882 700 chemins à tester, c'est 67 jours.

On peut aussi observer que le nombre de solutions dépend de la case initiale avec une répartition symétrique. Le nombre d'itérations varie aussi mais sans symétrie, sûrement car l'ordre des déplacements reste le même sans subir de symétrie.

Merci à Jessica pour l'énigme.