# définition d'une constante, la taille de l'échiquier
n=4

# partant d'une liste de longueur k,
# renvoie True si on peut compléter celle-ci
# par une reine en position new dans la colonne k+1

def ajoutValide(liste,new):
    sortie=True
    for i in range(0,len(liste)):
        if liste[i]==new or liste[i]==new-len(liste)+i or liste[i]==new+len(liste)-i:
            sortie=False
    return sortie

# partant d'une liste,
# on passe en revue toutes les solutions possibles

compteur=0
def nouvelleReine(liste):
    global compteur
    # print(liste) # on verra l'évolution
    # si on a une liste de longueur n, c'est une solution
    if len(liste)==n:
        print(liste)
        compteur+=1
    else:
        # sinon, on essaie d'étendre de toutes les façons possibles
        for j in range(1,n+1):
            if ajoutValide(liste,j):
                nouvelleReine(liste+[j]) # récursif

# on définit un parcours dans l'arbre
# [X,i] -> [X,i+1] si i<n
# [X,n] -> le successeur de [X]
# par exemple, [2,n,n] -> [3]
def suivant(liste):
    if liste==[]:
        return [1]
    elif liste[-1]<n:
        return liste[:-1]+[liste[-1]+1]
    else:
        return suivant(liste[:-1])

def premiereSolution():
# on explore l'arbre jusqu'à trouver une solution
    config=[1]
    while len(config)<n or not ajoutValide(config[:-1],config[-1]):
        # si on a une configuration valide, on descend d'un niveau
        if ajoutValide(config[:-1],config[-1]):
            config=config+[1]
        else:
            config=suivant(config)
    return(config)

print(premiereSolution())

nouvelleReine([])
print(compteur)
