coups_possibles = {
    "ligne 1"     : [1, 1, 1, 0, 0, 0, 0, 0, 0],
    "ligne 2"     : [0, 0, 0, 1, 1, 1, 0, 0, 0],
    "ligne 3"     : [0, 0, 0, 0, 0, 0, 1, 1, 1],
    "colonne 1"   : [1, 0, 0, 1, 0, 0, 1, 0, 0],
    "colonne 2"   : [0, 1, 0, 0, 1, 0, 0, 1, 0],
    "colonne 3"   : [0, 0, 1, 0, 0, 1, 0, 0, 1],
    "diagonale 1" : [1, 0, 0, 0, 1, 0, 0, 0, 1],
    "diagonale 2" : [0, 0, 1, 0, 1, 0, 1, 0, 0]
}

def representant(lst):
    decimal = 0
    for b in lst:
        decimal = 2*decimal + b
    return decimal
# ou
# def representant(lst):
#     n = len(lst)
#     decimal = 0
#     for i in range(n):
#         decimal += lst[i] * (2 ** (n - i - 1))
#     return decimal

assert representant([0, 0, 1, 0, 0, 1, 1, 1, 0]) == 78

def binaire(decimal):
    """
    Cette fonction prend en entrée un nombre décimal et renvoie sa représentation binaire sous forme de liste de 0 et de 1 de taille 9.
    """
    if decimal == 0:
        return [0] * 9
    lst = []
    while decimal > 0:
        lst.append(decimal % 2)
        decimal //= 2
    lst = lst + [0] * (9 - len(lst))
    lst.reverse()
    return lst

assert binaire(78) == [0, 0, 1, 0, 0, 1, 1, 1, 0]

def xor(b1, b2):
    if b1 == b2:
        return 0
    else:
        return 1
    
def xor_etendu(l_x, l_y):
    if len(l_x) != len(l_y):
        raise ValueError("Les deux listes doivent avoir la même taille.")
    res = []
    for i in range(len(l_x)):
        res.append(xor(l_x[i], l_y[i]))
    return res

def configurations_suivantes(config):
    config_bin = binaire(config)
    voisins = []
    for coup in coups_possibles.values():
        voisin = xor_etendu(config_bin, coup)
        voisins.append(representant(voisin))
    return voisins

def generation_graphe():
    graphe = {}
    for config in range(512):
        voisins = configurations_suivantes(config)
        graphe[config] = voisins
    return graphe

graphe = generation_graphe()
assert graphe[67] == [387, 123, 68, 359, 209, 10, 338, 23]

def parcours_profondeur(graphe, configuration, vus):
    vus.append(configuration)
    for s in graphe[configuration]:
        if s not in vus:
            parcours_profondeur(graphe, s, vus)

vus = []
parcours_profondeur(graphe, representant([1, 1, 1, 1, 1, 1, 1, 1, 1]), vus)
assert 4 not in vus
# ou
# vus = []
# parcours_profondeur(graphe, 4, vus)
# assert representant([1, 1, 1, 1, 1, 1, 1, 1, 1]) not in vus