Carrés magiques normaux d'ordre n⚓︎

Un carré magique normal d'ordre \(n\) est une grille carrée remplie de tous les entiers de \(1\) à \(n^2\), telle que les sommes suivantes sont égales :

la somme des nombres de chaque ligne,
la somme des nombres de chaque colonne,
la somme des nombres des deux diagonales.

Carré magique d'ordre \(3\)

🐍 Script Python

ex_ordre_3 = [
    [2, 7, 6],
    [9, 5, 1],
    [4, 3, 8],
]

Voici un exemple avec tous les entiers de \(1\) à \(9\).

la somme de chaque ligne est égale à \(15\)
- \(2+7+6 = 15\)
- \(9+5+1 = 15\)
- \(4+3+8 = 15\)
la somme de chaque colonne est égale à \(15\) ;
- \(2+9+4 = 15\)
- \(7+5+3 = 15\)
- \(6+1+8 = 15\)
la somme de chaque diagonale est égale à \(15\).
- \(2+5+8 = 15\)
- \(4+5+6 = 15\)

Carré magique d'ordre \(4\)

🐍 Script Python

ex_ordre_4 = [
    [16,  3,  2, 13],
    [ 5, 10, 11,  8],
    [ 9,  6,  7, 12],
    [ 4, 15, 14,  1],
]

Ce carré magique était connu du peintre allemand Albrecht Dürer, qui l'a inclus dans sa gravure Melencolia.

Écrire une fonction telle que est_carre_magique(carre) renvoie un booléen, la réponse à la question : carre est-il un carré magique normal ?

On garantit que carre est un tableau 2D de forme carrée, rempli d'entiers ; il y a autant de lignes que de colonnes et toutes les lignes ont le même nombre de colonnes.

Exemples

🐍 Console Python

>>> ex_ordre_3 = [
...     [2, 7, 6],
...     [9, 5, 1],
...     [4, 3, 8],
... ]
>>> est_carre_magique(ex_ordre_3)
True

Les entiers de \(1\) à \(9\) sont disposés, avec une somme de 3 alignés égale à \(15\).

🐍 Console Python

>>> contre_ex_ordre_2 = [
...     [2, 2],
...     [2, 2],
... ]
>>> est_carre_magique(contre_ex_ordre_2)
False

Certes, toutes les sommes sont identiques, mais les entiers de \(1\) à \(4\) ne sont pas tous présents.

🐍 Console Python

>>> ex_ordre_4 = [
...     [16,  3,  2, 13],
...     [ 5, 10, 11,  8],
...     [ 9,  6,  7, 12],
...     [ 4, 15, 14,  1],
... ]
>>> est_carre_magique(ex_ordre_4)
True

Les entiers de \(1\) à \(16\) sont disposés, avec une somme de 4 alignés égale à \(34\).

###

