Algorithmus für "Super-IQ"-Würfel

[Michael.Kallas at kaufhof.de]

> Hallo Michael,
> 
> > Seit geraumer Zeit geistert mir ein Problem im Kopf herum:
> > Ich habe von jemandem einen Würfel (an einer Seite offen) bekommen, den
> man
> > mit kleinen Holzsteinen füllen muß.
> > Der Würfel hat die Kantenlänge 5, die Steine sind 5 Würfel mit
> Kantenlänge
> > 1, 6 Quader mit 1x2x4 und 6 Quader mit 2x2x3.
> > Ausprobieren am realen Objekt könnte mich zum Wahnsinn treiben, also
> habe
> > ich versucht, irgendwie das Problem faßbar zu bekommen und an meinen
> > Rechenknecht zu vergeben.
> > Aber ich komme auf keinen gescheiten Algorithmus.
> > Hat jemand Ideen?
> 
> Hört sich nach einer interessanten Spielerei an ;-)
> 
> Hast Du eine Idee zur Datenstruktur? Wie stellst Du den großen
> Containerwürfel dar, und wie könnte ein Programm die einzelnen Bausteine
> sehen? Wie wird die Position der Bausteine im Containerwürfel dargestellt?
> 
> Wie sehen die elementaren Operationen aus? Wie stellst Du es an, einen
> Baustein in den Container zu legen? Wie prüfst Du vorher, ob dieser
> Baustein
> dorthin paßt?
> 
[Michael:]  Genau das waren auch meine Fragen. Ich hab mir ein bißchen den
Kopf zerknotet, war mir aber nicht ganz schlüssig, wonach ich die Schritte
überhaupt ordnen könnte (um es z.B. nach einer Unterbrechung weiterlaufen
lassen zu können).
[Michael:]  Ich hatte mir gedacht, eine Art Buchstabenkombination
auszudenken: Quader A1-6, Quader B1-6, Würfel C1-5, die dann jeweils eine
Kombination aus Raumlage und Drehung repräsentieren. Irgendwie ist das Thema
komplexer als ich dachte ;)
>  
> Wenn Du über _viel_ Rechenzeit verfügen kannst, suche mit der
> Brute-Force-Methode. Das heißt, daß Dein Programm alle möglichen
> 
[Michael:]  War auch meine Idee, wieviel ist _viel_ (auf der Grundlage eines
PIII 500) ?
> Kombinationen der Bausteine im Containerwürfel in geordneter Reihenfolge
> ausprobiert, und bei Erfolg abbricht. Achte darauf, Dreh- und
> Spiegelsymmetrien auszuschließen, das vermindert die Rechenzeit um einen
> Faktor 14 oder so.
> 
> Wenn Dir beim Basteln mit dem realen Modell weitere Gesetzmäßigkeiten
> auffallen, nur rein damit.
> 
> Ein anderer Ansatz wären "genetische Algorithmen". Hierbei werden zunächst
> mal aufs Geratewohl in mehreren Versuchen die Bausteine in den Container
> gepackt, so gut es eben geht. Wenn der Treffer dabei ist, ist es gut.
> Sonst
> bewertet man die einzelnen Versuche und greift sich die besten heraus. Das
> werden wohl diejenigen sein, bei denen die meisten Steine im Container
> untergebracht werden konnten. Diese werden dann leicht modifiziert und mit
> anderen Versuchen permutiert.
> 
> HTH,
> Bernd