c't Puzzle

[janjan]

Infos gibts in der aktuellen c't oder hier:

http://www.heise.de/ct/puzzle/

Ich zerbreche mir jetzt schon seit ein paar Tagen den Kopf wie das zu lösen sein könnte und komm auf keinen grünen Zweig. Der Artikel im Heft hilft nicht viel weiter, mittendrin hört es mit dem Verständniss einfach auf.

Wer von euch hat sich das mal angekuckt und evtl. schon ein paar Gedanken dazu gemacht?

[Minz]

Meinst du, wie man das mit Delphi löst, oder generell?

[janjan]

Ob man das jetzt in Delphi oder sonstwie löst ist eigentlich egal, mir gehts eher um das Verfahren/die Algorithmen die dahinterstehen.

[Minz]

*grübel*

also ich würde mal so anfangen, eine Matrix von 3x4x5 definieren.
Diese würde ich dann so mit den Würfeln belegen, dass schonmal C und T
zu sehen sind.
Dann geht es weiter die einzelnen Apostrophs durchzuprobieren.
Einfach eins nehmen und ausprobieren.

Den Rest der Matrix die leer ist, einfach wahllos mit Steinen füllen, bis nix mehr reinpasst.
Jetzt würde ich versuchen durch austauschen und verschieben Platz zu gewinnen, und dies solange bis alle Steine reingehen.
Wenns net funzt ein anderes Apostroph ausprobieren. Kann natürlich passieren, dass man die Lösung dabei um einen Versuch verpasst
jenachdem, wielange man ausprobieren lässt, man kann natürlich dabei
auch alle Möglichkeiten systematisch durchprobieren, aber des wird glaub ich zuviel!

[janjan]

Es geht darum alle Möglichen Lösungen zu finden, da wirst du mit wahllos ausprobieren nicht weit kommen.

Was du das so schreibst von wegen 'verschieben' und 'vertauschen' hört sich einfacher an als es in Wirklichkeit ist. Ich such da seit ein paar Tagen nach einer sinnvollen Lösung, aber je länger ich drüber nachdenke, desto werd ich...

[Minz]

Naja alle Möglichkeiten zu finden ist nahezu so komplex wie Schachstellungen zu berechnen. Es sind einfach zu viele!!

Das vertauschen an sich sollte nicht das Problem sein.
Du untersuchst die maximal-Ausmaße der Steine, die du vertauschen
willst und schaust ob der eine irgendwie an die andere Position
passt. Da du eine Matrix benutzt kannst du einfach die nötigen Matrix-
Felder mit dem Stein abgleichen. Dabei kannst du untersuchen, welche
Einzelwürfel im Stein nicht passen würden. Dann legst du eine Grenze fest, ab wieviel blockierten Einzelsteinen du weitersuchst. Wenns nur
einer ist, kannst du mal schauen, ob verschieben oder drehen weiterhilft, oder du behälst diesen Stein im Speicher und tauscht ihn mit dem nächsten...

[janjan]

Mal logisch ganz von vorne:

-Das Puzzle besteht aus 3*4*5 Teilen, das Ergibt eine Anzahl von *kopfrechnen* 60 Feldern.

-Auf die 60 Felder müssen 12 Objekte unterschiedlicher Größe gepackt werden.

-Für ein Teil gibt es 24 Möglichkeiten der räumlichen Orientierung.

-Ich lege für jedes Teil ein 'Zentrum' fest. Das heißt man legt ein Feld eines Teils willkürlich als Zentrum fest.

Angenommen ich versuche nur die Zentren der Objekte in den Würfel zu legen kommt man auf eine große Zahl, nämlich 60^12. Da sind aber auch Fälle drin, in denen zwei oder mehr Zentren auf einem Feld liegen. Die Anzahl der Möglichkeiten 12 Zentren auf 60 Felder ohne Überschneidungen zu legen ist

60*59*58*57*56*55*54*53*52*51*50*49

Dazu kommen dann noch die 24 Möglichkeiten ein Teil im Raum zu lagern

Angenommen man kann 10.000 Positionen pro Sekunde testen, dann dürfte es (wenn ich mich nicht verrechnet habe) ca. 200.000 Jahre dauern bis man fertig ist...


Ein wenig ZU lange für meinen Geschmack 8)

[Minz]

hä? liest du auch was ich schreibe?

[janjan]

Genau das selbe könnt ich dich fragen Es geht darum die Anzahl der Möglichen Lösungen zu finden, die Konfiguration mit dem c't oben ist optional. laut dem Artikel gibt es ca. 100.000 Lösungen.

Ich wollt nur mal kucken wie viele Möglichkeiten es maximal geben kann und ob man eventuell mit Brute-Force weiter kommt. Das das nicht klappt hab ich dann auch schnell festgestellt.

Ich denke es läuft daraus hinaus sich im vorhinein zu überlegen welche Positionen das Zentrum für ein Teil in einer nestimmten räumlichen Lage einnehmen kann.

Am Beispiel von diesem Kreuzförmigen Teil kann man das von 60*24=1440 auf 30 Möglichkeiten reduzieren...

[Minz]

Ich wunderte mich nur warum du mir vorrechnest, dass das solange dauern würde, wenn ich grad zuvor geschrieben hatte, das es zuviel wäre