""" Script qui résout le problèmes des n reines """
import copy

NB_REINES = 8

Echiquier = list[list[bool]]

def echiquier_vide() -> Echiquier:
    """ Crée un échiquier vide """
    return [[False for i in range(NB_REINES)] for j in range(NB_REINES)]

def case_vide(echiquier: Echiquier, colonne: int, ligne: int) -> bool:
    """ Vérifie si une case est vide
        :param echiquier: L'échiquier
        :param colonne: La colonne de la case 1..NB_REINES
        :param ligne: La ligne de la case 1..NB_REINES
        :return: True si la case est vide, False sinon
    """
    return not echiquier[ligne - 1][colonne - 1]

def placer_reine(echiquier: Echiquier, colonne: int, ligne: int) -> None:
    """ Place une reine sur l'échiquier
        :param echiquier: L'échiquier
        :param colonne: La colonne de la case 1..NB_REINES
        :param ligne: La ligne de la case 1..NB_REINES
    """
    echiquier[ligne - 1][colonne - 1] = True

def retirer_reine(echiquier: Echiquier, colonne: int, ligne: int) -> None:
    """ Retire une reine de l'échiquier
            :param echiquier: L'échiquier
            :param colonne: La colonne de la case 1..NB_REINES
            :param ligne: La ligne de la case 1..NB_REINES
    """
    echiquier[ligne - 1][colonne - 1] = False

def aucunes_reines_ne_peuvent_se_prendre(echiquier: Echiquier) -> bool:
    """ Vérifie si aucunes reines ne peuvent se prendre
        :param echiquier: L'échiquier
        :return: True si aucunes reines ne peuvent se prendre, False sinon
    """

    def nombre_reine_sur_une_ligne(echiquier: Echiquier, ligne: int) -> int:
        return sum(1 for colonne in range(1, NB_REINES + 1) if not case_vide(echiquier, colonne, ligne))

    def nombre_reine_sur_une_colonne(echiquier: Echiquier, colonne: int) -> int:
        return sum(1 for ligne in range(1, NB_REINES + 1) if not case_vide(echiquier, colonne, ligne))

    def nombre_reine_sur_une_diagonale_descendante(echiquier: Echiquier, colonne: int, ligne: int) -> int:
        count = 0
        for i in range(1, NB_REINES + 1):
            if colonne - i >= 1 and ligne - i >= 1 and not case_vide(echiquier, colonne - i, ligne - i):
                count += 1
            if colonne + i <= NB_REINES and ligne - i >= 1 and not case_vide(echiquier, colonne + i, ligne - i):
                count += 1
        return count

    def nombre_reine_sur_une_diagonale_montante(echiquier: Echiquier, colonne: int, ligne: int) -> int:
        count = 0
        for i in range(1, NB_REINES + 1):
            if colonne - i >= 1 and ligne + i <= NB_REINES and not case_vide(echiquier, colonne - i, ligne + i):
                count += 1
            if colonne + i <= NB_REINES and ligne + i <= NB_REINES and not case_vide(echiquier, colonne + i, ligne + i):
                count += 1
        return count
    
    for colonne in range(1, NB_REINES + 1):
        for ligne in range(1, NB_REINES + 1):
            if not case_vide(echiquier, colonne, ligne):
                if nombre_reine_sur_une_ligne(echiquier, ligne) > 1:
                    return False
                if nombre_reine_sur_une_colonne(echiquier, colonne) > 1:
                    return False
                if nombre_reine_sur_une_diagonale_descendante(echiquier, colonne, ligne) > 0:
                    return False
                if nombre_reine_sur_une_diagonale_montante(echiquier, colonne, ligne) > 0:
                    return False
    return True

def indice_premiere_colonne_vide(echiquier: Echiquier) -> int:
    """ Trouve l'indice de la première colonne vide
        :param echiquier: L'échiquier
        :return: L'indice de la première colonne vide, ou -1 si aucune colonne n'est vide
    """
    for colonne in range(1, NB_REINES + 1):
        if all(case_vide(echiquier, colonne, ligne) for ligne in range(1, NB_REINES + 1)):
            return colonne
    return 0

def echiquier_en_str(echiquier: Echiquier) -> str:
    """ Convertit un échiquier en une chaîne de caractères
            :param echiquier: L'échiquier
            :return: La chaîne de caractères représentant l'échiquier
    """
    result = ""
    for ligne in range(1, NB_REINES + 1):
        for colonne in range(1, NB_REINES + 1):
            result += "Q " if not case_vide(echiquier, colonne, ligne) else ". "
        result += "\n"
    return result

def resoudre(echiquier: Echiquier, solutions: list[Echiquier]) -> None:
    """ Résout le problème des n reines
        :param echiquier: L'échiquier
        :param solutions: La liste des solutions trouvées
    """
    colonne = indice_premiere_colonne_vide(echiquier)
    if colonne == 0:
        if aucunes_reines_ne_peuvent_se_prendre(echiquier):
            print("Solution trouvée:")
            print(echiquier_en_str(echiquier))
            solutions.append(copy.deepcopy(echiquier))
    else:
        for ligne in range(1, NB_REINES + 1):
            placer_reine(echiquier, colonne, ligne)
            resoudre(echiquier, solutions)
            retirer_reine(echiquier, colonne, ligne)

def resoudre_optimise(echiquier: Echiquier, solutions: list[Echiquier]) -> None:
    """ Résout le problème des n reines
        :param echiquier: L'échiquier
        :param solutions: La liste des solutions trouvées
    """
    colonne = indice_premiere_colonne_vide(echiquier)
    if colonne == 0:
        print("Solution trouvée:")
        print(echiquier_en_str(echiquier))
        solutions.append(copy.deepcopy(echiquier))
    else:
        for ligne in range(1, NB_REINES + 1):
            placer_reine(echiquier, colonne, ligne)
            if aucunes_reines_ne_peuvent_se_prendre(echiquier):
                resoudre_optimise(echiquier, solutions)
            retirer_reine(echiquier, colonne, ligne)

def main():
    print("Résolution du problème des n reines")
    print("Version optimisée")
    solutions = []
    resoudre_optimise(echiquier_vide(), solutions)
    print(f"Nb solutions: {len(solutions)}")
    print("Version non optimisée")
    solutions = []
    resoudre(echiquier_vide(), solutions)

if __name__ == "__main__":
    main()