Magische Quadrate, Teil II
The Update
Nachdem der erste Text den Brute-Force-Angriff auf alle Zahlen beschrieb, gilt es nun, sich dem Problem auf elegante Art und Weise zu nähern. Der erste Versuch generierte alle denkbaren Quadrate und sortierte einfach die aus, die nicht passten. Effizienter, und vor allem für Menschen ohne Computer die einzig denkbare Variante ist aber, eine Formel aufzustellen, die sämtliche magischen Quadrate erzeugt, ohne daß man eine Überprüfung folgen lassen müsste.
Zuerst einmal gibt es einen vom Aufbau recht einfachen Ansatz, welcher auf zwei Quadraten basiert:
A = [1,2,3,4] B = [1,2,3,4]
[3,4,1,2] [4,3,2,1]
[4,3,2,1] [2,1,4,3]
[2,1,4,3] [3,4,1,2]Beide Quadrate erfüllen die Grundbedingungen, das heißt eine konstante Summe für Spalten, Zeilen und Diagonalen. Nun kann man die Zahlen von 1 bis 4 beliebig vertauschen, ohne daß diese Eigenschaft verloren geht. Es gibt insgesamt 4! = 24 dieser Permutationen. Um nun magische Quadrate zu erzeugen, addiert man die Elemente der Basisquadrate wie folgt:
C(ij) = 4 * A(ij) + B(ij) - 4
(ij) bezeichnet dabei den Spalten bzw. Zeilenindex. Das funktioniert natürlich auch umgekehrt:
C(ij) = 4 * B(ij) + A(ij) - 4
Das Resultat sind 24 * 24 * 2 = 1152 Lösungen, da in beiden Formen jeweils 24 Permutationen beider Quadrate möglich sind. Faszinierend an diesem Ansatz ist nun, daß man die Basisquadrate A und B auf ein Quadrat zurückführen kann. Eine Permutation von B,
B = [1,3,4,2]
[2,4,3,1]
[3,1,2,4]
[4,2,1,3]ist gleich der Spiegelung an der Hauptachse von A. Nur leider hat diese Lösung einen Nachteil: Sie erzeugt Lösungen, die nicht allen Anforderungen gerecht werden. Da die Basis-Quadrate nur die Forderungen nach Spalten, Zeilen und Diagonalensummen gerecht werden, sind die Eckpunktsumme und die Unterquadrate nicht berücksichtigt. Da sich die Unterquadrate auf zwei Basisabfragen, nämlich die der Quadrate [b,c,f,g] und [e,f,i,j] für das allgemeine Quadrat
[a,b,c,d] [e,f,g,h] [i,j,k,l] [m,n,o,p]
reduzieren lassen, fehlen drei Bedingungen, was die Zahl 1152 = 3 * 384 erklärt. Ein zweiter Weg schafft hier Abhilfe: Man verwendet statt Quadraten mit Zahlen von 1 bis 4 solche mit 0 und 1:
A = [1,1,0,0] B = [1,0,1,0] C = [1,1,1,1]
[0,0,1,1] [0,1,0,1] [1,1,1,1]
[1,1,0,0] [0,1,0,1] [1,1,1,1]
[0,0,1,1] [1,0,1,0] [1,1,1,1]Daraus konstruiert man nun wie folgt sein erstes magisches Quadrat:
8 * A + 4 * B + 2 * At + Bt + C
Wobei At und Bt Translationen der Basisquadrate sind (gespiegelt an der Hauptachse). Ein Beispiel:
8 * [1,1,0,0] + 4 * [1,0,1,0] + 2 * [1,0,1,0] +
[0,0,1,1] [0,1,0,1] [1,0,1,0]
[1,1,0,0] [0,1,0,1] [0,1,0,1]
[0,0,1,1] [1,0,1,0] [0,1,0,1]
1 * [1,0,0,1] + 1 * [1,1,1,1] = [16, 9, 7, 2]
[0,1,1,0] [1,1,1,1] [ 3, 6,12,13]
[1,0,0,1] [1,1,1,1] [10,15, 1, 8]
[0,1,1,0] [1,1,1,1] [ 5, 4,14,11]Um nun aus den gegebenen Bitmustern alle 384 Quadrate zu bekommen, sind folgende Operationen nötig: Man kann die Bitmuster invertieren. A sieht dann so aus:
A = [0,0,1,1]
[1,1,0,0]
[0,0,1,1]
[1,1,0,0]Mathematisch gesprochen heißt das dann:
Für eine 4 x 4 Matrix M und k e {0,1} gilt
M_k = M, falls k = 0 und
M_k = C-k, falls k = 1.
Es gilt also
(k1,k2,k3,k4) e {0,1}^4
sowie die erweitere Formulierung des obigen Terms
8 * A_k1 + 4 * B_k2 + 2 * At_k3 + Bt_k4 + C
Das ergibt dann 4! * 2^4 = 384 magische Quadrate.
An dieser Stelle möchte ich Harald Oelschlaeger für den ersten und Markus Schick für den zweiten Ansatz danken, ohne sie wäre es wohl immer bei der Brute-Force-Attacke geblieben. Wer sich für Themen wie diese beigeistern kann, sollte übrigens auch einmal einen Blick in die Newsgruppe de.sci.mathematik werfen.