Créer un carré magique en Python n’est pas nécessairement facile. Nous allons voir sur cette page comment créer un objet représentant un carré magique : à l’aide d’une classe.
Cahier des charges du carré magique en Python
Faisons dans un premier temps une liste de tout ce que l’on souhaite:
- créer un objet MagicSquare admettant en argument une liste dont la dimension sera notée n², n étant un entier naturel supérieur ou égal à 3;
- afficher le carré magique sous forme de tableau;
- vérifier si un carré est magique.
Le constructeur
Une classe est quelque chose qui commence très souvent par un constructeur : c’est ce qui définit les composantes de l’objet (pour faire simple).
Nous allons donc commencer par écrire;
class MagicSquare :
def __init__(self, L) :
self.dim = int( len(L)**0.5 )
self.matrix = [ [ L[i+j*3] for i in range(self.dim) ] for j in range(self.dim) ]Le constructeur définit ainsi avant tout une variable dim rattachée à l’objet (avec le “préfixe” self.), qui va représenter la dimension d’une matrice carrée définie à partir des éléments de la liste passée en argument lors de l’appel à la classe. Ainsi, quand on écrit:
>>> square = MagicSquare ( [ 1,2,3,4,5,6,7,8,9 ] )
on construit la matrice:$$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix}$$ de dimension 3.
Affichage
Il nous faut maintenant pouvoir afficher le carré ainsi défini (la matrice). On écrit alors une fonction d’affichage dans la classe, que l’on appelle une méthode: comme son rôle est d’afficher l’objet, cette méthode doit être assimilée à une chaîne de caractères (mais pour l’objet défini); on va donc définir la méthode sous le nom “__str__”.
def __str__(self) :
out = ''
p = 1
w = int( log( self.dim , 10) ) + 1 # nombre de chiffres dans self.dim pour le formattage de l'affichage
formatage = '%' + str(w+3) + 'd'
for row in self.matrix:
for coef in row:
out += str( formattage % ( coef ) )
if p % self.dim == 0:
out += '\n'
p += 1
return outLà, je me suis un peu lâché car je voulais un “bel” affichage (dans la mesure du possible). J’ai donc formaté chaque coefficient en leur attribuant une dimension horizontale dépendante des coefficients. Avec cette méthode, en écrivant:
>>> square = MagicSquare ( [ 12,11,10,9,6,3,5,2,5 ] ) >>> print(square)
s’affiche:
12 11 10 9 6 3 5 2 5
Vérifier si le carré est magique en Python
Un carré est dit magique si la somme de chaque ligne, de chaque colonne et des deux diagonales est égale au même nombre. On arrive à démontrer (en mathématiques) que ce nombre est nécessairement égal à \(\frac{n(n^2+1)}{2}\). On peut alors imaginer une méthode isMagic qui renvoie “False” si le carré n’est pas magique, et “True” s’il l’est:
def isMagic(self):
# on vérifie d'abord si tous les nombres sont uniques
liste_nombres = []
for row in self.matrix:
for coef in row:
if coef not in liste_nombres:
liste_nombres.append( coef )
else:
return False
somme_theorique = self.dim * (self.dim**2 + 1) // 2
# somme de chaque ligne
for row in self.matrix:
somme = 0
for coef in row:
somme += coef
if somme != somme_theorique:
return False
# somme de chaque colonne
for column in range(self.dim):
somme = 0
for row in range(self.dim):
somme += self.matrix[row][column]
if somme != somme_theorique:
return False
# somme des diagonales
somme1 , somme2 = 0 , 0
for i in range(self.dim):
somme1 += self.matrix[i][i]
somme2 += self.matrix[i][self.dim-1-i]
if somme1 != somme_theorique or somme2 != somme_theorique:
return False
return TrueCette méthode n’est pas du tout optimale (car elle contient bien trop de boucles), mais cela fera l’affaire pour nous (mon but est d’être pédagogue et non de proposer tout de suite une méthode optimale). D’ailleurs, vous pouvez imaginer votre propre méthode en utilisant une autre philosophie que celle adoptée ici. Par exemple, vous pouvez jeter un coup d’œil sur cette page pour vous donner une autre idée (il y a des solutions bien plus efficaces, mais plus compliquées à comprendre).
Construire tous les carrés magiques d’une dimension donnée en Python
Nous allons nous servir de cette classe afin de construire tous les carrés magiques d’ordre 3.
def all_squares():
for a1 in range(1,10):
for a2 in range(1,10):
for a3 in range(1,10):
for b1 in range(1,10):
somme = a1 + a2 + a3
c1 = somme - a1 - b1
b2 = somme - a3 - c1
b3 = somme - b1 - b2
c2 = somme - a2 - b2
c3 = somme - c1 - c2
M = MagicSquare( [a1,a2,a3,b1,b2,b3,c1,c2,c3] )
if M.isMagic() and 0 < b2 < 10 and 0 < b3 < 10 and 0 < c1 < 10 and 0 < c2 < 10 and 0 < c3 < 10 :
print(M)
print("---------------")
all_squares()Cette solution, proposée par un élève du professeur qui a écrit cette page, fonctionne très bien. Elle affiche :
2 7 6 9 5 1 4 3 8 ------------ 2 9 4 7 5 3 6 1 8 ------------ 4 3 8 9 5 1 2 7 6 ------------ 4 9 2 3 5 7 8 1 6 ------------ 6 1 8 7 5 3 2 9 4 ------------ 6 7 2 1 5 9 8 3 4 ------------ 8 1 6 3 5 7 4 9 2 ------------ 8 3 4 1 5 9 6 7 2
Le programme Python complet est ci-dessous:
Avec les permutations
L’inconvénient de cette dernière méthode est que pour les carrés magiques d’ordre supérieur à 3, ça devient vite la galère. Aussi ai-je pensé aux permutations. Après tout, tel que défini plus haut, un carré magique n’est rien d’autre qu’une permutation de la liste [1,2,3,4,5,6,7,8,9] pour l’ordre 3.
Ainsi, le programme suivant donne la même chose:
from itertools import permutations
# affiche tous les carrés magiques d'ordre 3
for i in permutations(range(1,10)):
M = MagicSquare( i )
if M.isMagic():
print(M)Mais il faut bien avouer qu’il est légèrement plus lent. Et ce n’est rien comparé au cas où l’on regarde à l’ordre 4 !
Ce n’est donc clairement pas une solution à envisager…
Construction de carrés magiques d’ordres impairs
À partir d’ici, je vais changer de logique et abandonner la P.O.O. pour construire des carrés magiques quelconques d’ordres impairs.
Pour cela, je vais m’appuyer sur la méthode siamoise.
from numpy import array, zeros
def magic_even(S , line=None , col=None , number=1, orientation=None):
# Méthode siamoise, implémentée par Stéphane Pasquet (mathweb.fr)
if 0 not in S: return S
else:
start = { 'NE' : (0,len(S)//2),
'SE' : (len(S)-1,len(S)//2),
'NO' : (0,len(S)//2),
'SO' : (len(S)-1,len(S)//2)}
if col == None and line == None:
line, col = start[orientation][0] , start[orientation][1]
coin = { 'NE' : [ ( -1 ,len(S)) , 2, -1, len(S)-1, 0 ],
'SE' : [ (len(S),len(S)) , -2, -1, 0 , 0 ],
'NO' : [ ( -1 , -1 ) , 2, 1, len(S)-1, len(S)-1 ],
'SO' : [ (len(S) , -1 ) , -2, 1, 0 , len(S)-1 ]}
remp = {'NE' : [-1,1,2,-1] ,
'SE' : [1,1,-2,-1] ,
'NO' : [-1,-1,2,1] ,
'SO' : [1,-1,-2,1]}
if line == coin[orientation][0][0] and col == coin[orientation][0][1]:
line = line + coin[orientation][1]
col = col + coin[orientation][2]
if line == coin[orientation][0][0]:
line = coin[orientation][3]
if col == coin[orientation][0][1]:
col = coin[orientation][4]
if S[line][col] == 0:
S[line][col] = number
line = line + remp[orientation][0]
col = col + remp[orientation][1]
number += 1
else:
line = line + remp[orientation][2]
col = col + remp[orientation][3]
return magic_even(S,line,col,number,orientation)
def magic_square(n,direction):
if n%2 == 1: return magic_even(zeros((n,n),dtype=int),orientation=direction)
#else: magic_odd(n) # pour plus tard peut-être...>>> print( magic_square(3,'SO') )
[[2 9 4]
[7 5 3]
[6 1 8]]La fonction magic_square prend deux arguments: la dimension du carré magique souhaité (pour l’instant, seuls les nombres impairs sont pris en compte) et la direction souhaitée pour appliquer la méthode siamoise (‘NE’, ‘SE’, ‘NO’ ou ‘SO’).
L’objet retourné par cette fonction est un array. Il est donc nécessaire de faire appel au module numpy.
L’inconvénient de cette fonction est qu’elle ne retourne pas l’ensemble de tous les carrés magiques. Cependant, en considérant les quatre carrés obtenus avec les différentes directions, ainsi que leur transposé, on en a huit.
>>> for d in ('SO', 'NO', 'SE', 'NE'):
C = magic_square(3,d)
print( C , end='\n\n')
print( transpose(C) )
[[2 9 4]
[7 5 3]
[6 1 8]]
[[2 7 6]
[9 5 1]
[4 3 8]]
[[6 1 8]
[7 5 3]
[2 9 4]]
[[6 7 2]
[1 5 9]
[8 3 4]]
[[4 9 2]
[3 5 7]
[8 1 6]]
[[4 3 8]
[9 5 1]
[2 7 6]]
[[8 1 6]
[3 5 7]
[4 9 2]]
[[8 3 4]
[1 5 9]
[6 7 2]]J’ai aussi implémenté une fonction pour vérifier si un carré est magique:
from numpy import array, transpose, zeros
def is_magic(square):
somme = len(square) * ( len(square)**2 + 1) // 2
sum_col = sum( square )
sum_lines = sum( transpose(square) )
# on vérifie si les entiers de 1 à n sont tous présents une unique fois
s = sorted( [ square[i][j] for i in range(len(square)) for j in range(len(square)) ] )
for i in range(len(square)):
if s[i] != i+1: return False
# on teste si les deux tableaux de sommes de lignes et colonnes sont égaux
# ou (dans le cas où ils sont égaux) si la somme trouvée est bien égale à n(n²+1)/2
if not (sum_col == sum_lines).all() or sum_col[0] != somme:
return False
# si les sommes des lignes et des colonnes correspondent à nos attentes,
# on vérifie la somme des diagonales
sum_diag1 = sum( array( [ square[i][j] for i in range(len(square)) for j in range(len(square)) if i==j ] ) )
sum_diag2 = sum( array( [ square[len(square)-1-i][j] for i in range(len(square)) for j in range(len(square)) if i==j ] ) )
return sum_diag1 == somme and sum_diag2 == somme>>> C = magic_square(3,'SO')
>>> is_magic(C)
True