🚀 go-pugleaf

In de.sci.misc, article <1992Sep12.175946.14706@wega.rz.uni-ulm.de>,
  ORAKEL@rzmain.rz.uni-ulm.de (Framstag) writes:
> Pentominos - Eine Aufgabenstellung mit 3 Schwierigkeitsstufen:
> 
>     leicht, knifflig, nicht loesbar (?)
> 
Knifflig aber loesbar.
> 
> 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* :-)
> 
Clarke hat geflunkert. Es sind 195.

> Nun zum unloesbaren(?) Teil meiner Aufgabe:
> Kann man ueberhaupt die Anzahl der Loesungen berechnen?
> Kann man die Loesungen selbst algorithmisch berechnen?

Das hat bisher noch keiner geschafft.

> Oder nur durch die Holzhammermethode, sprich simples Ausprobieren?
> 
Das ist auch ein Algorithmus! ;-)

> Wenn letzteres gilt, dann moechte ich gerne wissen, wie man das am
> geschicktesten programmiert :-)
> 
Beobachte dich mal selber, wie du das Problem loest. Ich jedenfalls suche mir
die unzugaenglichste Ecke und plaziere dorthin alle moeglichen Pentominos in
allen moeglichen Orientierungen, und dann geht's rekursiv mit der naechsten
unzugaenglichen Ecke weiter. Wenn es keine solche Ecke gibt, ist das Quadrat
voll und die Loesung kann ausgegeben werden.
Ein entsprechendes Programm braucht auf meinem Mac IIfx+Unix+GCC 2.2.1 eine
halbe Stunde.
(Symmetrieprobleme loesen wir, indem fuer eines der Teile von acht moeglichen
 Orientierungen nur eine vertikale und eine horizontale Orientierung zuge-
 lassen werden. Das erspart eine Menge Arbeit.)

* Pentomino 1
EEGJJJCKBB
EGGGJCCKBA
EEGHJCKKBA
LHHHICFKBA
LHIIIFFDDA
LLLIFFDDDA

* Pentomino 51
LLLEEEBBII
LHHEGEBIIK
LCHGGGBJIK
CCHHGFBJKK
CDDDFFJJJK
CDDFFAAAAA

* Pentomino 101
JJJCCCBBBB
KJCCLLLDDB
KJHHFFLDDD
KKHFFGLIEE
KHHFGGGIIE
AAAAAGIIEE

* Pentomino 151
JJJFFGBBBB
AJFFGGGDDB
AJFHHGKDDD
AEEIHKKKKL
AEIIHHCCCL
AEEIICCLLL

* Pentomino 195
BBBBICCCEE
AHHBIIGCCE
AKHIIGGGEE
AKHHFJGLLL
AKKFFJDDDL
AKFFJJJDDL

-- 
Long's Note
   Always store beer in a dark place.
-- 
Matthias Urlichs  --  urlichs@smurf.sub.org -- urlichs@smurf.ira.uka.de   /(o\
Humboldtstrasse 7 -- 7500 Karlsruhe 1 -- Germany  --  +49-721-9612521     \o)/