Mit KI gelöst: 18 Jahre altes mathematisches Rätsel entschlüsselt

Kategorien: Datenschutz und Künstliche Intelligenz

Mit einem KI-System ist es dem Autor gelungen, ein mathematisches Rätsel zu lösen, das 18 Jahre lang ungelöst war. So konnten sogenannte Magische Sechsecke mit Standard-Hardware in einer bisher nicht bekannten Weise gelöst werden. Die dafür eingesetzte KI half beim Entwickeln des Lösungsprogramms. Der Rest war geringe Eigenintelligenz eines Nichtmathematikers.

Worum geht es?

Es wird gezeigt, dass mit Hilfe von KI ein bisher ungelöstes mathematisches (NP-schweres) Problem von einem Informatiker mit eher unterentwickelten Mathematikkenntnissen gelöst werden kann. NP-schwer sind die schwierigsten Probleme, weil sie durch reines Ausprobieren meist nicht in endlicher Zeit gelöst werden können, und weil es keinen Algorithmus gibt, der garantiert die Lösung liefert.

KI wurde hier als Mittel zum Zweck eingesetzt. Zusätzlich war menschliches Zutun erforderlich. Ohne KI wäre die gezeigte Lösung allerdings nie zustande gekommen.

18 Jahre lang gab es keine Lösung für das Problem, jetzt ist sie da. Mit KI.

Nebenbei sei erwähnt, dass die Lösung hier deutlich schwieriger zu finden war als die bisher beste Lösung, die bereits 18 Jahre alt ist! Das Ursprungsproblem geht auf das Jahr 1887 zurück, in dem der Stralsunder Stadtbaumeister Ernst von Haselberg seine Faszination für Magische Hexagone entdeckte. Später machte Martin Gardner das Problem weltweit bekannt.

Einleitung

KI kann enorm viel leisten, wenn man sie richtig einsetzt. Das folgende konkrete Fallbeispiel zeigt mit einem realen, für die Mathematik relevanten Ergebnis, wie KI die Arbeit erheblich erleichtern kann. Für das genannte Problem wurde die Arbeit nicht nur erleichtert, sondern die Lösung überhaupt erst ermöglicht. Ohne KI gäbe es alle hier vorgestellten Lösungen (ab N = 7) nicht.

Datenschutz, Urheberrecht, Geschäftsgeheimnisse

Auch wenn keine personenbezogenen Daten verarbeitet wurden: Die verwendete Lösung lief auf einer eigenen Infrastruktur. Immerhin geht es auch um so etwas wie ein „Geschäftsgeheimnis“. Der Lösungsweg für die magischen Hexagone scheint in dieser Form nicht bekannt zu sein.

Wer aus Verlegenheit ein Wikipedia-Bild auf seiner Webseite einbinden möchte, sollte lieber zehnmal darüber nachdenken. Die Grafik im folgenden Abschnitt wurde selbst erstellt. Wer hingegen ein vergleichbares Hexagon (mit anderer Lösung) von der deutschen Wikipedia-Seite nehmen möchte, der wird an den rechtlich notwendigen Urheberangaben für die Lizenz CC-BY-SA-3.0 scheitern. So wie der Autor vor 7 Jahren. Damals hatte ein selbsternannter Plagiatsjäger (Fotograf) nach falscher Verwendung der von ihm auf Wikipedia „frei“ zur Verfügung gestellten Bildern gesucht. In dem Wissen, dass die Urheberangabe nur von intimen Kennern richtig befolgt werden kann. Leider hatte der Plagiatsjäger einige Datenschutzprobleme auf seinen Webseiten und Schwierigkeiten mit der Anbieterkennung. So kam es, dass er seine Kostennote zurückzog, als er darauf aufmerksam gemacht wurde…

Magische Sechsecke

Es geht um magische Hexagone. Was sind magische Hexagone?

