das magische 4eck

[fabian ackle]

ich nehme an, viele von euch kennen das magische viereck (3x3 felder) und dort sollen die zahlen 1-9 so eingesetzt werden, dass es senkrecht, waagrecht und diagonal bei addierung dieser zahlen jeweils 15 ergibt,

also zum beispiel:
+---+---+---+
| 2 | 9 | 4 |
+---+---+---+
| 7 | 5 | 3 |
+---+---+---+
| 6 | 1 | 8 |
+---+---+---+
es müsste ungefähr 9^9 verschiedene kombinationen geben, wobei 12 davon richtig sind. ich habe auch ein kleinnes programm gebastelt, welches innerhalb von wenigen minuten alle 12 richtigen kombinationen raus findet.

nun möchte ich aber das ganze mit 5x5 feldern machen, und wollte wissen ob es da einen guten algorithmus dafür gibt... bei 3x3 habe ich es mit jeweils 9 ineinander verschachtelten for- & if-schleifen gemacht. aber das ganze 25 mal zu machen ist mir zu aufwendig und das berechnen würde auch viel zu lange dauern (immerhin 25^25 verschiedene kombinationen!!)
btw. ist es mit 5x5 überhaupt möglich? und wie gross wäre die summe?

greetz

fabian

[DarkTemplar]

Ich glaube die ganze Sache unter dem Begriff "Hexeneinmaleins" mal gehört zu haben. Ist es bei dem gesuchten Allgorythmus für dich im Übrigen egal, ob Zahlen doppelt vorkommen, oder nicht?

Bye,
DarkTemplar

PS: Von so einem Allgorythmus gehört habe ich noch nichts, allerding müßte sich doch mit Sicherheit eine Lösung finden lassen!

[fabian ackle]

das problem ist ja, dass jede zahl nur einmal vorkommen darf...

stimmt es das die summe der zahlen in einer linie bei einem quadrat mit 5x5 felder 65 ergibt?
meine überlegung:
9 felder -> summe 15 FORMEL: (1+2+...+9)/3
25 felder -> summe 65 FORMEL: (1+2+...+25)/5

greetz

fabian

[Bibolorean]

Hab da was gefunden:

das hier (http://www.mathe.tu-freiberg.de/~hebisch/cafe/magisch.html) :D

eine schöne Erklärung, für die, die noch nicht kapiert haben, was er meint.
Aber den Algorithmus würde mich interessieren.


Greetz Bìbòlorean

[Codeq]

ich hätte es jetzt über das finden einer inversen matritze probiert... hmm
warum auch leicht wenns so schön umständlich geht...

zum coden: ich würd aus dem ganzen einen ungeordneten baum machen, dann musste nurnoch die knoten und wege definieren und fertig is das ding... :cool:

[fabian ackle]

@codeq: klingt interessant, aber ich verstehe nicht ganz was du mit ungeordneten bäumen meinst ;)

ich habe hier mal einen lösungsansatz in VB...
fehler sind nicht ausgeschlossen, denn ich bin beim tippen des sources schier verblödet... das geht doch bestimmt auch einfacher?!?

wie lange braucht eigentlich ein durchschnitts-computer um 8.8817841970012523233890533447266e+34 (25^25 ;)) kombinationen durch zu probieren?... dürfte doch extram lange dauern...

greetz

dubious

[Bibolorean]

Wie lange das geht, hängt ganz von der Programmiersprache und natürlich auch vom Computer ab. Aber auch, wie er diese Kombinationen machen muss.

Wenn du hunderte von If Blöcken hast, von denen einige durchgearbeitet werden und andere nicht, kann man nicht gut sagen, wie lange das gehen wird..

Im übrigen hast es in VB gemacht, wird während dem laufen interpretiert, also nochmals lahmer...

Hab da mal ne Berechnung gemacht, in der ich 20 Städte hatte und der PC selber herausfinden musste, welche die kürzeste Route ist. Das wäre ne MOL Rechnung.. weil mir die zu lange ging, habe ich's mit 8 Städten gemacht.. er hat da schon ne Minute gerechnet. Und da das ganze quadratisch zunimmt, denke ich mal, dass es bei 25*25 Felder ne.. Ewigkeit gehen könnte :D

