🚀 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.
> 
> 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.
> 
Drehung und Spiegelung sind hoffentlich erlaubt.  ;-)

> 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?
> 
Ausprobieren mit Heuristik.

> 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.
> 
OK. Als ersten Schritt initialisieren wir eine Array [i][j] mit
Pentomino i in Orientierung j. Es gibt mit Drehung und Spiegelung
bis zu 8 Orientierungen; bei einem dieser 8fach orientierten Teile
lassen wir alle bis auf eine horizontale und eine vertikale
Orientierung weg und ueberspringen dadurch bei der Loesungssuche
saemtliche symmetrischen Faelle.
Die Initialisiererei ist statisch, weil wir keine Lust haben, einen
Pentominogenerator zu schreiben und, schlimmer, zu debuggen.  ;-)

Brutale Methode:
pento(i) {
   wenn i = 12, drucke gefundene Loesung. Return.
   fuer jede moegliche Stelle fuer jede moegliche Orientierung von [i]
      plaziere [i] dorthin
      pento(i+1)
      nimm [i] wieder weg
}
main() { init(); pento(0); }
Geschaetzte Dauer: mehrere Wochen. Nach zwei Stunden Programmlauf
wurde keine einzige Loesung gefunden. So lang ist mein Rechner nicht
up -> Suche nach besserer Loesung.  ;-)

OK, ich beobachte mich nun selber beim Versuch, eine Loesung per Hand zu
generieren, und finde folgende semiintelligente Methode:
pento() {
   suche freie Stelle mit den meisten belegten Plaetzen drumherum
	   (der Rand ist 4 Stellen breit und wird als "belegt"
	    initialisiert, um die Abfrage diverser Randbedingungen
	    weglassen zu koennen)
   wenn keine Stelle gefunden
      Loesung drucken, Return
   wenn freie Stelle mit > 6 belegten Plaetzen drumherum gefunden
      Situation unmoeglich, Return
   fuer alle noch nicht plazierten Pentominos in allen Orientierungen
	   in allen Positionen ueber dieser Stelle
      wenn Pentomino passt und die Stelle durch dieses Pentomino belegt wird
	  plaziere Pentomino dorthin
	  pento()
	  nimm Pentomino wieder weg
}
main() { init(); pento(); }
Es laesst sich leicht ueberlegen, dass diese Routine notwendigerweise alle
Belegungen finden muss. Die Suche der freien Stelle bewirkt, dass die Suche
bei vielen unmoeglichen Situationen sofort abgebrochen wird.

Dauer: Eine halbe Stunde auf Max IIfx unter Unix, GCC 2.2.1 -O2 -funroll-loops.
Zahl der gefundenen Pentominos: 195.

* Pentomino 1
EEGJJJCKBB
EGGGJCCKBA
EEGHJCKKBA
LHHHICFKBA
LHIIIFFDDA
LLLIFFDDDA
[...]
* Pentomino 195
BBBBICCCEE
AHHBIIGCCE
AKHIIGGGEE
AKHHFJGLLL
AKKFFJDDDL
AKFFJJJDDL