Magische Hexagone sind Sechsecke mit bestimmten Eigenschaften und haben eine Ordnungszahl, die N genannt wird. Diese Ordnungszahl sagt, aus wie vielen Waben (Zellen) jede Außenkante des Sechseckes besteht. Hier ein Beispiel:

Dieses magische Hexagon der Ordnung N = 3 hat 3 Waben in jeder Außenkante. Die Anzahl der Waben beträgt 19 und folgt der Formel 3N²-3N+1. Insgesamt besteht dieses Hexagon aus 15 Reihen. Diese 15 Reihen sind:

• 5 horizontale Reihen
• 2 Hauptdiagonalen
• 4 Nebendiagonalen außen
• 4 Nebendiagonalen innen
• = 15 Reihen

Nun kommt das Magische: Ein Magisches Hexagon (der Ordnung 3) ist nur magisch, wenn alle 15 Reihen dieselbe Summe aufweisen und alle Zahlen in den Waben ganzzahlig sind und jede dieser Zahlen aus einer aufeinanderfolgenden Reihe entnommen wurde und jede Zahl genau einmal verwendet wurde. Die Anzahl der Reihen ist zugleich die Anzahl der (von einander abhängigen) Gleichungen, die gleichzeitig gelöst werden muss. Für ein Magisches Sechseck gibt es immer mehrere Lösungen.

Bildlich gesprochen, sehen die 15 Reihen im kleinsten sinnvollen Magischen Hexagon so aus (die Ordnung 1 lassen wir weg, weil das zugehörige Hexagon aus genau einer Wabe besteht; Ordnung 2 ist nicht möglich):

Zu sehen sind 5 diagonale Reihen mit roter Markierung, 5 diagonale Reihen mit grüner Markierung und 5 horizontale Reihen mit blauer Markierung Macht 15 Reihen. Jede der 15 Reihen muss also dieselbe Summe über alle Waben der jeweiligen Reihe haben. Für kleinere Ordnungen verwendet man gerne positive Zahlen, weil sie anschaulicher sind. Im Beispiel oben und auch in den folgenden Beispielen und neu hervorgebrachten Ergebnissen wurden allerdings Zahlen von -X bis X verwendet. Das X entspricht bei N = 3 dem Wertebereich von -9 bis 9. Diesen Bereich kann man ermitteln durch: (Anzahl der Waben – 1) / 2, also (19 – 1)/2 = 9.

Die Faszination für diese magischen Sechsecke begeistert viele. So wurde beispielsweise im Jahr 2022 ein Genetischer Algorithmus entwickelt, um Mini-Hexagone der Ordnung N = 3 zu lösen. Dieses Mini-Hexagon hat 19 Felder und 15 Reihen. Wir werden ein Hexagon lösen, welches die Ordnung N = 9 und 217 Felder sowie 51 Reihen hat! Die Komplexität steigt also mit höheren Ordnungen erheblich an.

Für den oben genannten symmetrischen Wertebereich (-X bis +X) ergibt sich als magische Summe M immer die 0. Diese Magische Konstante ist für andere Wabenbelegungen nicht einfach ermittelbar. Es ist zudem nicht klar, für welche Zahlenbereiche ein magisches Sechseck der Ordnung N jeweils überhaupt lösbar ist. Für N = 5 gibt es beispielsweise wohl keine Lösung mit Zahlen größer 15 als kleinste Startzahl. Daher ist M = 0 sehr charmant, weil sie erstens berechenbar ist und es zweitens so aussieht, als könnte diese Summe für jede Ordnung N möglich sein.

Lösungen

Je größer ein Sechseck wird, desto schwieriger ist es, dessen magische Lösung zu finden. Das größte bisher bekannte magische Sechseck ist nach Recherche des Autors eines mit der Kantenlänge N = 8 (siehe auch Wikipedia). Falls jemand größere Sechsecke gefunden oder gesehen hat, bittet der Autor um eine Information.

Für Magische Hexagone der Kantenlänge 3 bis 6 ist die Lösung durch brutales Ausprobieren recht schnell gefunden ("Brute Force"). Ab N = 7 wird es spannend.

