"""Recherche du nombre de solutions pour une énigme"""

import datetime

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

a = datetime.datetime.now()

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 de la grille cases disponibles
    """
    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_it(lieu):
    """Cherche les solution pour un lieu de départ
    et les retourne sous forme de liste"""
    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:
        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


def iterative():
    nbr_total = 0
    nbr_solutions_total = 0

    for x in range(5):
        for y in range(5):
            solutions = chercher_solutions_it((x, y))


def chercher_solutions_re(lieu, grille, chemin):

    global solutions

    nv_grille = grille[:]
    nv_grille.remove(lieu)

    if len(nv_grille) == 0:
        solutions[chemin[0]].append(chemin)
    else:
        for dplt in range(8):
            if test_lieu_dplt(lieu, dplt, nv_grille):
                chercher_solutions_re(
                    nv_lieu(lieu, dplt),
                    nv_grille,
                    chemin +(dplt, )
                )


def recursive():

    global solutions

    solutions = {(x, y):[] for x in range(5) for y in range(5)}

    grille = [(x, y) for x in range(5) for y in range(5)]

    for x in range(5):
        for y in range(5):
            lieu = (x, y)
            chercher_solutions_re(lieu, grille, (lieu, ))


b = datetime.datetime.now()

iterative()

c = datetime.datetime.now()

recursive()

d = datetime.datetime.now()

print(b-a)
print(c-b)
print(d-c)