# ===================================
# Recherche d'un carré magique 3x3 par force brute
# sans utiliser le module itertools
# 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)
for c0 in range (1,10):
    # affiche l'avancée :
    print('c0 = %d / 9' % c0)
    print('Nombre de carrés magiques déjà testés : %d\n' % n)
    for c1 in range (1,10):
        for c2 in range (1,10):
            for c3 in range (1,10):
                for c4 in range (1,10):
                    for c5 in range (1,10):
                        for c6 in range (1,10):
                            for c7 in range (1,10):
                                for c8 in range (1,10):
                                    c=[c0,c1,c2,c3,c4,c5,c6,c7,c8]
                                    # on ne veut pas de doublons dans la liste c :
                                    if len(set(c))!=9:
                                        break
                                    # teste les 9 permutations circulaires de la liste c :
                                    for i in range(9):
                                        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
                                        # réalise une permutation circulaire (le dernier élément devient le premier) :
                                        c=[c[-1]]+c[:-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)
"""