Für Magische Hexagone der Ordnung 9 (Länge jeder Außenkante) gab es bisher keine Lösung. Seit dem 10.09.2024 gibt es sie.

Quelle: Klaus Meffert und eigene Recherche.

Auf Wikipedia ist genau eine Lösung für N = 7 genannt. Die Lösung verwendet die 128 Zahlen von 2 bis 127 und hat die magische Summe von 365. Die Lösung wurde im Jahr 2006 entdeckt.

Neue Lösung für Magisches Hexagon der Ordnung 7

Um keine Probleme wegen falscher Urheberangabe zu machen, geben wir hier eine selbst gefunden Lösung an:

Für die Ordnung 8 ist auf Wikipedia ebenfalls genau eine Lösung genannt. Diese wurde ebenfalls im Jahr 2006 (!) von Louis Hoelbling entdeckt.

Neue Lösung für Magisches Hexagon N = 8

Auch für N = 8 hat der Autor eigene Lösungen mit einem selbst entwickelten Programm gefunden, das unter anderem mit KI entstanden ist. Diese Lösung ist anders als die auf Wikipedia und lautet:

Die auf Wikipedia verzeichnete Lösung von Louis Hoelbling ist deshalb anders, weil nicht nur die Zahlenbelegung anders ist, sondern weil auch keine Symmetrie vorherrscht. Symmetrisch etwa wären Lösungen, wenn sie durch Drehen, Spiegeln oder auch über Umkehr der Vorzeichen ineinander überführt werden könnten.

Die Farbintensität in den abgebildeten Hexagonen deutet die Anzahl der Waben an, die durch jeweils eine Wabe beeinflusst werden. Offensichtlich beeinflusst das zentrale Feld im Hexagon am meisten anderen Felder. Daher ist es am dunkelsten dargestellt. Die Außenfelder beeinflussen jeweils am wenigsten andere Felder. Mehr dazu weiter unten.

Erste Lösung für Magisches Hexagon der Ordnung 9

Für N = 9 gibt es nach Recherche des Autors bisher keine Lösung für Magische Hexagone. Am 10.09.2024 hat der Autor diese Lösung gefunden. Die Lösung lautet:

Die Lösung wurde vom Lösungssystem des Autors gefunden, das mit Hilfe von KI und eigener Entwicklung entstand. Die Mail mit der Lösung, die vom Lösungssystem automatisch verschickt wird, wurde um 10.09.2024 um 00:08 Uhr verschickt.

Die Lösungsbedingungen bestehen aus 51 Gleichungen und 217 Variablen. Eine Variable ist hier die Zahl auf einer Wabe im Sechseck. Jede Variable ist Teil von 3 der 217 Gleichungen (weil jede Variable einer Wabe entspricht und jede Wabe genau Teil von 3 Reihen im Hexagon ist). Klingt recht komplex und ist es auch. Mit bloßem Ausprobieren kommt man hier nicht wirklich zum Ziel.

Auch in der Abbildung des Magischen Hexagons der Ordnung 9 zeigt die Farbintensität jeder Wabe an, wie viele andere Waben beeinflusst werden. Beeinflussung heißt, dass eine Änderung des Zahlenwertes auf der Wabe Auswirkungen auf die anderen Waben hat, die durch die Zahlenänderung beeinflusst werden. Konkret sieht die Beeinflussung für Magische Sechsecke der Ordnung 9 immer so aus:

Das Mittelfeld beeinflusst also 48 andere Waben. Die Eckwaben hingegen beeinflussen jeweils nur 32 andere Waben. Jede Wabe ist Teil von genau drei Reihen. Das Mittelfeld liegt in drei gleich langen Reihen, die jeweils 17 Waben lang sind. Die 17 ergibt sich aus 2N-1 (2*9-1). Weil das Mittelfeld selbst nicht mitgezählt wird bei der Beeinflussung anderer