Magisches Quadrat |
24.08.2017, 21:28 | Tangens | Auf diesen Beitrag antworten » | |||||||
Magisches Quadrat Ich stehe gerade an einem kleinen mathematischen Problem und suche eine Formel, die mir helfen kann, ich hoffe, dass ihr mir hier weiter helfen könnt. Es geht um folgendes Szenario: Quersummenberechnung mit Unbekannten Mein Fall, ich habe Folgendes vorgegeben: [attach]45136[/attach] Wie auf dem Bild zu sehen, habe ich 3 mal 3 Felder in denen zwei Zahlen vorgegeben sind, die 3 und die 2. Ich suche nun eine Formel mit der ich sämtliche X Werte (Unbekannten) berechnen kann, sodass am Ende sämtliche "?" dieselbe Quersumme ergeben. Ein Computerprogramm habe ich schon geschrieben, welches mir eine Lösung ausgibt. Leider dauert die Berechnung einer solchen mathematischen Aufgabe, doch eine kleine Weile. Wäre es möglich eine Formel zu entwickeln, mit der man die Unbekannten ermittelt? Grüße von Tangens |
|||||||||
24.08.2017, 21:42 | xb | Auf diesen Beitrag antworten » | |||||||
Ich vermute mal,dass alles natürliche Zahlen sein sollen Dann wird es glaube ich nicht so einfach mit der Formel |
|||||||||
25.08.2017, 07:54 | xb | Auf diesen Beitrag antworten » | |||||||
Man findet im Internet jede Menge zu dem Thema Auch Möglichkeiten zur Berechnung.Da sind dann die Diagonalen mit dabei Die Frage ist,ob es immer eine Lösung gibt,wenn man 2 Zahlen irgendwo einsetzt und darauf verzichtet,dass es auf den Diagonalen auch die Quersumme gibt |
|||||||||
25.08.2017, 08:33 | Tangens | Auf diesen Beitrag antworten » | |||||||
Wie gesagt, ich habe mir ein Programm geschrieben, wo man Zahlen vorgibt. Zu einer Lösung kommt man schon, es dauert nur mit der Berechnung 1 - 2 Minuten. Ich dachte mit einer Formel komme ich hier besser. @xb - Nach was müsste ich denn da suchen? |
|||||||||
25.08.2017, 08:43 | IfindU | Auf diesen Beitrag antworten » | |||||||
Man kann es als lineares Gleichungssytem mit 6 Gleichungen auffassen. Man kann dann die Gleichungen voneinander subtrahieren, s.d. die Quersumme verschwindet und man nur noch 5 Gleichungen zu betrachten hat: Solange das Quadrat selbst nur natürliche Zahlen beinhaltet, so wird die Quersumme natürlich sein. Ab dann wird es schwierig die Natürlichkeit der Lösung zu Gewährleisten. Man kann es dennoch als Unterbestimmtes Gleichungssystem auffassen und bisschen umstellen. Wenn man nur Ganzzahligkeit will, reicht alle Nenner "rauszumultiplizieren", und dann beliebige Zahlen einzusetzen. Für Natürlichkeit kommt man wohl nicht über Fallunterscheidungen und ähnliches herum. |
|||||||||
25.08.2017, 09:27 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Es sieht so aus, als hast du ein paar Rahmendaten bisher nicht genannt. Dass es nur um natürliche Zahlen geht, davon gehen wir nun wohl alle aus. Aber das allein reicht ja wohl auch nicht: Sind es womöglich nur Ziffern, d.h. einstellige Zahlen 0..9, die du für die X zulässt? Kann aber irgendwie auch nicht sein, denn dann müsste jedes einigermaßen effiziente Programm bei diesem winzigen 3x3-Tableau eher im Millisekundenbereich fertig sein. |
|||||||||
Anzeige | |||||||||
|
|||||||||
25.08.2017, 09:53 | Tangens | Auf diesen Beitrag antworten » | |||||||
Ja, stimmt, es sollen rein natürliche Zahlen sein. X sind die gesuchten Zahlen. Der Zahlenraum wäre zwischen 0 und 99. Das hatte ich vergessen anzugeben. Zur Berechnung des Programms - ich habe es bisher so geschrieben, dass er für jedes X eine Zufallszahl erzeugt wird und am Ende kontrolliert wird, ob alle Quersummen gleich sind.Falls dies nicht der Fall ist, werden wieder Zufallszahlen erzeugt. Da hier sehr viel Zufall rein spielt, dauert es schon ein weilchen. Eine alternative ist mir bisher nicht eingefallen, deswegen behellige ich euch gerade, ob es eventuell eine Formel gibt. Das Programm lief auch mit 5 x 5 Zahlen, also insgesamt 25 Zahlen, davon waren 2 vorgegeben, alles andere Zufallszahlen. |
|||||||||
25.08.2017, 10:03 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Ok, das ist allerdings ziemlich ineffizient, außerdem kannst du dir damit nie sicher sein, alle Lösungen erwischt zu haben - eher kommen mal wieder welche "doppelt" vor. Warum machst du es nicht so:
Bleibt noch das Quadrat links unten: Durch Festlegung eines Wertes, z.B. , lassen sich die anderen drei unmittelbar und ohne Probieren ausrechnen. Auch hier gilt: Verlässt einer der Werte den zulässigen Bereich -> Fall wegwerfen. Insgesamt also 1000000 Fälle mit ein paar simplen Grundrechenoperationen sowie Vergleichen, bei meinem kurzen Testprogramm weniger als eine Sekunde Rechenzeit (inklusive Ausgabe aller 357159 Lösungen). |
|||||||||
25.08.2017, 10:37 | Tangens | Auf diesen Beitrag antworten » | |||||||
Na klar, stimmt, warum bin ich nicht gleich drauf gekommen, danke dir! |
|||||||||
25.08.2017, 20:51 | xb | Auf diesen Beitrag antworten » | |||||||
Kann das sein? 357159 Lösungen bei 100 Zahlen Wie sind da die Quersummen verteilt? |
|||||||||
25.08.2017, 21:07 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
|
|||||||||
25.08.2017, 21:37 | xb | Auf diesen Beitrag antworten » | |||||||
Nicht schlecht Gibt´s auch noch einen Erwartungswert |
|||||||||
25.08.2017, 22:19 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Hmm, nein: |
|||||||||
25.08.2017, 22:32 | xb | Auf diesen Beitrag antworten » | |||||||
Irgendwie magisch |
|||||||||
30.08.2017, 09:24 | Tangens | Auf diesen Beitrag antworten » | |||||||
Da bin ich noch einmal! Ich habe noch einmal weiter getüftelt, bei meinem 3 x 3 Feld, soll die Lösung berechnet, werden, jedoch soll jede Zahl nur einmal vorkommen, ähnlich wie bei Sudoku. Das Ganze funktioniert ohne Probleme bei einem 3 x 3, 4 x 4 und auch 5 x 5 Feld. Nun stehe ich aber vor der Berechnung eines 6 x 6 Feldes. Ich gebe nun einige Zahlen vor und berechne wie oben beschrieben. Zuerst rechne ich mir die oberste Reihe und die spalte links aus. Von dort an, berechne ich Richtung rechts unten alles aus. Mein Problem ist nun, dass: 1. Alle Zahlen nur einmal vorkommen dürfen 2. Jedoch trotzdem die Zahlen zusammen in jeder Reihe und in jeder Spalte eine Quersumme ergeben sollen. Mein Programm zur Berechnung schafft es nicht, dieses "Rätsel" zu lösen. Es scheint, als wäre es mit den Grundrechenoperationen hier nicht mehr weiter zu kommen. Habt ihr für mich noch einen Tipp? |
|||||||||
30.08.2017, 09:51 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Nur einmal pro Zeile bzw. Spalte (das wäre "wie Sudoku") oder doch nur einmal im gesamten Feld (wie beim klassischen Magischen Quadrat) ?
Der von mir oben propagierte Bruteforce-Algorithmus zur Bestimmung aller (!) Lösungen ist bei einem 6x6-Feld (mit 36 Einzelfeldern) und Durchprobieren aller 100 Möglichkeiten pro Einzelfeld natürlich nicht mehr praktikabel. Selbst bei Vorgabe von Feldern und Ausnutzung der Spalten- und Zeilensummen bleiben immer noch ca. Varianten durchzutesten, für kleine undurchführbar. Die Frage ist: Du kannst ja unmöglich an einer Auflistung aller Lösungen interessiert sein (die würden nicht Bücher, sondern ganze Universen füllen) - bist du bereits mit einzelnen Lösungen zufrieden, die deinen Bedingungen genügen? |
|||||||||
30.08.2017, 10:13 | Tangens | Auf diesen Beitrag antworten » | |||||||
Entschuldige, blöd ausgedrückt. Jede Zahl soll im gesamten Quadrat nur einmal vorkommen. An allen Lösungen bin ich nicht interessiert, jedoch an vielen. Die Zahlen im Quadrat habe ich bereits auf den Werteraum 0 - 100 eingegrenzt. Eventuell ist die Eingrenzung auch zu groß. Jedoch auch ein größerer Werteraum hat den selben Effekt. Mein Programm soll so funktionieren, dass es für die 36 möglichen Zahlen die Zahlen aus dem Werteraum nimmt. Summe der Spalten und Zeilen soll wie gesagt die Quersumme sein. Welche positiven Zahlen dies sind und wie hoch im Endeffekt die Quersumme ist, ist nicht so wichtig. Nur der Werteraum darf nicht zu hoch sein. Problem ist eben, dass ich mit relativ viele Zufallszahlen arbeite, bis ich zu einem berechenbaren Muster komme. |
|||||||||
30.08.2017, 10:16 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Dann würde ich spontan so vorgehen: 1) Suchen einer Zeile sowie Spalte , wo keiner der Vorgabewerte drin sind. Sowas gibt es doch, oder? 2) Auswürfeln aller Felder außer denen in Zeile und unter Beachtung der Vorgabe, dass keine Werte mehrfach vorkommen. 3) Überprüfen der bisherigen Zeilen- und Spaltensummen: Sollten da welche mehrfach vorkommen, dann zurück zu Punkt 2. Ansonsten mögen diese dann 25 verschiedenen Werte die Menge bilden. 4) Der gemeinsame Zeilen- und Spaltensummenwert liegt ja auf jeden Fall im Bereich . Man probiere alle Möglichkeiten aus diesem Intervall durch: Bei Vorgabe eines Wertes kann man ja die noch fehlenden 11 Werte in Zeile bzw. Spalte genau ausrechnen. Sollten es da keine Überschneidungen mit den in 2) berechneten 25 Werten kommen, hat man ein passendes Gesamttableau gefunden, ansonsten wieder zurück zu 2). Zu beachten ist auch, dass (wenn es blöd läuft) der Bereich in 4) "leer" ist. In dem Fall geht es sofort wieder zu 2) zurück. Evtl. ist es überdenkenswert, die Punkte 2) und 3) zu verzahnen: Bei entsprechender "Befüllung" z.B. zeilenweise kann man ja die Verschiedenheit der partiellen Zeilensummen ja schon "on the fly" überprüfen und irgendwie gegensteuern (sofortiger Abbruch und Neustart oder das Auswürfeln einzelner Felder wiederholen). |
|||||||||
30.08.2017, 10:17 | Tangens | Auf diesen Beitrag antworten » | |||||||
Das ist schon mal ein guter Denkanstoss, probiere ich gleich einmal aus, danke! |
|||||||||
30.08.2017, 13:21 | Tangens | Auf diesen Beitrag antworten » | |||||||
Leider war es nicht von Erfolg gekrönt. Es kommen relativ viele negative Zahlen vor, da die Quersumme zu klein ist, vermute ich. |
|||||||||
30.08.2017, 13:26 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Dann machst du was falsch, denn bei mir klappt es - in Sekundenbruchteilen. Tatsächlich ist es so, dass der befürchtete Fall
tatsächlich der Regelfall ist (hätte man mit einer kleinen Wahrscheinlichkeitsbetrachtung auch eher drauf kommen können. ) Aber dennoch kommt man genügend oft "durch", und dann auch zu einer Lösung. |
|||||||||
30.08.2017, 14:20 | Tangens | Auf diesen Beitrag antworten » | |||||||
Fragt sich halt was? Ich erstelle zuerst die Zeile 1 mit Zufallszahlen, danach Spalte 1, wobei die unterste Zahl berechnet wird. Danch ist Spalte 6 dran, die letzte Zahl wird über die Quersumme berechnet. Anschließend die unterste Reihe, wobei auch wieder eine Zahl berechnet wird. So arbeite ich mich nach innen vor. |
|||||||||
30.08.2017, 14:22 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Wieviel (also Wert ) Vorgabewerte hast du denn, wo sind die platziert und welche? Die kann ich dann ja mal durch meinen Algo jagen, vielleicht schlummert da noch was? |
|||||||||
30.08.2017, 14:26 | Tangens | Auf diesen Beitrag antworten » | |||||||
Ich habe nun beides versucht: 1. Zahlen willkürlich vorgegeben, den Rest berechnen lassen oder per Zufall erstellt. 2. Reihe 1 und Spalte 1 vorgegeben und den Rest im Kern per Zufall erstellt und dann Reihe 6 und Spalte 6 berechnen lassen. Egal wie ichs mache, er hängt sich auf. Habe nun eine Sicherheitsvariable eingebaut, damit er sich nicht jedes mal aufhängt und mir mein Programm abschmiert. Maximal 500 - 600 durchläufe macht er, danach StackOverflow. |
|||||||||
30.08.2017, 14:30 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Mit Reihe 1 ist natürlich schon die Summe festgeklopft, insofern trifft das nicht so die Situation von meinem Algorithmus oben: Der setzte voraus, dass zumindest eine Zeile und eine Spalte noch komplett frei belegbar sind - in meiner Algorithmenumsetzung sind das o.B.d.A. die letzte Zeile und die letzte Spalte (ansonsten tauschen). Zudem ist die Vorgabe von Spalte 1 nicht mehr frei: Sie muss dieselbe Summe wie Zeile 1 aufweisen! |
|||||||||
30.08.2017, 14:42 | Tangens | Auf diesen Beitrag antworten » | |||||||
Ach so meinsst du das, hatte erst nicht ganz verstanden wie du es meintest. Also erst die 25 Felder per Zufall erstellen, danach die letzte Spalte und letzte Zeile berechnen. Versteh ich das so richtig? Nehmen wir mal an, die letzte Spalte und die letzte Zeile wären frei. Dann wäre Zahl 36 der Knackpunkt. Denn sowohl in der Spalte, als auch in der Zeile muss der selbe Quersummenwert erreicht werden. |
|||||||||
30.08.2017, 14:48 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Das ist kein Problem: Wenn Zeile 1..6 und Spalte 1..5 dieselbe Summe haben, dann hat auch Spalte 6 automatisch Summe - warum? |
|||||||||
30.08.2017, 15:03 | Tangens | Auf diesen Beitrag antworten » | |||||||
Arbeiten wir mal mit Grafiken, vielleicht kommen wir dann auf einen Nenner.^^ So sieht es bei mir gerade eben aus. [attach]45190[/attach] (Frag mich einer warum das so verschwommen aussieht, bei einem Klick drauf, wirds schärfer) Ein 25er Feld welches mit Zufallszahlen gefüllt ist und eine Zahl rechts oben - Spalte 6 mit einer 50. Ergibt die erste Quersumme 218. Problem fängt hier jedoch an. Die 218 gehört mit zu den kleinsten Quersummen, es müssen demnach fast überall negative Werte auftreten. |
|||||||||
30.08.2017, 15:06 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Naja, können wir sofort ad acta legen: Es ist und , und das erfüllt damit den Tatbestand
Hast du oben wohl noch nicht ernst genommen. Das "ansonsten wieder zurück zu 2)." ist nicht der Ausnahme-, sondern der Regelfall. |
|||||||||
30.08.2017, 15:15 | Tangens | Auf diesen Beitrag antworten » | |||||||
Doch, ist heut nur einfach nicht mein Tag.^^ Also jetzt für ganz verpeilte... Du rechnest somit die 5 Spalten und 5 Reihenwerte zusammen und bildest daraus eine Summe, aus der du dann wieder die letzte Zahl jeder Reihe und Spalte ermittelst? |
|||||||||
30.08.2017, 15:27 | HAL 9000 | Auf diesen Beitrag antworten » | |||||||
Eigentlich habe ich es oben ziemlich genau beschrieben, aber bitte, ich bin den flüchtigen Stil hier im Board langsam gewohnt, dass manche alles erst vier- bis fünfmal hören müssen, bis sie wirklich drüber nachdenken. Also nochmal, mit etwas anderen Worten: Es werden zunächst die ersten 5 Zeilen und ersten 5 Spalten bestimmt (z.T. vielleicht vorgegeben, der Rest simuliert). Dann sind (wie ich voraussetze) Zeile 6 und Spalte 6 noch komplett leer. Wie groß ist nun die gemeinsame komplette Zeilen- und Spaltensumme aller Zeilen und Spalten des Tableaus? Nun, mindestens so groß wie die größte der bisherigen 10 ermittelten (noch unvollständigen) Zeilen- und Spaltensummen, aber zugleich auch um maximal 99 größer als die kleinste dieser 10 Zahlensummen. Das gibt den Rahmen vor für die zu probierenden Werte für , und der ist also . Für dein Tableau oben bedeutet dies , und leider gibt es keine Zahlen , die das erfüllen... daher: Dieses Tableau wegwerfen, ein neues generieren. Wie es oben schon stand: Die Ergänzung der letzten Zeile und Spalte macht nur für aus diesem Intervall Sinn, weil nur so keine "negativen Zahlen" oder Zahlen >= 100 im Tableau auftauchen!!! Und die 10 Summen müssen deswegen verschieden sein, weil nur so die ergänzten 10 Werten in den Zeilen und Spalten auch voneinander verschieden sind. Letztlich müssen diese 10 sowie auch Nummer 11 (bei dir Feldelement 36) aber zusätzlich von den ersten 25 verschieden sein - eine weitere Prüfung. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|