Die Geschichte des kleinsten trimagischen Quadrats
Geschrieben von Walter Trump im Januar 2003


Am 25.04.2002 machte mich Aale de Winkel, ein Freund aus Holland, auf eine neue Internetseite mit der Adresse www.multimagie.com aufmerksam. Der Franzose Christian Boyer beschreibt auf dieser Seite die historische Entwicklung der multimagischen Quadrate und die Entdeckung der ersten tetra- und penta-magischen Quadrate durch ihn selbst und seinen Freund André Viricel. Ein multimagisches Quadrat ist ein magisches Quadrat, das magisch bleibt, wenn man von allen seinen Zahlen bestimmte Potenzen bildet (hoch 2, hoch 3, ...).

Für die Konstruktion multimagischer Quadrate der Ordnung n ist die Berechnung multimagischer Reihen von Bedeutung; das sind alle möglichen Kombinationen von n verschiedenen natürlichen Zahlen kleiner gleich n², deren Summen der ersten, zweiten, ... Potenzen jeweils einen bestimmten konstanten Wert ergeben. Mit anderen Worten, unter allen Zahlenfolgen sind dies die potenziellen Kandidaten für die Zeilen und Spalten der multimagischen Quadrate.

Eine trimagische Reihe der Ordnung 8

1  + 19  + 23  + 24  + 36  + 42  + 53  + 62  =     260 = (1  + 2  + ... + 64 ) / 8
1
2 + 192 + 232 + 242 + 362 + 422 + 532 + 622 =  11,180 = (12 + 22 + ... + 642) / 8
1
3 + 193 + 233 + 243 + 363 + 423 + 533 + 623 = 540,800 = (13 + 23 + ... + 643) / 8

Zwischen Christian Boyer und mir entstand eine rege E-Mail-Konversation über bimagische Reihen. Mitte Mai hatte er die Idee von bimagischen zu TRImagischen Reihen überzugehen und bat mich seine Anzahl von 121 trimagischen Reihen der Ordnung 8 zu überprüfen. Am 18. Mai bestätigte ich dieses Ergebnis. Dies war der Startschuss für die Suche nach trimagischen Quadraten.

Unter anderem diskutierten wir darüber, ob es ein kleineres trimagisches Quadrat gibt, als das von Benson gefundene, es hat die Ordnung 32 (d.h. 32 Zeilen und 32 Spalten). An dieser Diskussion beteiligten sich, wenn auch weniger intensiv, noch weitere Liebhaber magischer Quadrate aus aller Welt. Einige vermuteten, dass 32 bereits die kleinstmögliche Ordnung wäre (z. B. George Chen aus Taiwan), andere meinten 27 (André Viricel aus Frankreich), keiner zog Ordnungen unter 16 in Erwägung.

Christian Boyer hatte bereits nachgewiesen, dass Ordnungen kleiner 10 nicht in Frage kommen. Ich konnte mit anderen Methoden seine Ergebnisse bestätigen und zusätzlich beweisen, dass es kein trimagisches Quadrat mit der Ordnung kleiner 12 geben kann.

Im Rahmen dieser Überlegungen berechneten wir für kleine Ordnungen n alle trimagischen Reihen. Bis zur Ordnung 10 konnten diese relativ schnell ermittelt werden. Bei der Ordnung 11 kam ich nach Berichtigung eines kleinen Fehlers auf die gleiche Anzahl wie Christian Boyer. Um alle trimagischen Reihen der Ordnung 12 zu finden, waren einige Tage Rechenzeit (auf einem gewöhnlichen PC) notwendig. Ich fand nicht weniger als  2 226 896  trimagische Reihen der Ordnung 12. Bislang wurde dieses Ergebnis von niemandem bestätigt. Alle Reihen bestehen aus 6 geraden und 6 ungeraden Zahlen.