Wie lange genau, fragen wir doch lieber mal die erfahrenen Coder hier *g*

Greetz Bìbòlorean

[Codeq]

also wie lange es dauert hängt zum grossteil vom algorithmus ab!
also wenn du wirklich alles durchprobieren willst, dann brauchst du echt jahre...

es gilt halt ein verfahren zu entwickeln das unsinnige und überflüssige vergleiche gar nicht erst zulässt... desshalb muss man das problem rein mathematisch angehen...

ein ungeordneter Baum hmm.. ich tipp mal die ganze definition ab... oki?
bin im mom ned zuhause.. ;)

und an ner lösung werd ich mich auch ma versuchen ....

[DarkTemplar]

Genau wegen dieser Hohen Anzahl von Kombinationen, die du genannt hattest (25^25) hatte ich zu Anfangs eigentlich auch gefragt, ob du jede Zahl mehrfach verwenden darfst.

Wenn man nämlich berücksichtigt, dass jede Zahl nur einmal benutzt werden darf wäre es prinzipiell möglich die Gesamtheit aller Möglichkeiten auf 25! zu reduzieren. Der Unterschied in der Anzahl der Möglichkeiten is folgender(nur einmal als Ansatz):
25!:
15.511.210.043.330.985.984.000.000
25^25:
88.817.841.970.012.523.233.890.533.447.265.600

Ich werde mir 'mal etwas überlegen, vielleicht fällt mir ja eine günstige Lösung ein!

Bye,
DarkTemplar

[Bibolorean]

Eine Zahl ist fix, das dürfte das ganze noch ein wenig schneller machen:

bei 9 Feldern ist die Summe in einer Linie ja 15.. in der Mitte steht die 5. Daraus schliesse ich, dass es bei 5*5 Feldern (die Summe gibt ja 65) eine 13 in der Mitte hat.

Hmm.. nur noch sone beschleunigung :cool:

Greetz Bìbòlorean

[fabian ackle]

@Codeq: jep, das mit der definition wäre wunderbar, thx

@DarkTemplar: stimmt, hast recht, kleiner fehler meinerseits...
mein VB-programm testet auch "nur" 25! kombinationen (falls der source überhaupt stimmt *g*) aber auch das dauert eine ewigkeit (hab das prog mal einen tag lang laufen lassen mit dem ergebniss dass es am ende verreckt ist...)

