Magische Quadrate, Lösung I
The Update
Zuerst stellt sich die Frage, wie man die Quadrate überhaupt generiert, da ja jede Zahl nur ein mal vorkommen darf und man auch keine doppelten Quadrate haben möchte. Da Vergleiche immer Zeit kosten, fällt auch die Möglichkeit weg, einfach jedes Feld von 1 bis 16 durchzugehen und dann nur die Quadrate zu prüfen, bei denen jede Zahl nur ein mal vorkommt. Dieser Weg zeigt aber schon in die richtige Richtung: Man belegt das erste Feld mit einer FOR-Schleife von 1 bis 16. Da gibt's noch nichts dran zu rütteln, es ist das erste, also existiert die Zahl auch nirgendwo anders. Das nächste Feld füllt man mit der nächsten Schleife.
Erster Versuch: Man schreibt eine Eins rein. Das gibt natürlich nichts, da die Eins schon im Feld 1 steht, also erhöht man den Wert um eins und schaut noch mal nach, ob's den Wert schon gibt. Wenn nicht, geht's mit Feld Nr. 3 weiter, das Prinzip bleibt das gleiche. Die FOR-Schleife bestimmt die Zahl, wenn's sie schon gibt, erhöht man sie so lange, bis man eine noch nicht verwendete findet. Aber Vorsicht: Zum einen darf man ja nicht über die 16 gehen, zum anderen muß man beachten, daß man nach der Erhöhung wieder von vorne mit den Vergleichen anfängt, sonst scheitert man spätestens, wenn Feld 1 eine Zwei und Feld 2 eine Eins enthält, da dann Feld 3 auch eine Zwei bekäme.
Somit hätte man schon mal alle Quadrate, die aus den Zahlen 1 bis 16 bestehen, generiert. Bei diesem Vorgang fällt es nun leicht, die Rechenleistung abzusenken: Bereits nach den ersten vier Zahlen kann man entscheiden, ob es sich lohnt, weiter zu rechnen, da ja die Zeile schon 34 ergeben muß. Nach dem sechsten Feld erfolgt der nächste Test, das linke obere 2*2-Quadrat. Nach acht Zahlen kann man die zweite Reihe und das zweite Quadrat testen, usw. So werden unmögliche Kombinationen recht schnell verworfen, so daß sich die Laufzeit schon auf angenehme Werte reduziert. Nach wenigen Minuten erhält man auf einem c366/vc++ schon eine Liste mit allen 384 verfügbaren Quadraten.
Der Quellcode ist in den Sprachen C++ und Basic im Bonusverzeichnis dieses WildMag's zu finden.
Womit sich nur noch folgende Frage stellt: Warum ausgerechnet 34? Die Summe der Zahlen von 1 bis 16 ergibt 136, welches durch vier geteilt (die Prüfungen beziehen sich jeweils auf ein Viertel der 16 Felder) 34 ergibt. Die Formel dazu lautet (x^3 + x) / 2, wobei x die Seitenlänge des Quadrates ist.
The Update
mados