Trimagische Reihen mit 6 ungeraden und 6 geraden Zahlen

 1   5  45  69  73 143  70  72  74  86  90 142
 1   5  45  75  91 143  68  70  72  74  84 142
 1   5  47  77  87 143  60  70  72  82  84 142
  ...
93  95 101 111 125 139   4  22  40  42  48  50
93  97 113 115 125 129  10  26  30  42  44  46
99 111 113 115 117 125  22  26  28  30  40  44

Nun stellte sich die Frage, ob man aus den trimagischen Reihen auch tatsächlich ein trimagisches Quadrat der Ordnung 12 bilden kann. Stellen Sie sich das Folgende wie die Suche nach einem goldenen Schatz vor. Wo soll man suchen? Wie soll man suchen? Existiert der goldene Schatz überhaupt?

Würde man mit 'Brute Force' (d. h. mit roher Gewalt) zum Ziel kommen? Man könnte mit dem Computer normale magische Quadrate der Ordnung 12 berechnen und jeweils testen, ob zusätzlich trimagische Eigenschaften vorliegen. Ein solcher Versuch scheitert kläglich an der immens großen Anzahl von magischen Quadraten der Ordnung 12. Nach meinen statistischen Näherungen beträgt die Anzahl dieser Quadrate nämlich mehr als 10188 (eine Zahl mit 189 Stellen - jenseits jeder menschlichen Vorstellungskraft).

Ein anderer Ansatz könnte darin bestehen 12 unabhängige trimagische Reihen zu finden, welche die Zeilen des Quadrats bilden. Anschließend könnte man die Zahlen innerhalb der Zeilen umordnen bis auch die Spalten trimagische Reihen sind. Doch auch dieser Weg ist wenig erfolgversprechend, weil die prognostizierten Rechenzeiten bei einigen Milliarden Jahren liegen.

Das ‚Gebiet’ für die Schatzsuche musste noch enger begrenzt werden. Deshalb wurde die Suche auf so genannte achsensymmetrische Quadrate beschränkt. Bei diesen ist die Summe von zwei symmetrisch gelegenen Zahlen stets gleich n²+1. Zwei Zahlen mit dieser Summe werden komplementär genannt. Für die Zeilen kamen jetzt nur noch symmetrische trimagische Reihen in Frage und für die Spalten solche ohne komplementäre Zahlenpaare. Außerdem braucht nur noch die linke Hälfte des Quadrats (72 Zahlen)  berechnet werden, die rechte ergibt sich aus der Symmetrie.

Damit stand das Gebiet der Schatzsuche fest, aber noch nicht die Suchmethode. Wenn man nach Gold sucht, kann man zunächst prüfen ob überhaupt Metall vorhanden ist. Wenn man nach magischen Quadraten sucht, kann man zunächst nach so genannten semi-magischen Quadraten Ausschau halten. Bei diesen Quadraten spielt die Summe der Zahlen in den Diagonalen keine Rolle.

Bei semi-magischen Quadraten bleiben die Eigenschaften erhalten, wenn man die Zeilen bzw. Spalten umordnet. Daher kann man eine beliebige Zahl in das linke obere Feld setzen. Ich wählte die Zahl 23, weil sie am häufigsten innerhalb der trimagischen Reihen vorkommt. Damit ergeben sich nur noch 3 646 Möglichkeiten für die erste Zeile, 107 099 Möglichkeiten für die erste Spalte, 33 004 für jede weitere Zeile und 473 663 für jede weitere Spalte. Das sind immer noch viel zu viele Möglichkeiten für eine Trial-and-Error-Strategie. Wenn man die erste Zeile und die erste Spalte vorgibt, müssen nur noch 55 Zahlen berechnet werden. Mit einem Trick ist es möglich, die potenziellen trimagischen Zeilen und Spalten mit jeweils nur einer einzigen 64-Bit-Zahl auszudrücken. Mit Hilfe der AND-Funktion kann man nun extrem schnell feststellen, ob zwei Reihen gemeinsame Zahlen enthalten. Zunächst wird die erste Spalte um fünf weitere unabhängige Spalten ergänzt. Dabei kommt ein Backtracking-Verfahren zum Einsatz. Das heißt, man versucht alle möglichen Wege zu beschreiten, gelangt man in eine Sackgasse, so kehrt man zur letzten Wegkreuzung zurück. Auch die Zeilen werden mit einem Backtracking-Verfahren gesucht. Dabei muss nicht nur die Unabhängigkeit der Zeilen beachtet werden, sondern es muss zusätzlich jede Zeile mit jeder Spalte jeweils genau eine Zahl gemeinsam haben.

