Wenn die Steine eines Boss-Puzzles aufeinanderfolgende Zahlen tragen, dann kann man diese auch in einer anderen Reihenfolge anordnen als der Größe nach. Immer wieder taucht die Fragestellung auf, die Zahlen als magisches Quadrat anzuordnen. Sie erinnern sich sicher: Bei einem Magischen Quadrat müssen die folgenden Summen alle gleich sein: Die Summen jeder Zeile, ebenso die Summen jeder Spalte und die Summen der beiden Diagonalen.
Hier eine Lösung für das Boss-Puzzle der Größe 3x3 (im Leerfeld denke man sich die Ziffer 9):
Es ist sinnvoll, einen Moment nachzudenken, statt einfach loszuprobieren. Wie groß muss die Zeilensumme sein? Da wir die Gesamtsumme aller Steine kennen, müssen wie diese durch die Anzahl der Zeilen teilen, um die geforderte Zeilensumme zu erhalten. Ein zweiter nützlicher Tipp: Das Magische Quadrat entsteht nicht so einfach im Boss-Puzzle. Wenn Sie beispielsweise beim 4x4-Boss-Puzzle die Zeilensumme für die erste Zeile und zweite Zeile hinbekommen, dann muss sich das Puzzle nicht unbedingt komplett lösen lassen. Und ein dritter Tipp: Es gab doch unlösbare Aufgaben für das Boss-Puzzle. Wie stellen wir sicher, dass ein vorgegebenes Magisches Quadrat auch eine lösbare Aufgabe für das Boss-Puzzle ist?
Schwierigkeit: Wenn wir das gewöhnliche Boss-Puzzle lösen können, dann wird es mit dem Magischen Quadrat nur ein klein wenig komplizierter: Wir müssen uns nur ein magisches Quadrat passender Größe beschaffen und dieses als Vorlage für die Reihenfolge der Steine verwenden. Schwierig nur für Anfänger.
Boss-Puzzle der Größe 3x3
Das Foto oben enthält ein magisches Quadrat der Größe 3x3, wenn wir uns in dem leeren Feld die nächste Zahl 9 vorstellen. Die Summen jeder Zeile, Spalte oder Diagonale betragen (1 + 2 + ... + 8 + 9) / 3 = 15.
Damit dies eine lösbare Aufgabe für das Boss-Puzzle ist, muss es sich um eine sogenannte gerade Permutation der natürlichen Reihenfolge handeln. Um das festzustellen, können wir relativ einfach die Anzahl der Fehlstellungen bestimmen: Wir schreiben die Zahlen aus dem Quadrat in eine lineare Reihe (also 6,1,8,7,5,3,2,9,4) und bestimmen die Anzahl der Paare, bei denen eine größere Zahl vor einer kleineren steht. Dies sind die Fehlstellungen. Im Beispiel haben wir folgende Fehlstellungen:
6 steht vor 1, 5, 3, 2, 4 (5 Fehlstellungen)
8 steht vor 7, 5, 3, 2, 4 (5 Fehlstellungen)
7 steht vor 5, 3, 2, 4 (4 Fehlstellung)
5 steht vor 3, 2, 4 (3 Fehlstellungen)
3 steht vor 2 (1 Fehlstellungen)
9 steht vor 4 (1 Fehlstellung)
Dies ergibt insgesamt 19 Fehlstellungen, also eine ungerade Zahl. Da außerdem das Leerfeld (hier mit der Ziffer 9) von der Ausgangsposition rechts unten um einen Schritt wandert (eine ungerade Anzahl von Schritten), ergibt sich insgesamt eine gerade Permutation und eine lösbare Aufgabe.
Vorsicht: Es gibt auch Magische Quadrate mit ungerader Permutation, die dann unlösbare Aufgaben für das Boss-Puzzle darstellen. Eine davon ist die folgende, bei der das obige Magische Quadrat vertikal gespiegelt wurde:
8 1 6
3 5 7
4 9 2
Hier ist die Anzahl der Fehlstellungen um eins kleiner und die Aufgabe nicht lösbar.
Boss-Puzzle der Größe 4x4
Boss-Puzzle der Größe 5x5: Sixty-5
Wie finden wir Magische Quadrate?
- Wir können uns mit Papier und Stift hinsetzen und als erste Knobelaufgabe ein Magisches Quadrat passender Größe ausknobeln. Je größer das Magische Quadrat werden soll, desto schwieriger
- Wir können in Büchern oder im Internet nach fertigen Magischen Quadraten suchen oder ein Programm, welches uns Magische Quadrate ausrechnet. Ein Beispiel ist der Generator für Magische Quadrate von H.B. Meyer [1], der mittels Backtracking. Hier kann man auch einzelne Zahlen vorgeben.
- Oder wir programmieren uns einen einfachen Generator selber. Für Magische Quadrate bietet sich wieder ein SMT-Solver an.
Keine Kommentare:
Kommentar veröffentlichen