Magische Quadrate – gar nicht mehr so magisch

Seit ich kürzlich auf meinem Smartphone diverse Messenger installiert habe, bekomme ich von Freunden und der Familie immer wieder Bilder und Videos geschickt, auf denen mathematische Spielereien zu sehen sind.

Im Video wird anschließend eine Methode gezeigt, mit der man systematisch aus seinem eigenen Geburtstag ebenfalls ein solches magisches Quadrat entwickeln kann. Dies ist durch einfache Addition und Subtraktion der vorgegebenen ersten Zeile (das eigene Geburtsdatum) möglich. Einziges Problem dabei: Wenn eine der Zahlen zu klein ist, funktioniert die Methode nicht mehr, da die Zahlen dann in den negativen Bereich rutschen – eine Eigenschaft, die man bei magischen Quadraten vermeiden sollte.

Was macht also der Mathematiker von heute? Er greift zu Constraint Programming (CP), in diesem Fall der CP-Solver des CPLEX Optimization Studios.

Die einzelnen Felder sind unsere Variablen, nach Vorgabe oben als positive Integerwerte definiert. Alle Summen, die nun übereinstimmen sollen, werden als Entscheidungsausdrücke definiert, so also die Summe aller Zeilen, aller Spalten, aller Diagonalen etc. Anschließend wird im subject to-Block, also in dem Bereich des Modells, in dem die Bedingungen definiert werden, angegeben, dass diese Summen alle übereinstimmen sollen.

Den Rest übernimmt der Solver: Man muss nun keine eigenen Algorithmen mehr entwickeln, um auch in solchen Spezialfällen zu einer Lösung zu gelangen. Der Computer berechnet das völlig eigenständig. In meinem Testbeispiel präsentierte mir der Solver eine Lösung nach weniger als einer Zehntelsekunde.

Warum nun Constraint Programming und nicht lineare Optimierung? Weil wir hierdurch (sofern es dann noch eine Lösung gibt) eine weitere Eigenschaft mit hinzunehmen können: Der CP-Ansatz erlaubt uns eine weitere Bedingung einzubauen, nämlich, dass alle Zahlen unterschiedlich sein sollen. Dies mit linearer Optimierung zu modellieren wäre relativ aufwändig, mit dem CP-Ansatz reicht dafür eine weitere Zeile.

Haben wir Ihr Interesse geweckt? Wollen Sie weitere Informationen dazu, wie Sie mathematische Optimierung für Ihr Unternehmen gewinnbringend einsetzen können? Sprechen Sie uns gerne an, wir freuen uns auf das Gespräch mit Ihnen!