# ===================================
# Recherche d'un carré magique 4x4 par force brute
# sans utiliser le module itertools
# nsi.gecif.net
# décembre 2024
# ===================================


# ---------------------------------------------------------------------
# c est une liste de 16 éléments (chiffres entre 1 et 15)
# 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]      c[9]      c[10]     c[11]
#   c[12]     c[13]     c[14]     c[15]

# Le carré magique est correctement rempli si

# les 4 lignes :
# c[0]+c[1]+c[2]+c[3]==c[5]+c[5]+c[6]+c[7]==c[8]+c[9]+c[10]+c[11]==c[12]+c[13]+c[14]+c[15]==\

# les 4 colonnes :
# c[0]+c[4]+c[8]+c[12]==c[1]+c[5]+c[9]+c[13]==c[2]+c[6]+c[10]+c[14]==c[3]+c[7]+c[11]+c[15]==\

# les 2 diagonales :
# c[0]+c[5]+c[10]+c[15]==c[3]+c[6]+c[9]+c[12]==\

# ---------------------------------------------------------------------

print("Recherche par force brute d'un carré magique 4x4 en cours ...")

# c est une liste de 16 nombres sans doublons (valeurs unique de 1 à 16)
c=[]
# c0 à c15 sont les 16 valeurs (chacune de 1 à 16)
for c0 in range (1,17):
    for c1 in range (1,17):
        for c2 in range (1,17):
            for c3 in range (1,17):
                for c4 in range (1,17):
                    for c5 in range (1,17):
                        # affiche l'avancée :
                        print('c5 = %d / 16' % c5)
                        for c6 in range (1,17):
                            for c7 in range (1,17):
                                for c8 in range (1,17):
                                    for c9 in range (1,17):
                                        for c10 in range (1,17):
                                            for c11 in range (1,17):
                                                for c12 in range (1,17):
                                                    for c13 in range (1,17):
                                                        for c14 in range (1,17):
                                                            for c15 in range (1,17):
                                                                c=[c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15]
                                                                # on ne veut pas de doublons dans la liste c :
                                                                if len(set(c))!=16:
                                                                    break
                                                                # teste les 16 permutations circulaires de la liste c :
                                                                for i in range(16):
                                                                    if c[0]+c[1]+c[2]+c[3]==c[5]+c[5]+c[6]+c[7]==c[8]+c[9]+c[10]+c[11]==c[12]+c[13]+c[14]+c[15]==\
                                                                        c[0]+c[4]+c[8]+c[12]==c[1]+c[5]+c[9]+c[13]==c[2]+c[6]+c[10]+c[14]==c[3]+c[7]+c[11]+c[15]==\
                                                                        c[0]+c[5]+c[10]+c[15]==c[3]+c[6]+c[9]+c[12]:
                                                                            print("Carré magique trouvé :",c)
                                                                    # réalise une permutation circulaire (le dernier élément devient le premier) :
                                                                    c=[c[-1]]+c[:-1]