# ===================================
# Recherche d'un carré magique 3x3 par force brute
# sans utiliser le module itertools
# Dans cette version du programme on crée directement une liste sans doublons
# nsi.gecif.net
# décembre 2024
# ===================================


# ---------------------------------------------------------------------
# c est une liste de 9 éléments (chiffres entre 1 et 9)
# chaque élément de la liste représente une case du carré magique :

#   c[0]      c[1]      c[2]
#   c[3]      c[4]      c[5]
#   c[6]      c[7]      c[8]

# Le carré magique est correctement rempli si
# c[0]+c[1]+c[2]==c[3]+c[4]+c[5]==c[6]+c[7]+c[8]==\
# c[0]+c[3]+c[6]==c[1]+c[4]+c[7]==c[2]+c[5]+c[8]==\
# c[0]+c[4]+c[8]==c[2]+c[4]+c[6]

# ---------------------------------------------------------------------
print("Recherche par force brute d'un carré magique 3x3 en cours ...\n")

# n permet de compter le nombre de carrés magiques testés
n=0
# t permet de compter le nombre de carrés magiques trouvés
t=0
# c est une liste de 9 nombres sans doublons (valeurs unique de 1 à 9)
c=[]
# c0 à c8 sont les 9 valeurs (chacune de 1 à 9)
valeurs_c0=list(range (1,10))
for c0 in valeurs_c0:
    # affiche l'avancée :
    print('c0 = %d / 9' % c0)
    print('Nombre de carrés magiques déjà testés : %d\n' % n)
    valeurs_c1=list(range (1,10))
    valeurs_c1.remove(c0) # il est inutile que c1 prenne la valeur de c0 puisqu'on ne veut pas de doublons
    for c1 in valeurs_c1:
        valeurs_c2=list(range (1,10))
        valeurs_c2.remove(c0) # c2 différent de c0 et de c1
        valeurs_c2.remove(c1)
        for c2 in valeurs_c2:
            valeurs_c3=list(range (1,10))
            valeurs_c3.remove(c0)
            valeurs_c3.remove(c1)
            valeurs_c3.remove(c2)
            for c3 in valeurs_c3:
                valeurs_c4=list(range (1,10))
                valeurs_c4.remove(c0)
                valeurs_c4.remove(c1)
                valeurs_c4.remove(c2)
                valeurs_c4.remove(c3)
                for c4 in valeurs_c4:
                    valeurs_c5=list(range (1,10))
                    valeurs_c5.remove(c0)
                    valeurs_c5.remove(c1)
                    valeurs_c5.remove(c2)
                    valeurs_c5.remove(c3)
                    valeurs_c5.remove(c4)
                    for c5 in valeurs_c5:
                        valeurs_c6=list(range (1,10))
                        valeurs_c6.remove(c0)
                        valeurs_c6.remove(c1)
                        valeurs_c6.remove(c2)
                        valeurs_c6.remove(c3)
                        valeurs_c6.remove(c4)
                        valeurs_c6.remove(c5)
                        for c6 in valeurs_c6:
                            valeurs_c7=list(range (1,10))
                            valeurs_c7.remove(c0)
                            valeurs_c7.remove(c1)
                            valeurs_c7.remove(c2)
                            valeurs_c7.remove(c3)
                            valeurs_c7.remove(c4)
                            valeurs_c7.remove(c5)
                            valeurs_c7.remove(c6)
                            for c7 in valeurs_c7:
                                valeurs_c8=list(range (1,10))
                                valeurs_c8.remove(c0)
                                valeurs_c8.remove(c1)
                                valeurs_c8.remove(c2)
                                valeurs_c8.remove(c3)
                                valeurs_c8.remove(c4)
                                valeurs_c8.remove(c5)
                                valeurs_c8.remove(c6)
                                valeurs_c8.remove(c7)
                                c8=valeurs_c8[0]
                                # c est directement une liste sans doublons
                                c=[c0,c1,c2,c3,c4,c5,c6,c7,c8]
                                n+=1
                                if c[0]+c[1]+c[2]==c[3]+c[4]+c[5]==c[6]+c[7]+c[8]==\
                                    c[0]+c[3]+c[6]==c[1]+c[4]+c[7]==c[2]+c[5]+c[8]==\
                                    c[0]+c[4]+c[8]==c[2]+c[4]+c[6]:
                                        print("Carré magique trouvé : %s\n" % c)
                                        t+=1

print('Sur %d carrés magiques testés le programme en a trouvés %d corrects.' % (n,t))

"""
Sur les 362880 permutations possibles il existe 8 carrés magiques 3x3 :
Carré magique trouvé : (2, 7, 6, 9, 5, 1, 4, 3, 8)
Carré magique trouvé : (2, 9, 4, 7, 5, 3, 6, 1, 8)
Carré magique trouvé : (4, 3, 8, 9, 5, 1, 2, 7, 6)
Carré magique trouvé : (4, 9, 2, 3, 5, 7, 8, 1, 6)
Carré magique trouvé : (6, 1, 8, 7, 5, 3, 2, 9, 4)
Carré magique trouvé : (6, 7, 2, 1, 5, 9, 8, 3, 4)
Carré magique trouvé : (8, 1, 6, 3, 5, 7, 4, 9, 2)
Carré magique trouvé : (8, 3, 4, 1, 5, 9, 6, 7, 2)
"""