Programm:
begin 644 pento.c.Z
M'YV0(]*X&<.F#IDR('C,H4,FS1L7:'PH"#BPX,&$<]*<<1.&#42)$P^:$8C0
M294F4(HXH?($1`P9(<N,=(,029$D1Y!0<0DCYDR$5Y(0H8($A`V?)$$T"8+%
M2A`I('`@I0D""A.5(&I,14@E2TH0<]"\D4-G*XBG18*X-(LVR-(I2T#`P`/C
M!ELI:9=B,:I``9T\<,J(!$M'3ITQ=$#L`='UJY@T=.9LL:JRRPX08]"$D0/B
M3AHR=-!<SKP9!)HR&M'0N=P'1&`W=-[L\`M8L$S"AA$K=ET&]AO76_0ZE6(9
MLV;.<_*T8<W;=XS9KV/'`&X2I4J6EA4LS)T83IK=I#F+-E[ZSNCC(.0P][ZE
M>LJ53[(K"`\"S^/(6V+PX$'92?;&18`P4AELD+&%33CIM((,*O37@@S9"928
M&]']UH-<LTF(61URL%&&'02"<"$,LRF@(1EO?`&'B!CV9<<;GX$@$&1PH/#B
M9RG,=B,9(-!1QD(U[IBCBS#R"(<<$@999`J**9"`AFG,ED"%TZD`!QQ2TI?1
M1EL$-10271QX4TY49)>`&6.AD$8/)'['`P@(DGE9&BNLP.0>3CX)&PAJ2'EF
MFFJP>9D:"8'@)5&#UIE"G@ELZ<86:H291A<LG@#""5+VT=>?<JC))@M7]H"E
MC(6Z=]T3<]8)*AR*-IF`GHDMER>`(*CPF)\5UGHEEGFF808*[$WJ`F=OPK#H
MJPF,\09L`M51!JY7LF@"'%L(2VVP70QK)J<HM/'I8Z)>V8(/]\UQ61N%[CKN
M::FM!D(;JC[6*I[(:NB&G]RZ(:@;Z8KK@V>@C>?&O(P^^:NMWYD``@K3[0>"
M&RD<BVRC&CTZ,+8NW!$FO!BCT44/)P1QP@I1,JKIJR>?C&:G:[99Z*%(I&JG
MJ[#RZ>?*"P=*(I^%QJE3HG8R"D<==(2'@J/5AAGID*\.7?1Q*)S`A1LG,'VR
MTT9+33739IA14%A',_0&T4S[B@***A9J;)YHKSCB;)HJL&-Z=5!HXY(*T`NE
ME-L=UMUW*@@DY8DQONTDE;KRZJ2&F0DJXYYCW.$XXV[(T4,+SSFYLJ<P8[Y#
M&CX(FD8++=S9ZYY]YKEYH#Y3X;D:H9.H!NFFU[OG&BS(6N^O`Q8(Z0H.QD"I
MP@PG]*::P%_E!.812_RJLLRZX2R^:[!((J.;>]M"6SNTP4,/W,,[,[W(5K_"
MA?9!)AD*O1NH1O(J8;Y"&Y3ZX(.,\"\?P_9X!<&DPFUYRQ*VE8"3O<ILU;O?
M&"I7.V1EAD5]PLP=6!0ES%2.16O`EP%3MKA?+9`S/;@0\YH$@A*:L(130A)L
M?B6"J:F@*KV)31L$\IL2D&%J(F!!G2@4PS<,Z80G3&&24/!#(*)0#F6@`X?N
MY:23F>V#(+A?`)G"I!>\T%=19(&`QG*&),HH,6EH0QL$DX8P^(@->:C5"_*$
M1"7*@8G<:MFJ1,4"@8BJ@FX"@:G@([-5J4H@!&M:#Q/'JP.BSD]F$\BX.!,Z
MN3@/>G1HUK-4!ZA/[2I<X\*2&GC@K^0LYWTK6!6KQL<H#640>VE:0[C@,"Z`
MA<9S:XC=#M9`.YH9,E;XJMD<\,"BR.4/<RTXY<2RM\IUH>8,JO$<NF3YKEJ2
MSW83RF4":(4P+2),#-(T6PB`Y:]R;8%^("!>P]ZTAN85['G+BJ3T)CFQ?!73
M!^Q")ATPQP)PJ8M<ZJMG&L30`Q.T;PN9^>7^Z'<9?C5R9VX@G3[CM<]`MM-L
MUPSGPA!F/+#@(6+G?-49WA`;$`PAG=(T(+(:0H8Z27-S^KIG/),9`WV^LUSZ
MY*<_TT`@`P4T>"T@Z,.B^+:'*51>H7R,&%J5T8CRX4(HH*C#=LFT<RK2!R"T
MV>/6U8/,Y'1."?U75>\03&D:QFY,F]A3H^HY)YT3I>]<Z3Q;:L]NYE.H_?SG
M394'3)T:M*<);<%"@]K0F155J.'L@1\F^IB*,E6:'X6-#G(IT@TVL8,H"`%)
MPZFPMDGL2$,<4MSF1A,\T*%&&II#[=K&HK+&K0UA$(B:]K29,XR!!?1106OM
ML(4NU&YO3J(5'A2G)QH1\3(^`M)O-W4'-*3!0RA0$XNZ&!LXT`$%K7WM;%D@
M`CB((&(@",&%BO`$(S!I#IYYFIH:.(8PS`$A)X##"70`@K:9%`1B0&(8A)D`
MD82A#FR@`WO-@-D5ANT@<I`#=:LPAS!TD;TEF`,(6@`''+)`MG(X@QUR!((R
MX`$R*)"!U3:U6Q8Q;#\H<)"&F<2'A>F'!RB`F4`C)J7-M>QS/1N3@A@DXL\I
M2G4T]=VD6+3;%N?80"+^F!^N=Z8?BRE!5!"HD*^GN32].(][9(F-@]:T-"1M
M6*7-',4VTA$43`$G59B"%%K:V<\R[:LUTBR18A3<S]X-1Z["[91Z6*4KS68$
M(DE*$:0@!13@C@UW$E!_Z?"KA0!8P"(H0H!AZ!L0V/`%-G2T@FWHX#2P0`TL
M^#.%+8SA&%!894ZV)!Q$]3D>O&3*?B3E+6V6IUQ9R<Z4[)3.1(E)'VBR7^/R
M)-!$Z=":5<]PT'P7OJAY*U1VRELP<.D]R]6]?K$2GL=43?<8VFN#);6P]G.-
MOUR)!B;MN<\BN,)G0I/#-H3U5>9#GS<11D!K;Y.BQ*-HMCV-4;'^:IERH6QV
M4?"8+<!@>/"U,N9L"P(^E!A=;U)IM->J[VWV^]\2[;?PL/MM%(B@"6;,3+G/
M+5($9O="_?$VGRW^T;K1(8?E]),!L08UK54M4PK8;)$>YULAQ7E/)8NCZ%!\
MXI!/N8$:2MVKTH>?20DJUBC0V0XVV9^E]SJ1)O@P#]10;V0173*3,NFK\L3!
M*?D[6Y[L@0RD1*U_NZ#LV?(FQ$>$AQ@8X3)H/_O7,S9N-/2@!CN(>]S5V@,M
MNWCG>*>3G?2>G[2K+VE])_O<J24\N@<L\81O/-_QOBG&@UTY8K^,%46$@\L@
MD0R'$<@90'`&-KQ!#!WIT6],7UXV@$4Y8RQ,&E6P1J\W/NYJIQ3;8?!VX-Q^
M[MX4GO7HHF7+R]WLW.X!#?)>^.-GB^]C/USSJ04A%^1^^+R'^_2W4/W@ZUXN
M=.F\]']?_>0OW_C4?_[",S_^;%&+!H;'S]K!#X/G^-[]6X"_]0\O_-V_O?UR
MIW_FQWR_IW_0IWB_9P/Q)QGS-Q<PT'GW)W<*N'_XT7_T]W^VAW\3.(#HMP43
M>(``:'S7MWOVUX&-YWW85WS;=X*'!R$IJ'V_QX+X,0/?YX`S@(#XUWC)-W8F
MJ'[MHGPX*'<T2($,6(-T,7812"U#B(*[%WT9*(0+R'U&"`-(V(%+>'@TB'TW
M&();,(0[2(#X-X1\MWQ<6`-1V(!T<8-)N`5F2(2%]X)E&(4N2((PB']MZ$U9
M2(=QZ'BAD7D=V(9C&(34<@-G.(5JV(&$Z(86Z(!.B(AR.(55N'V)B(>0*(A;
MD(A?Z(@0L7YD*'W5%W;BYW75AWN'AX8P4`3:-XK`QW^&J'BJB'QU!X3IYWR;
M^(.-*(5RUWVE.(4WD(KXIXL5.(5#X(J_F"T<B(NS"(*BB'_Z-X+T=XC(F']1
MN(AT@8J>R(S&&(OG%XT&N'ZWJ(H3Z(P..(S``8[3R(O$*('9^'C;:(ZU*$_L
MMXQR)X-%^(+EF(/G"(?R*((MV(KW.(]1F(?T]XWXR(=VQX/1*'F<F(Y*6(C8
M%XFJ>(7!^)`,V86/J(6^"(5N*)`.J((1N8Y]B)`?^8ZJ`837*'=WN(L4^8_4
MDI(3N7M;N(]L>)%TR)(SN9%3Z)%V")('R7RJ"(@+>9*#Z)`U.8M#J8BM*)27
M2),#F9%'28D4J928&(LBB7^)&(B59Y$N`(J*-X2D*'_H"!Q>N8HO27\VT)7X
M!XN/=X,-28O*V):S*(YIJ'UC"8R208UU@9:YR),]P)9:F8S>J)?O1Y1F29?8
MB)38UXO2-Y8"&(M^R9@^"(^W.);AJ)*[UXMBJ8'Y")."Z8%\^9B:29)T$(]P
MV7QR67^&"9"(R9F+69#>-(?/V)DZ2)7,-Y8*^8,Q69H268^<F9D:R82QV9J_
MV8]1Z75CZ86TJ9N169*Y^9<W>9J1.)8N>9=):9P[Z8:P:8.=V8:9Z)Q`B9N=
M.8F6&9N^^92LB)'":9[XD9W$%YY\B9!C>97KMX72IW]A1X9>IW]?R9OTAYF#
M28O`Z8"4EY]I^9G,IY]S]Y;2N)=N:(IX!QP(:I=O>)F*%Z$&^I^`:8L5ZIKC
MJ9T0RJ%EV9$;JIJO69T8VGS=B:"W"8_-B:"[^748^:'#&:)'.*)M6:+H2:`:
MF:)AN)RC29]>UX;WJ7AMN)\PNGMG"1Q%2I;4F:,M6:#8F9-$"J7)YY=+:G9\
MUYQ+2H]'2G\E>)/\2*,PH*4@*AGL"0-G*7U;>J%@VGQ9.J4,>IK0N*02BI=I
M&J3%&*78AY]/RJ!5RGQTZJ-]":<WVJ%TL7Q*VJ.K69AJJJ@XRIIXNJ..":B*
M^J99.8%AIX(3:*2F&(F;RJ03VI^*]ZEF]ZA-*7VDRJ:I*IJ#FI6).*32EXB<
M.H5)>I1&BI>W**N@>J;-J:MJV8=^Z:N"VJMEVJ4B"ARZRJ5XJ9A>EZQ,Z8!\
MNI2J^:>VZJ;SJ7BZ*J&F"(W9NIFGVJQY:JH.>*?56GZ36J[#BJV.:J@P@*C5
M^J++JJXS:J92&JN*2JW2VI:6*GTX<'G>$HK4TJ\`RJZUN@4">ZLF:K!0*JXU
MRJ]4>JX*ZY;7ZK`DRJY?>K"F>9X42K%A2J_%&;`%B:\8NZ+,J7@8JZV5"!PG
MZZWC:K+A2IR0"K)^"K$KRZK-B;$OVJG:A[,L2Q?,*K.%NIY3&*T\:Y"#"K1:
M::E>A['-R*[0R+0]BZ8N&X#/VK!+>Y@B>YA*B[33::R'NK/7&:`^.[5]RK!4
M2+8WF;4HF:X<ZYD-FK)(6YEB>K.A:;;D&K'4LH$T&YI;B[?2"IU@*W?B*:8_
MZ[>#Z[%Z>+6"RZ88*Y_@F94YX*\FZ761.[!@F9C:5[D(^[%;H+F[6HG2Y[F_
M:G=^*;IL2[G%:HI?ZKG*BHZA6ZQGJH*LRZ:S:[.*Y[DHNY+4@KM1>XN\JZ<;
MB[HSNY;,][M]Z[DY.[29NZZ$>[O,B[CT%ZW(2[N5.K'C9W9<>;T+RZZ]QWAF
MM[E-B(#?.W?'&`/CBZ6!J;UQRKTP.+YUJKSJ.XOEZ[Z">HOF>YB`ZWOCV[1B
MBH'>B[7:2(#[6[_B6[?LZJ[Y,;YRVZ3^5\#J:+3;>+\/K*`2W+%>BYKZ6ZQX
MJ8(5G+%"&Z/_6[$S6*^V-[ZS^7@(V<$D.YK1VL')J[L)_+RARH@.'+30ZZ$A
M;,,6R;DN_)X"7+T_V,+CV[6JV[YAJ['!6<)'_,%%&<-KBY/ZF,-IFYQ.W*=8
MJ<2+^[8PW,&'.\-S&;]_"[--F<%9#)7A"\93B<(_G,58.7Z-!ZNV]WNE>L`P
M*,=1V\)V#+RBZL8/2[R,E\=]&P,Q2)@.Z)_Y,<B+*J)\+,(WW)Z+;'SX*L@%
M&<CD1\CMZ7N5G,B.',<OR\1[S,G#"ZP$F,F4+,.F:,B2/*]>W*X(^'LO>J9X
*?*\0F\KZ.K&:`LB.
`
end
-- 
Life is a process, not a principle, a mystery to be lived, not a problem to
be solved.
- Gerard Straub, television producer and author (stolen from Frank Herbert??)
-- 
Matthias Urlichs  --  urlichs@smurf.sub.org -- urlichs@smurf.ira.uka.de   /(o\
Humboldtstrasse 7 -- 7500 Karlsruhe 1 -- Germany  --  +49-721-9612521     \o)/

orakel@rzmain.rz.uni-ulm.de (Framstag) writes:
> [Die 12 moeglichen Pentominos sollen] in einem 10*6 grossen Rechteck
> untergebracht werden, so dass dieses vollstaendig ausgefuellt wird.
> 
> 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.

Mein Programm behauptet, es seien 4678.  Ich bin etwas skeptisch.
Wir sind bestimmt nicht die ersten, die mit diesen Pentominos
herumspielen -- es ist gut moeglich, dass Clarke aus irgendeiner
mathematischen Kuriositaetensammlung die richtige Loesung kannte.

Gardner?  Hofstaedter?  rec.puzzles?

urlichs@smur@.sub.or= (Matthias Urlichs) writes:
> wenn freie Stelle mit > 6 belegten Plaetzen drumherum gefunden
>      Situation unmoeglich, Return

Hm.  Erklaer' das mal genauer.

Jutta

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)/

In article <1992Sep12.175946.14706@wega.rz.uni-ulm.de>, Framstag writes:

> 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

Aehm...... sind das nicht sechs Quadrate? ;)


	Party on
		Henning

-- 
-- Henning Schmiedehausen --- barnard@forge.erh.sub.org --- A 3000/25 --- __
...and in deep shelters lurk below, sub-regional control      | Home __  ///
who sympathize but cannot help to mend your body or your soul |of the\\\///
self-appointed guardians of the race... - Jethro Tull, A      | BSF   \XX/

In de.comp.misc, article <1992Sep14.004826.23022@cs.tu-berlin.de>,
  jutta@opal.cs.tu-berlin.de (Jutta Degener) writes:
> 
> Mein Programm behauptet, es seien 4678.  Ich bin etwas skeptisch.
> Wir sind bestimmt nicht die ersten, die mit diesen Pentominos
> herumspielen -- es ist gut moeglich, dass Clarke aus irgendeiner
> mathematischen Kuriositaetensammlung die richtige Loesung kannte.
> 
Hmmm...

> urlichs@smurf.sub.org (Matthias Urlichs) writes:
> > wenn freie Stelle mit > 6 belegten Plaetzen drumherum gefunden
> >      Situation unmoeglich, Return
> 
Aua. Kommando zurueck. Danke dass du meinen Fehler gefunden hast.  ;-)
Was ich eigentlich tun wollte, ist "wenn freie Stelle mit belegten Plaetzen
links+rechts+oben+unten". Weil alle Teile horizontal oder vertikal verbunden
sind, passt da logischerweise kein Pentomino mehr rein.

Bei mir sind's jetzt 2339 Pentominos. Das passt zu deinen 4678 unter der
Voraussetzung, dass du einen symmetrischen Fall uebersehen hast..?

-- 
"It is not enough to discover how things seem to seem.
 We must discover how things really seem."
                    -- Niels Bohr
-- 
Matthias Urlichs  --  urlichs@smurf.sub.org -- urlichs@smurf.ira.uka.de   /(o\
Humboldtstrasse 7 -- 7500 Karlsruhe 1 -- Germany  --  +49-721-9612521     \o)/

In <1992Sep14.004826.23022@cs.tu-berlin.de> jutta@opal.cs.tu-berlin.de writes:

> Mein Programm behauptet, es seien 4678.  Ich bin etwas skeptisch.

was hast Du denn fuer ein Programm? *NEUGIER*
Schieb doch mal rueber :-)
Ich bin immer noch interessiert an der Frage, ob sich ueberhaupt beweisen
laesst WIEVIELE Loesungen es gibt. Die nexte Frage ist dann die nach den
Loesungen an sich.

Das Ausprobierprogramm von Matthias ist ja ganz nett, aber damit bekomme in
endlicher Zeit nicht alle Loesungen und schon gar nicht "Last solution
found. Program stopped" :-)


> Wir sind bestimmt nicht die ersten, die mit diesen Pentominos
> herumspielen -- es ist gut moeglich, dass Clarke aus irgendeiner
> mathematischen Kuriositaetensammlung die richtige Loesung kannte.
> 
> Gardner?  Hofstaedter?  rec.puzzles?

rec.puzzles waere mein nexter Anlauf gewesen. Ich war aber ersma zu faul
alles in sauberem Englisch zu formulieren, so dass ich auch nicht
missverstanden werde. An meiner Anfrage hier hab ich schon lang genug
gefeilt, dass sie nicht mehrdeutig war. Ich bin kein native math-speaker
:-)


\  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."  \

urlichs@smurf.sub.org (Matthias Urlichs) writes:

>In de.comp.misc, article <1992Sep14.004826.23022@cs.tu-berlin.de>,
>  jutta@opal.cs.tu-berlin.de (Jutta Degener) writes:
>> 
>> Mein Programm behauptet, es seien 4678.  Ich bin etwas skeptisch.
>> Wir sind bestimmt nicht die ersten, die mit diesen Pentominos
>> herumspielen -- es ist gut moeglich, dass Clarke aus irgendeiner
>> mathematischen Kuriositaetensammlung die richtige Loesung kannte.

Berlekamp, Conway und Guy behaupten auf Seite 787 der Winning Ways:
(2nd corrected printing 1983)

  Such problems are peculiar susceptible to idle computers and the
  6x10 pentomino rectangle was one of the first to be tackled in
  this way when C.B.Haselgrove found its 2339 solutions in 1960.

Und eine Seite vorher steht:

  A domino is made of two squares stuck together, so S.W. Golomb has
  suggested the words tromino, tetromino etc. for the figures that 
  can be made by sticking 3, 4 or more equal squares together.
  He has registered the particular names pentomino (5 squares) 
  and polyomino (n squares) as trade-marks. Unfortunatly few of
  the puzzles that have been proposed have hidden secrets, so they
  yield to nothing better then trial and error (or systematic
  search).

>Bei mir sind's jetzt 2339 Pentominos. Das passt zu deinen 4678 unter der
>Voraussetzung, dass du einen symmetrischen Fall uebersehen hast..?

2339 scheint ja zu stimmen. Wann hat denn Clarke seinen Roman geschrieben ?

Hope this helps, -KK

---
------------------------------------------------------------------------------
    Klaus Kalb     | mail :  IMMD1 / Martenstr. 3 / W-8520 Erlangen / Germany 
 Werch ein Illtum  | email:  kskalb@immd1.informatik.uni-erlangen.de   
------------------------------------------------------------------------------