# testsbksl-nlbksl-nlexpy-undordrepy-und3 = [bksl-nl [2, 7, 6],bksl-nl [9, 5, 1],bksl-nl [4, 3, 8],bksl-nl]bksl-nlassert estpy-undcarrepy-undmagique(expy-undordrepy-und3)bksl-nlbksl-nlcontrepy-undexpy-undordrepy-und2 = [bksl-nl [2, 2],bksl-nl [2, 2],bksl-nl]bksl-nlassert not estpy-undcarrepy-undmagique(contrepy-undexpy-undordrepy-und2)bksl-nlbksl-nlexpy-undordrepy-und4 = [bksl-nl [16, 3, 2, 13],bksl-nl [ 5, 10, 11, 8],bksl-nl [ 9, 6, 7, 12],bksl-nl [ 4, 15, 14, 1], bksl-nl]bksl-nlassert estpy-undcarrepy-undmagique(expy-undordrepy-und4)bksl-nlbksl-nl# autres testsbksl-nlbksl-nl# ordre 3bksl-nlassert estpy-undcarrepy-undmagique([[2, 7, 6], [9, 5, 1], [4, 3, 8],])bksl-nlassert not estpy-undcarrepy-undmagique([[1, 6, 5], [8, 4, 0], [3, 2, 7],]), "0 est présent ; interdit"bksl-nlassert not estpy-undcarrepy-undmagique([[3, 8, 7], [10, 6, 2], [5, 4, 9],]), "1 est absent ; interdit"bksl-nlassert not estpy-undcarrepy-undmagique([[1, 1, 1], [1, 1, 1], [1, 1, 1],]), "beaucoup d'absents ; interdit"bksl-nlassert not estpy-undcarrepy-undmagique([[4, 3, 8], [2, 7, 6], [9, 5, 1],]), "erreur avec les diagonales"bksl-nlassert not estpy-undcarrepy-undmagique([[7, 6, 2], [5, 1, 9], [3, 8, 4],]), "erreur avec les diagonales"bksl-nlbksl-nl# ordre 1bksl-nlassert estpy-undcarrepy-undmagique([[1]])bksl-nlassert not estpy-undcarrepy-undmagique([[0]])bksl-nlassert not estpy-undcarrepy-undmagique([[-1]])bksl-nlassert not estpy-undcarrepy-undmagique([[2]])bksl-nlassert not estpy-undcarrepy-undmagique([[128]])bksl-nlbksl-nl# ordre n impairbksl-nldef magiquepy-undf(i, j, n):bksl-nl assert n%2 == 1bksl-nl return n py-str ((i + j + (n-3)//2)%n) + ((i + 2py-strj - 2) % n) + 1bksl-nlbksl-nldef rotation(carre):bksl-nl n = len(carre)bksl-nl carre = [[carre[n-1-j][i] for j in range(n)] for i in range(n)]bksl-nlbksl-nldef switch(carre):bksl-nl # on inverse deux lignes extremes et deux colonnes extremesbksl-nl n = len(carre)bksl-nl carre[0], carre[-1] = carre[-1], carre[0]bksl-nl for i in range(n):bksl-nl carre[i][0], carre[i][-1] = carre[i][-1], carre[i][0]bksl-nlbksl-nlfor n in range(3, 21, 2):bksl-nl carre = [[magiquepy-undf(i, j, n) for j in range(1, n+1)] for i in range(1, 1+n)]bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl switch(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl carre[0][-1] += 1bksl-nl carre[0][-2] -= 1bksl-nl carre[1][-1] -= 1bksl-nl carre[1][-2] += 1bksl-nl carre[-1][0] -= 1bksl-nl carre[-1][1] += 1bksl-nl carre[-2][0] += 1bksl-nl carre[-2][1] -= 1bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl switch(carre)bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nlbksl-nl# ordre n pairbksl-nlbksl-nlsoleil = [bksl-nl [ 6, 32, 3, 34, 35, 1],bksl-nl [ 7, 11, 27, 28, 8, 30],bksl-nl [19, 14, 16, 15, 23, 24],bksl-nl [18, 20, 22, 21, 17, 13],bksl-nl [25, 29, 10, 9, 26, 12],bksl-nl [36, 5, 33, 4, 2, 31],bksl-nl]bksl-nlassert estpy-undcarrepy-undmagique(soleil), "Erreur avec le carré dit 'du Soleil'"bksl-nlbksl-nlfranklin = [bksl-nl [52, 61, 4, 13, 20, 29, 36, 45],bksl-nl [14, 3, 62, 51, 46, 35, 30, 19],bksl-nl [53, 60, 5, 12, 21, 28, 37, 44],bksl-nl [11, 6, 59, 54, 43, 38, 27, 22],bksl-nl [55, 58, 7, 10, 23, 26, 39, 42],bksl-nl [ 9, 8, 57, 56, 41, 40, 25, 24],bksl-nl [50, 63, 2, 15, 18, 31, 34, 47],bksl-nl [16, 1, 64, 49, 48, 33, 32, 17],bksl-nl]bksl-nlassert estpy-undcarrepy-undmagique(soleil), "Erreur avec le carré de Benjamin Franklin"bksl-nlbksl-nldef magiquepy-und4(n):bksl-nl assert n%4 == 0bksl-nlbksl-nl def case(i, j):bksl-nl if ((i + j + 1) % 4 == 0) or ((i - j) % 4 == 0):bksl-nl return 1 + i + npy-strjbksl-nl else:bksl-nl return n py-str n - (i + npy-strj)bksl-nlbksl-nl return [[case(i, j) for j in range(n)] for i in range(n)]bksl-nlbksl-nlfor n in range(4, 21, 4):bksl-nl carre = magiquepy-und4(n)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl switch(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl carre[0][-1] += 1bksl-nl carre[0][-2] -= 1bksl-nl carre[1][-1] -= 1bksl-nl carre[1][-2] += 1bksl-nl carre[-1][0] -= 1bksl-nl carre[-1][1] += 1bksl-nl carre[-2][0] += 1bksl-nl carre[-2][1] -= 1bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl switch(carre)bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nl rotation(carre)bksl-nl assert not estpy-undcarrepy-undmagique(carre), f"Erreur avec n = {n}"bksl-nlbksl-nl ∞/∞

def estpy-undcarrepy-undmagique(carre):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlexpy-undordrepy-und3 = [bksl-nl [2, 7, 6],bksl-nl [9, 5, 1],bksl-nl [4, 3, 8],bksl-nl]bksl-nlassert estpy-undcarrepy-undmagique(expy-undordrepy-und3)bksl-nlbksl-nlcontrepy-undexpy-undordrepy-und2 = [bksl-nl [2, 2],bksl-nl [2, 2],bksl-nl]bksl-nlassert not estpy-undcarrepy-undmagique(contrepy-undexpy-undordrepy-und2)bksl-nlbksl-nlexpy-undordrepy-und4 = [bksl-nl [16, 3, 2, 13],bksl-nl [ 5, 10, 11, 8],bksl-nl [ 9, 6, 7, 12],bksl-nl [ 4, 15, 14, 1], bksl-nl]bksl-nlassert estpy-undcarrepy-undmagique(expy-undordrepy-und4)bksl-nlbksl-nlbksl-nlNone

Indice 1

En utilisant la formule \(1+2+3+\cdots+n^2 = \dfrac{n^2(n^2+1)}{2}\), il est possible de déterminer la somme commune d'un carré magique normal d'ordre \(n\), sans même avoir lu une seule ligne du tableau.

Indice 2

On pourra procéder par étapes. À chaque test qui échoue, la fonction peut renvoyer False.

À la fin, si tous les critères sont validés, la fonction renvoie True.

Indice 3

Pour vérifier la présence unique des nombres de \(1\) à \(n^2\), on pourra utiliser un tableau de booléen deja_vu de longueur \(n^2+1\).

On pensera à tester au passage que les entiers sont bien de \(1\) à \(n^2\).