classe CarreMagique
class CarreMagique :
def __init__(self, coef) :
self.mat = [ [ coef[i+j*3] for i in range(3) ] for j in range(3) ]
def __str__(self) :
return "\n".join ( [ ",".join( [ str(n) for n in row ] ) for row in self.mat ] )
def __add__ (self, carre) :
coef = []
for i in range(3) :
for j in range(3) :
coef.append ( self.mat[i][j] + carre.mat[i][j])
return CarreMagique(coef)
c = CarreMagique ( [ 1,3,4, 2,6,9, 8,7,5 ] )
print (c)
print (c + c)
fonction est_magique
Fonction \codes{est\_magique}:
class CarreMagique :
def __init__(self, coef) :
self.mat = [ [ coef[i+j*3] for i in range(3) ] for j in range(3) ]
def __str__(self) :
return "\n".join ( [ ",".join( [ str(n) for n in row ] ) for row in self.mat ] )
def __add__ (self, carre) :
coef = []
for i in range(3) :
for j in range(3) :
coef.append ( self.mat[i][j] + carre.mat[i][j])
return CarreMagique(coef)
def somme_ligne_colonne_diagonale(self):
tout = [ sum ( ligne ) for ligne in self.mat ] + \
[ sum ( [ self.mat[i][j] for j in range(3) ] ) for i in range(3) ] + \
[ sum ( [ self.mat[i][i] for i in range(3) ] ) ] + \
[ sum ( [ self.mat[2-i][i] for i in range(3) ] ) ]
return tout
def coefficient_unique(self):
d = { }
for ligne in self.mat :
for c in ligne :
d [c] = d.get(c,0) + 1
return len(d) == 9
def est_magique(self):
unique = self.coefficient_unique()
if not unique : return False
somme = self.somme_ligne_colonne_diagonale()
return min(somme) == max(somme)
c = CarreMagique ( [ 1,1,1, 1,1,1, 1,1,1 ] )
print (c.est_magique())
c = CarreMagique ( [ 1,4,8, 5,2,6, 7,9,3 ] )
print (c.est_magique())
tous les carrés, de façon naïve (1)
def tous_les_carre_naif() :
res = []
for a1 in range(9) :
for a2 in range(9) :
for a3 in range(9) :
for b1 in range(9) :
for b2 in range(9) :
for b3 in range(9) :
for c1 in range(9) :
for c2 in range(9) :
for c3 in range(9) :
carre = CarreMagique( [a1,a2,a3, b1,b2,b3, c1,c2,c3 ])
if carre.est_magique() :
res.append (carre)
print (carre)
return res
tous les carrés, de façon naïve (2)
def tous_les_carre_naif2() :
# on choisit l'ensemble de tous les tableaux de 9 chiffres compris entre 1 et 9
coef = [ 1 ] * 9
res = [ ]
while coef [0] < 10 :
carre = CarreMagique(coef)
if carre.est_magique() :
res.append (carre)
print (carre)
coef[-1] += 1
if coef[-1] >= 10 :
i = len(coef)-1
while coef[i] >= 10 and i > 0 :
coef[i] = 1
coef[i-1] += 1
i -= 1
tous les carrés, permutation
#coding:latin-1
def tous_les_carres_permutation( permut = None, pos = 0):
if pos == 9 :
carre = CarreMagique (permut)
if carre.est_magique() :
print (carre)
print ()
return [ carre ]
else :
return []
else :
res = [ ]
if permut == None :
permut = [ i+1 for i in range(9) ]
for i in range (pos,9) :
# on permute les éléments i et pos
a = permut[i]
permut[i] = permut[pos]
permut[pos] = a
res += tous_les_carres_permutation(permut, pos+1)
# on effectue la permutation inverse
a = permut[i]
permut[i] = permut[pos]
permut[pos] = a
return res
res = tous_les_carres_permutation()
print ("nombre de carrés", len(res))
mesure du temps d'exécution
import time
d = time.clock()
res = tous_les_carres_permutation()
d = time.clock() - d
print ("nombre de carrés", len(res), " en ", d)
carré magique, réduction du nombre de permutations évaluées
def tous_les_carres_permutation_ligne12_meme_somme( permut = None, pos = 0):
if pos == 9 :
carre = CarreMagique (permut)
if carre.est_magique() :
#print (carre)
#print ()
return [ carre ]
else :
return []
else :
if pos >= 6 : # ajout
if sum ( permut[:3]) != sum(permut[3:6]) : # ajout
return [ ] # ajout
res = [ ]
if permut == None :
permut = [ i+1 for i in range(9) ]
for i in range (pos,9) :
# on permute les éléments i et pos
a = permut[i]
permut[i] = permut[pos]
permut[pos] = a
res += tous_les_carres_permutation_ligne12_meme_somme(permut, pos+1) # changé
# on effectue la permutation inverse
a = permut[i]
permut[i] = permut[pos]
permut[pos] = a
return res
parcours des carrés magiques, version complète
#coding:latin-1
class CarreMagique :
def __init__(self, coef) :
self.mat = [ [ coef[i+j*3] for i in range(3) ] for j in range(3) ]
def __str__(self) :
return "\n".join ( [ ",".join( [ str(n) for n in row ] ) for row in self.mat ] )
def __add__ (self, carre) :
coef = []
for i in range(3) :
for j in range(3) :
coef.append ( self.mat[i][j] + carre.mat[i][j])
return CarreMagique(coef)
def somme_ligne_colonne_diagonale(self):
tout = [ sum ( ligne ) for ligne in self.mat ] + \
[ sum ( [ self.mat[i][j] for j in range(3) ] ) for i in range(3) ] + \
[ sum ( [ self.mat[i][i] for i in range(3) ] ) ] + \
[ sum ( [ self.mat[2-i][i] for i in range(3) ] ) ]
return tout
def coefficient_unique(self):
d = { }
for ligne in self.mat :
for c in ligne :
d [c] = d.get(c,0) + 1
return len(d) == 9
def est_magique(self):
unique = self.coefficient_unique()
if not unique : return False
somme = self.somme_ligne_colonne_diagonale()
return min(somme) == max(somme)
def tous_les_carres_permutation_ligne12_meme_somme( permut = None, pos = 0):
if pos == 9 :
carre = CarreMagique (permut)
if carre.est_magique() :
#print (carre)
#print ()
return [ carre ]
else :
return []
else :
if pos >= 6 : # ajout
if sum ( permut[:3]) != sum(permut[3:6]) : # ajout
return [ ] # ajout
res = [ ]
if permut == None :
permut = [ i+1 for i in range(9) ]
for i in range (pos,9) :
# on permute les éléments i et pos
a = permut[i]
permut[i] = permut[pos]
permut[pos] = a
res += tous_les_carres_permutation_ligne12_meme_somme(permut, pos+1) # changé
# on effectue la permutation inverse
a = permut[i]
permut[i] = permut[pos]
permut[pos] = a
return res
import time
d = time.clock()
res = tous_les_carres_permutation_ligne12_meme_somme()
d = time.clock() - d
print ("nombre de carrés", len(res), " en ", d)