Magische Quadrate, Teil I
The Update
Gesucht wird ein magisches 4*4-Quadrat (es dürfen nur die Zahlen von 1 bis 16 verwendet werden, und die auch nur jeweils einmal) bei dem jede Zeile und jede Spalte je 34 ergeben. Auch die beiden Diagonalen ergeben 34, wie auch das 2*2 Quadrat, welches sich in der Mitte des 4*4 Quadrates befindet. Zusätzlich ergeben die vier Teilquadrate in dem 4*4 Quadrat auch 34. Auch die vier Ecken des 4*4 Quadrats ergeben 34.
Das klingt ja im Prinzip recht einfach. 4*4er Arrays mit den Zahlen von 1 bis 16, das wäre ein 4*4 Pixel großer EGA-Bildschirm, keine große Aufgabe für heutige Computer. Spannend wird es erst durch die Bedingungen. Man hat 16 Felder und 16 Zahlen, die Anzahl möglicher Kombinationen liegt somit bei 16! = 2,1 * 10^13. Das klingt schon nicht mehr ganz so einfach...
Selbst wenn man die theoretische Möglichkeit nimmt, daß man keine Rechenzeit braucht, um die Quadrate zu erhalten, benötigt man pro Quadrat noch 14 SIMD-Additionen für die Prüfung, was, bei der theoretischen Annahme von 1 Taktzyklus pro Addition und 1 GHz CPU-Takt rund 81 Stunden dauern würde. In der Praxis kommt da noch eine Menge drauf, schließlich wollen die 14 Additionen ausgewertet und die Quadrate überhaupt erst einmal generiert werden. Also gilt es, den Algorithmus ein wenig zu verbessern.
Eine Lösung gibt's hier.
The Update