@Bibolorean: stimmt! und dank dieser fixen zahl reduziert sich das ganze auf 24! möglichkeiten (also auf lächerliche 620'448'401'733'239'439'360'000 mögliche kombinationen...) :rolleyes:


greetz

fabian

[Codeq]

http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heap.htm
da gibts schonma die definition eines binären baumes..

und hier von graphen
http://www.inf.fh-flensburg.de/lang/algorithmen/grundlagen/graph.htm

und wer sich mathematische sachen ausgedacht hat kann hier ma die genauen definitionen anschaun
http://www.inf.fh-flensburg.de/lang/algorithmen/grundlagen/grund.htm


also ich werde mich nun mal hinsetzen und mir ein 5x5 rechteck erstellen und versuchen dsa ganze graphisch zu lösen, also so in der art, beginne rechts unten mit der höchsten zahl, gehe einen link, 2 nach oben und setze die nächst kleinere zahl, usw... am rand mache auf der rechten seite weiter...

wenn man sowas gefunden hat, dann kann man das anhand eines ungerichteten graphen programmiertechnisch umsetzen, was viiiiiiiiel schneller ist als alles durchrechnen zu lassen vom programm...

so, dann bastel ich mal... :cool:

[DarkTemplar]

Hi!!

Hört sich echt interessant an und der Sortieralgorythmus sieht auch nicht schlecht aus! Werde mich vielleicht auch einmal ransetzen und schauen, was dabei herauskommt.

Mittlerweile ist mir allerdings noch eine andere Idee gekommen. Wenn man nicht von Anfang an das ganze Viereck durchrechnen würde und sich einfach auf die Reihen konzentriert, die in der Summe diesen kennzeichnenden Wert ergeben (bei 5*5 Feldern war das pro 5er Reihe glaub ich 65). Damit ließen sich doch schonmal eine Menge Möglichkeiten einsparen und am Ende müßte man diese Reihen dann nur noch zusammensetzen. Im Endeffekt ist der Exponent der Anzahl von Möglichkeiten, die man am Ende durchtesten muß, laut Rechnung nur halb so groß, was eigentlich einer doch enormen Ersparung von Rechenzeit entspräche.
Ich werde am Besten auch das einmal austesten und wir können dann vergleichen, was am Schnellsten läuft!

Bye,
DarkTemplar

[Messiah_of_Death]

http://www.magic-squares.de

[Tilion]

so meine theorie ist jetzt bestätigt :D

zum 3*3 quadrat gibt es nur 1 lösung in 8 ausführungen.
man nehme eine beliebige lösung und drehe sie 3 mal -> 4 unterschiedliche positionen der zahlen, summe ändert sich jedoch nicht.

um die restlichen 4 lösungen zu bekommen, muss man eine lösung spiegeln (horizontal oder vertikal ist egal, aber nur 1 mal spiegeln) und die dann ebenfalls rotieren -> nochmal 4
also gesammt 8


beim 5*5 wird das wahrscheinlich ähnlich sein. wenn man eine lösung hat, kann man durch etwas umformung an die anderen kommen. erstmal die 8, die sich wie oben zusammensetzen.


2. ich glaube aber, dass es noch 8 weitere lösungen geben kann, indem man teilquadrate um 180° rotiert (nicht spiegeln)


+---+---+---+---+---+
| 1 | 1 | 2 | 3 | 3 |
+---+---+---+---+---+
| 1 | 1 | 2 | 3 | 3 |
+---+---+---+---+---+
| 8 | 8 | | 4 | 4 |
+---+---+---+---+---+
| 7 | 7 | 6 | 5 | 5 |
+---+---+---+---+---+
| 7 | 7 | 6 | 5 | 5 |
+---+---+---+---+---+


zusammengehörige zahlen bilden ein teilquadraht. müssen alle gleich gedreht werden...


das alles ist aber ungetestet in meinem kopf entstanden, bin also nicht 100% sicher bei dem 2. :D


wenn das wirklich so hinhaut, müsste dein algorythmuss ja nur eine lösung finden... und dann die anderen herleiten

[fabian ackle]

aber das problem ist das ich es bis jetzt noch nicht mal geschafft habe einen algorithmus zu basteln welcher auf diese eine benötigte lösung kommt ;)

greetz

fabian

[gsascha]

hat jemand schon eine lösung fürs 3*3 quadrat? kann er die bitte mal aufschreiben, vielleicht komm ich dann leichter drauf

[gsascha]

hm, ich hab jez schon mal einen denkansatz:

man schreibt sich mal alle lösungen pro zahl auf, aber ohne die hinteren 2 zahlen umzudrehen und ohne doppelten zaheln

also:

1 5 9
1 6 8

2 4 9
2 5 8
2 5 7

3 4 8
3 5 7

4 2 9
4 3 8
4 5 6

5 1 9
5 2 8
5 3 7
5 4 6

6 1 8
6 2 7
6 4 5

7 2 6
7 3 5

8 1 6
8 2 5
8 3 4

9 1 5
9 2 4

daraus folgt, das 2, 4, 6 und 8 auf jeden fall an einer ecke sind (3 möglichkeiten, nur an der ecke gibts so viele. 5 hat 4 möglichkeiten => mitte!

der rest hat nur 2 möglichkeiten => irgendwo in die mitte am rand (wenn ihr wissts, was ich mein!)

also zerst weiß man nur (aus den möglichkeiten herausgesehen)

2 * 4
* 5 *
6 * 8

jetzt wird wieder aus den möglichkeiten herausgesehen, zwischen welchen zahlen der 1er z.B. vorkommt, und schon kann man ihn richtig einsetzen.
so kommt man auf:

2 4 9
7 5 3
6 1 8

das noch spiegeln und drehen, und man kommt auf den rest.

das ist glaub ich besser, als alles irgendwie durchzuprobieren!

alerdings, wie das jetzt bei 5 zahlen geht, weiß ich nicht! welche summe muss denn da rauskommen? und elche summe bei 7 bzw 9 usw?

[belze]

hrhr, für das magische 4-Eck gabs mal (bitte NICHT lachen :D) in der Mickey-Mouse eine ganz einfache Anleitung wie man ein solches mit bis zu n-Kästchen erstellt...
Da wurden einfach die Seiten Pyramidenartig verlängert und dann irgendwie ausgefüllt und die Zahlen aus der Verlängerung rübergeholt..vielleicht finde ich das wieder, war aber an sich auch alles ganz logisch, aber als ich das gelesen habe war ich < 10 Jahre alt, deswegen weiß ich das nicht mehr genau.

[fabian ackle]

hehe, was es in der MickeyMouse nicht alles gibt, erstaunlich :)
Wäre toll wenn du es finden würdest, würde mich interessieren :)