Zur Umsetzung des Algorithmus verwendete ich die Programmiersprache GB32, die in Deutschland von Gfa-Soft entwickelt wurde, im Wesentlichen von Frank Ostrowski. GB32 ist sehr gut zur Lösung mathematischer Probleme geeignet und zu Unrecht relativ unbekannt. Die erste Fassung des Programms wurde im Mai 2002 fertiggestellt. Einige Stunden Rechenzeit führten nur zu einem Teilerfolg, mehrere beinahe trimagische Quadrate, bei denen 4 Spalten nicht den trimagischen Forderungen entsprachen, wurden gefunden. Am 1. Juni wurde ein beinahe magisches Quadrat gefunden, bei dem alle 12 Zeilen und 10 Spalten trimagisch waren.

Beinahe semi-trimagisches Quadrat (1. Juni 2002)

53

67

74

69

1

3

142

144

76

71

78

92

79

72

64

5

35

7

138

110

140

81

73

66

118

11

9

55

85

68

77

60

90

136

134

27

15

17

13

82

62

57

88

83

63

132

128

130

124

108

122

126

43

56

89

102

19

23

37

21

129

46

36

120

104

29

116

41

25

109

99

16

38

24

34

47

114

18

127

31

98

111

121

107

10

133

95

59

96

33

112

49

86

50

12

135

48

131

75

8

40

39

106

105

137

70

14

97

44

113

139

100

30

42

103

115

45

6

32

101

93

94

125

141

117

65

80

28

4

20

51

52

119

54

84

58

143

22

123

2

87

61

91

26

Christian Boyer schrieb daraufhin: (übersetzt aus dem Englischen)

Außerdem formte Christian Boyer das angesprochene Quadrat so um, dass alle Spalten zumindest bimagisch waren und sich in den Diagonalen die normale magische Summe ergab. Also ein magisches Quadrat, das semi-bimagisch und beinahe trimagisch war.

Semi-bimagische und beinahe trimagische Transformation,
erstellt von Christian Boyer.

53

69

71

78

1

142

3

144

67

74

76

92

79

5

81

73

35

138

7

110

72

64

140

66

118

55

136

134

85

68

77

60

11

9

90

27

15

82

132

128

62

57

88

83

17

13

63

130

124

126

23

37

43

89

56

102

108

122

19

21

129

120

109

99

104

29

116

41

46

36

25

16

38

47

111

121

114

18

127

31

24

34

98

107

10

59

50

12

96

33

112

49

133

95

86

135

48

8

70

14

40

106

39

105

131

75

137

97

44

100

6

32

30

103

42

115

113

139

45

101

93

141

20

51

117

65

80

28

94

125

4

52

119

58

61

91

143

22

123

2

54

84

87

26

Trotz dieser anfänglichen Teilerfolge zeigte sich, dass das Programm nicht effektiv genug arbeitete. Mit dieser Version hätte es vermutlich Jahre gedauert, bis wenigstens ein semi-trimagisches Quadrat erzielt worden wäre.

