🚀 go-pugleaf

Pentominos - Eine Aufgabenstellung mit 3 Schwierigkeitsstufen:

    leicht, knifflig, nicht loesbar (?)


Prolog:

Vor vielen Jahren las ich mal einen faszinierenden SF-Roman von Arthur C.
Clarke (ja, genau der von 2001 :-) ): "MacKenzie kehrt zur Erde heim"
Leider hab ich das Buch grad nicht griffbereit und weiss daher nicht den
Originaltitel.

In dem Buch kommt eine Art Denksportaufgabe vor, die Pentominos.
Diese Aufgabe hatte mich damals als 14 jaehrigen derart gefesselt, dass ich
darueber staendig meine Hausaufgaben vergass und sogar ab und zu zu spaet
zur Schule kam, von den blutunterlaufenen Augen wegen zu wenig Schlaf und
zermartertem Gehirn ganz zu schweigen :-)


Der erste Teil der Aufgabe ist relativ einfach:

Gegeben sind 5 Quadrate gleicher Kantenlaenge. Wieviele geometrische
Figuren koennen damit gemacht werden wenn sich dabei die Quadrate ueber
mindestens eine (ganze) Kantenlaenge beruehren?
Figuren, die durch Spiegelung oder Rotation aus einer anderen hervorgehen,
werden dabei nicht mitgezaehlt bzw sie werden als identisch behandelt.

Loesung:  12
                                                                     
OOOOO   OOOO    OOOO    OOO   OOO   OO     O    OO    OO    OOO      
           O       OO   OO    O O    OO   OOO    O     OO    O       
       O                              O    O     OO    O     O       
  O    O                                                             
OOOO   OOO


Wir haben nun 5*12 Basisquadrate, macht zusammen 60.
Kommen wir zum schwierigeren Teil:
Diese 12 geometrische Figuren sollen nun in ein 10*6 grosses Rechteck
untergebracht werden, so dass dieses vollstaendig ausgefuellt wird.

Damals mit 14 brauchte ich knapp 4 Tage bis zur ersten Loesung, gestern
Nacht nur noch 30 min :-)

Legt mal los..'

Ich hatte damals ca 130 verschiedene Loesungen gefunden und aufgeschrieben.
Das gemeine an der Sache war bzw ist, dass Clarke (genauer: der Computer in
dem Roman) behauptet, dass es exakt 2673 Loesungen gibt. Gemein deshalb,
weil der Computer das kurzerhand berechnet und ich damals wie heute keine
Moeglichkeit sehe, das zu ueberpruefen.
Ich wills aber wissen! *fus_stampf* :-)

Nun zum unloesbaren(?) Teil meiner Aufgabe:
Kann man ueberhaupt die Anzahl der Loesungen berechnen?
Kann man die Loesungen selbst algorithmisch berechnen?
Oder nur durch die Holzhammermethode, sprich simples Ausprobieren?

Wenn letzteres gilt, dann moechte ich gerne wissen, wie man das am
geschicktesten programmiert :-)

Ich habe mir schon diverse Ausprobieralgorithmen ueberlegt, aber alle sind
schrecklich ineffzient und wuerden gigantisch viel Rechenzeit verbraten.

Bei Hinweisen nach einem Algorithmus moechte ich bitten zu
beruecksichtigen, dass ich weder Mathematiker noch Informatiker bin: bitte
begrabt mich nicht mit Fachausdruecken :-)


\  Ulli 'Framstag' Horlacher    \    psi%0262450502601::rzmain::orakel  \
 \  Student consultant VAX/VMS and networks   \  orakel@dulruu51.bitnet  \
  \  Rechenzentrum  Universitaet Ulm  Germany  \    orakel@rz.uni-ulm.de  \
   \  "With mainframes you just can do nonsense, with PCs not even that."  \