greetz

fabian

[Jan Krüger]

aloha,
hier auch von mir ein paar wilde vermutungen über regelmäßigkeiten in magischen quadraten.

bei magischen quadraten mit einer geraden zahl n als ordnung:
- in jeder zeile/spalte ist die hälfte der vorkommenden zahlen größer als (n²/2) (algorithmus: wenn in einer zeile diese bedingung nicht erfüllt ist, kann die momentane rekursionsebene sofort abgebrochen werden)
- in jeder zeile/spalte ist die hälfte der vorkommenden zahlen gerade, die andere hälfte somit ungerade

bei magischen quadraten mit einer ungeraden zahl n als ordnung:
- jedes teilquadrat des magischen quadrats, das die gleiche zahl als mitte hat (bspw. bei n=5 bei entfernung der ersten und letzten zeile und spalte vom ursprünglichen quadrat), ist auch ein magisches quadrat, wenn auch kein normales. die summe t für ein teilquadrat mit der kantenlänge m kann folgendermaßen berechnet werden: t = s / n * m, wobei sich die summe s jeder reihe des großen quadrates wie folgt berechnet: s = (n² + 1) * n / 2

-----

somit werden magische quadrate mit der ordnung 5 recht einfach zu berechnen, weil man zunächst einfach mit einem quadrat der ordnung 3 anfängt (mit der 13 in der mitte), dann alle möglichen kombinationen irgendwo speichert (summe aller felder des 3er-quadrats: 39) und dann in alle richtungen um eine reihe erweitert und hier alle möglichkeiten, aufzufüllen, durchtestet.

auch das ließe sich dann noch optimieren (wenn die genannten regeln tatsächlich stimmen, könnte ich besagte optimierung sogar beweisen), aber da gehe ich evtl. später mal drauf ein, jetzt hab ich erst mal genug nachgedacht.

[Ryu]

ähm nur so ne frage, aber bringen eure überlegungen eigentlich was für ein normales programm?? :p

[fabian ackle]

was verstehst du unter einem "normalem programm"?

das magische 4eck kannst du in anwendungsprogrammen kaum verwenden, das ist richtig, aber wir befinden uns hier im ALGORITHMUS-Forum, hier geht es darum probleme mit Coden zu lösen... Ich war dabei ein so ein 4eck 'manuell' zu lösen, eines mit 3*3 hab ich gerade noch hinbekommen, da ich es aber beim 5*5er vergeblich versucht hatte wollte ich halt den pc damit beauftragen... ;)

greetz

fabian

[Ryu]

jo stimmt und außerdem sin ferien und ich hab keinen ferialjob also hab ich den ganzen tag zeit zum coden :D

meine überlegung:
also bei nem 3x3 felder quadrat is die summe einer reihe 15, und ich hab jetzt auch versucht ne formel für die 15 zu finden, die immer funzt, und ich bin auf folgende formel gekommen:
x²:(6:9+1)
also x is bei nem 3x3 quadrat die zahl 3, bei nem 4x4 quadrat die zahl 4 etc.
kann das stimmen?

[gsascha]

ja, aber was nützt es einem? bei einem 4*4 quadrat muss die summe dann ja größer sein als 15, weil ja 4 zahlen in einer reihe sind, oder nicht?

achja, ich habe einen ferialjob, hab aber trotzdem den ganzen tag zeit nachzudenken :D . ich müsste zwar ur viel programmieren, aber ich verschiebs immer...