Einige Ideen für Verbesserungen des Programms spukten mir im Kopf herum und konkretisierten sich in der Nacht zu Samstag, den 8. Juni 2002. Ich stand gegen 6 Uhr auf und arbeitete die neuen Ideen in das vorhandene Programm ein. Gegen 9 Uhr wurden bereits die ersten semi-trimagischen Quadrate der Ordnung 12 gefunden.

Das erste ‚Metall’ war gefunden. Es musste jetzt geprüft werden ob ‚Gold’ darunter ist. Mit einem weiteren Computerprogramm wurde durch Umordnung der Zeilen und Spalten versucht, trimagische Diagonalen zu erzeugen. Nach wenigen Stunden, genau beim 88. semi-trimagischen Quadrat konnte eine trimagische Diagonale konstruiert werden und aus Symmetriegründen war die andere Diagonale automatisch trimagisch. Aber ich vermutete, dass ein Fehler vorlag, der Erfolg hatte sich an diesem Tag zu schnell eingestellt. Deshalb überprüfte ich alle geforderten Eigenschaften zusätzlich mit einem Tabellenkalkulationsprogramm. Jede Zahl von 1 bis 144 wurde genau einmal verwendet, alle Summen waren korrekt.

Das erste trimagische Quadrat der Ordnung 12,
Walter Trump, 8. Juni 2002

1

22

33

41

62

66

79

83

104

112

123

144

9

119

45

115

107

93

52

38

30

100

26

136

75

141

35

48

57

14

131

88

97

110

4

70

74

8

106

49

12

43

102

133

96

39

137

71

140

101

124

42

60

37

108

85

103

21

44

5

122

76

142

86

67

126

19

78

59

3

69

23

55

27

95

135

130

89

56

15

10

50

118

90

132

117

68

91

11

99

46

134

54

77

28

13

73

64

2

121

109

32

113

36

24

143

81

72

58

98

84

116

138

16

129

7

29

61

47

87

80

34

105

6

92

127

18

53

139

40

111

65

51

63

31

20

25

128

17

120

125

114

82

94

Bildschirm angezeigt. Die Suche nach dem kleinsten trimagischen Quadrat wurde erfolgreich abgeschlossen.

Am nächsten Tag verschickte ich das Zahlenquadrat per E-Mail an alle mir bekannten Freunde der magischen Quadrate und bat sie um Überprüfung des Resultats. Einige Antworten können im Anhang nachgelesen werden, alle bestätigten die Richtigkeit des Ergebnisses.

Ich bedanke mich insbesondere bei Christian Boyer (Frankreich), der durch seine Veröffentlichungen und Ideen die Suche eingeleitet hat. Ohne seine eigenen Beiträge und seine kritische Prüfung meiner Berechnungen wäre die Suche nicht erfolgreich gewesen. Mein Dank gilt auch Aale de Winkel (Holland), der mich im Laufe des Jahres immer wieder ermutigt hat, auf dem Gebiet der magischen Quadrate weiter zu arbeiten. Ähnlichen Rückhalt erfuhr ich auch von Harvey Heinz (Kanada) und George Chen (Taiwan).

Walter Trump, Nürnberg, Januar 2003


Reaktionen, per E-Mail, auf die Entdeckung des kleinsten trimagischen Quadrats
(Alle Texte waren ursprünglich in Englisch verfasst und wurden nachträglich übersetzt.)

Christian Boyer (Frankreich, ehemaliger technischer Direktor von Microsoft France, Gründer einer Softwarefirma, Entdecker der ersten tetra- und penta-magischen Quadrate, Webpublisher: www.multimagie.com)

Yung C. Chen, alias George Chen (Taiwan, Begründer von Konstruktionsmethoden, Author kombinatorischer Abhandlungen)

Aale de Winkel (Niederlande, Physiker und Informatiker, publiziert die magic square encyclopedia)

Harvey Heinz (Kanada, Autor des Buches Magic Square Lexicon, betreut die weltweit umfangreichste Website über magische Quadrate.)


Zurück zur Homepage http://www.multimagie.com