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

def magic_even(S , line=None , col=None , number=1, orientation=None):
    # Méthode siamoise
    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)
    
if __name__ == "__main__":
    for d in ('SO', 'NO', 'SE', 'NE'):
        C = magic_square(3,d)
        print( C , is_magic(C) , end='\n\n')
        print( transpose(C) , is_magic(transpose(C)) , end = '\n\n' )