Aller au contenu

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(bksl-nl [bksl-nl [2, 7, 6],bksl-nl [9, 5, 1],bksl-nl [4, 3, 8],bksl-nl ]bksl-nl)bksl-nlassert not estpy-undcarrepy-undmagique(bksl-nl [bksl-nl [1, 6, 5],bksl-nl [8, 4, 0],bksl-nl [3, 2, 7],bksl-nl ]bksl-nl), "0 est présent ; interdit"bksl-nlassert not estpy-undcarrepy-undmagique(bksl-nl [bksl-nl [3, 8, 7],bksl-nl [10, 6, 2],bksl-nl [5, 4, 9],bksl-nl ]bksl-nl), "1 est absent ; interdit"bksl-nlassert not estpy-undcarrepy-undmagique(bksl-nl [bksl-nl [1, 1, 1],bksl-nl [1, 1, 1],bksl-nl [1, 1, 1],bksl-nl ]bksl-nl), "beaucoup d'absents ; interdit"bksl-nlassert not estpy-undcarrepy-undmagique(bksl-nl [bksl-nl [4, 3, 8],bksl-nl [2, 7, 6],bksl-nl [9, 5, 1],bksl-nl ]bksl-nl), "erreur avec les diagonales"bksl-nlassert not estpy-undcarrepy-undmagique(bksl-nl [bksl-nl [7, 6, 2],bksl-nl [5, 1, 9],bksl-nl [3, 8, 4],bksl-nl ]bksl-nl), "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 + 2 py-str j - 2) % n) + 1bksl-nlbksl-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-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-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-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 + n py-str jbksl-nl else:bksl-nl return n py-str n - (i + n py-str j)bksl-nlbksl-nl return [[case(i, j) for j in range(n)] for i in range(n)]bksl-nlbksl-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-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-nldef estpy-undcarrepy-undmagique(carre):bksl-nl n = len(carre)bksl-nl somme = n py-str (n py-str n + 1) // 2bksl-nlbksl-nl # test des lignesbksl-nl for i in range(n):bksl-nl sommepy-undi = sum(carre[i][j] for j in range(n))bksl-nl if sommepy-undi != somme:bksl-nl return Falsebksl-nlbksl-nl # test des colonnesbksl-nl for j in range(n):bksl-nl sommepy-undj = sum(carre[i][j] for i in range(n))bksl-nl if sommepy-undj != somme:bksl-nl return Falsebksl-nlbksl-nl # test des diagonalesbksl-nl sommepy-undd1 = sum(carre[i][i] for i in range(n))bksl-nl if sommepy-undd1 != somme:bksl-nl return Falsebksl-nl sommepy-undd2 = sum(carre[i][n - 1 - i] for i in range(n))bksl-nl if sommepy-undd2 != somme:bksl-nl return Falsebksl-nlbksl-nl # test présence uniquebksl-nl dejapy-undvu = [False] py-str (n py-str n + 1)bksl-nl for i in range(n):bksl-nl for j in range(n):bksl-nl if not (1 <= carre[i][j] <= n py-str n):bksl-nl return Falsebksl-nlbksl-nl if dejapy-undvu[carre[i][j]]:bksl-nl return Falsebksl-nl dejapy-undvu[carre[i][j]] = Truebksl-nlbksl-nl return Truebksl-nlbksl-nl

A

Z

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\).