Magisches Quadrat

Neue Frage »

Tangens Auf diesen Beitrag antworten »
Magisches Quadrat
Hallo an alle!

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
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
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
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?
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.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tangens
Ich suche nun eine Formel mit der ich sämtliche X Werte (Unbekannten) berechnen kann, sodass am Ende sämtliche "?" dieselbe Quersumme ergeben.

[...]

Zu einer Lösung kommt man schon, es dauert nur mit der Berechnung 1 - 2 Minuten.

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. Augenzwinkern
 
 
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.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tangens
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.

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:

code:
1:
2:
3:
4:
a 3 c ?
d e f ?
g h 2 ?
? ? ?
Wir lassen alle Kombinationen {0,..,99} durchlaufen, das sind Stück. Dann lässt sich die Summe bestimmen, damit sofort (falls es außerhalb {0,...,99} liegt -> Fall "wegwerfen").

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).
Tangens Auf diesen Beitrag antworten »

Na klar, stimmt, warum bin ich nicht gleich drauf gekommen, danke dir! Big Laugh
xb Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
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).


Kann das sein?
357159 Lösungen bei 100 Zahlen

Wie sind da die Quersummen verteilt?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von xb
Wie sind da die Quersummen verteilt?

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
  3	1
  4	4
  5	9
  6	15
  7	22
  8	30
  9	39
 10	49
 11	60
 12	72
 13	85
 14	99
 15	114
 16	130
 17	147
 18	165
 19	184
 20	204
 21	225
 22	247
 23	270
 24	294
 25	319
 26	345
 27	372
 28	400
 29	429
 30	459
 31	490
 32	522
 33	555
 34	589
 35	624
 36	660
 37	697
 38	735
 39	774
 40	814
 41	855
 42	897
 43	940
 44	984
 45	1029
 46	1075
 47	1122
 48	1170
 49	1219
 50	1269
 51	1320
 52	1372
 53	1425
 54	1479
 55	1534
 56	1590
 57	1647
 58	1705
 59	1764
 60	1824
 61	1885
 62	1947
 63	2010
 64	2074
 65	2139
 66	2205
 67	2272
 68	2340
 69	2409
 70	2479
 71	2550
 72	2622
 73	2695
 74	2769
 75	2844
 76	2920
 77	2997
 78	3075
 79	3154
 80	3234
 81	3315
 82	3397
 83	3480
 84	3564
 85	3649
 86	3735
 87	3822
 88	3910
 89	3999
 90	4089
 91	4180
 92	4272
 93	4365
 94	4459
 95	4554
 96	4650
 97	4747
 98	4845
 99	4944
100	5044
101	5144
102	5238
103	5138
104	5038
105	4938
106	4839
107	4741
108	4644
109	4548
110	4453
111	4359
112	4266
113	4174
114	4083
115	3993
116	3904
117	3816
118	3729
119	3643
120	3558
121	3474
122	3391
123	3309
124	3228
125	3148
126	3069
127	2991
128	2914
129	2838
130	2763
131	2689
132	2616
133	2544
134	2473
135	2403
136	2334
137	2266
138	2199
139	2133
140	2068
141	2004
142	1941
143	1879
144	1818
145	1758
146	1699
147	1641
148	1584
149	1528
150	1473
151	1419
152	1366
153	1314
154	1263
155	1213
156	1164
157	1116
158	1069
159	1023
160	978
161	934
162	891
163	849
164	808
165	768
166	729
167	691
168	654
169	618
170	583
171	549
172	516
173	484
174	453
175	423
176	394
177	366
178	339
179	313
180	288
181	264
182	241
183	219
184	198
185	178
186	159
187	141
188	124
189	108
190	93
191	79
192	66
193	54
194	43
195	33
196	24
197	16
198	9
199	4
200	1
xb Auf diesen Beitrag antworten »

Nicht schlecht
Gibt´s auch noch einen Erwartungswert smile

HAL 9000 Auf diesen Beitrag antworten »

Hmm, nein:
xb Auf diesen Beitrag antworten »

Irgendwie magisch smile
Tangens Auf diesen Beitrag antworten »

Da bin ich noch einmal! smile

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?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tangens
jedoch soll jede Zahl nur einmal vorkommen, ähnlich wie bei Sudoku.

Nur einmal pro Zeile bzw. Spalte (das wäre "wie Sudoku") oder doch nur einmal im gesamten Feld (wie beim klassischen Magischen Quadrat) ?

Zitat:
Original von Tangens
Mein Programm zur Berechnung schafft es nicht, dieses "Rätsel" zu lösen.

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?
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.
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).
Tangens Auf diesen Beitrag antworten »

Das ist schon mal ein guter Denkanstoss, probiere ich gleich einmal aus, danke! Freude
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.
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

Zitat:
Original von HAL 9000
Zu beachten ist auch, dass (wenn es blöd läuft) der Bereich in 4) "leer" ist.

tatsächlich der Regelfall ist (hätte man mit einer kleinen Wahrscheinlichkeitsbetrachtung auch eher drauf kommen können. Augenzwinkern )

Aber dennoch kommt man genügend oft "durch", und dann auch zu einer Lösung.
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. verwirrt
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?
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.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tangens
2. Reihe 1 und Spalte 1 vorgegeben

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! verwirrt
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.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Tangens
Dann wäre Zahl 36 der Knackpunkt. Denn sowohl in der Spalte, als auch in der Zeile muss der selbe Quersummenwert erreicht werden.

Das ist kein Problem: Wenn Zeile 1..6 und Spalte 1..5 dieselbe Summe haben, dann hat auch Spalte 6 automatisch Summe - warum? Augenzwinkern
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.
HAL 9000 Auf diesen Beitrag antworten »

Naja, können wir sofort ad acta legen:

Es ist und , und das erfüllt damit den Tatbestand

Zitat:
Original von HAL 9000
Tatsächlich ist es so, dass der befürchtete Fall

Zitat:
Original von HAL 9000
Zu beachten ist auch, dass (wenn es blöd läuft) der Bereich in 4) "leer" ist.

tatsächlich der Regelfall ist (hätte man mit einer kleinen Wahrscheinlichkeitsbetrachtung auch eher drauf kommen können. Augenzwinkern )

Aber dennoch kommt man genügend oft "durch", und dann auch zu einer Lösung.

Hast du oben wohl noch nicht ernst genommen. Augenzwinkern

Das "ansonsten wieder zurück zu 2)." ist nicht der Ausnahme-, sondern der Regelfall. smile
Tangens Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000Hast du oben wohl noch nicht ernst genommen. Augenzwinkern


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?
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »