Weihnachtsrätsel

[HeLLsHInE]

Bei uns ist es üblich das es immer zu Weihnachten eine Knobelaufgabe gibt.
Ich dachte da sich schon viele am Projekt Euler beteiligen könntet ihr vielleicht auch an so etwas Spass haben:

Aufgabe : Ein Würfel hat bekanntlich 12 Kanten und 6 Flächen. Verteilen Sie die Zahlen 1, 2, 3, … , 12 als Gewichte so auf die Würfelkanten, dass die Summe der Kantengewichte für alle sechs Flächen gleich ist. Dabei
darf jedes Kantengewicht nur einmal vergeben werden.

Definition : Zwei mögliche Lösungen heissen verschieden, wenn diese nicht durch Spiegelungen und Rotationen ineinander überführt werden können.

Also möglichst viele oder alle Lösungen finden.

 

[Brusko651]

zu schwer^^

 

[Dr. Picasso]

die 12 fakultät möglichkeiten kann man ja brute forcen

mach ich heute abend mal, damit das forum hier nicht eingeht

 

[ducki]

bei meiner sauschlechten implementierung würde das bruteforcen geschätze 10 jahre dauern. da muss es doch ne elegantere lösung geben 8[
ich glaub mit dem aufgestellten LGS kommt man auch nicht unbedingt weiter:

LGS:

l + k + i = b + f + a
l + k + j + i = h + g + f + e
k + j + i = c + h + d
l + j + i = c + b + g
l + k + j = d + a + e
j + b + a = h + g + e
j + b + f + a = l + c + h + d
j + f + a = c + k + g
j + b + f = d + i + e
h + g + f + e = l + c + h + d
h + f + e = c + k + b
h + g + f = d + i + a
l + h + d = k + b + g
l + c + h = i + a + e
c + k + b + g = d + i + a + e

 

[Myta]

die 12 fakultät möglichkeiten kann man ja brute forcen

mach ich heute abend mal, damit das forum hier nicht eingeht

es sind sogar nur 12! / 6! möglichkeiten wenn du aus der bedingung für die 6 seiten sechs gleichungen machst, und dann brute force nur auf die übrigen 6 variablen anwendest. wenn du zusätzlich noch rotationen vermeidest sparst du dir noch mal einen faktor 24. bleiben noch knappe 30 000 möglichkeiten.

 

[mfb]

Man kann eine Kante mit einer beliebigen Zahl fest vorgeben, wenn man noch 5 weitere Zahlen an irgendwelchen Kanten vorgibt, hat man noch 6 Unbekannte und 6 Gleichungen. Macht also nur noch 11!/6!=55440 Möglichkeiten, ohne dass man Rotationen rausfischen muss. Dazu kann man bei sinnvoller Wahl der festzusetzenden Kanten noch eine Ebenensymmetrie ausnutzen und eine Kante willkürlich als kleiner als eine andere Kante festlegen, das halbiert die Zahl der Möglichkeiten nochmal auf 27720. Wobei der größte Teil davon noch wegfällt, wenn man als erste feste Zahl die 1 oder die 12 nimmt und einer oder beiden zugehörigen Flächen zwei weitere Kanten gibt. Dann führen die meisten Gleichungssysteme direkt dort zu einer unmöglichen Lösung (kleiner als 1 oder größer als 12).

Wirklich lösen muss der Computer dann vielleicht noch 10000 Gleichungssysteme. Oder anders gesagt: Die Implementierung dauert viel länger als das eigentliche Berechnen.

 

[Dr. Picasso]

ah ganz vergessen.

mein vorschlag:
insgesamt sind es 960.
nimmt man rotationen raus, sind es 40.
nimmt man spiegelungen raus, sind es 20.
korrekt?

habe es brute force gelöst, also keine gleichungssysteme aufgestellt, sondern einfach alle möglichkeiten durchprobiert. rechenzeit < 1s.