🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

🏠 Home 📰 News 🗂️ Usenet Search 🔑 Login 📝 Register
Article View: de.comp.misc
Article #134
Back to de.comp.misc Previous Next

Re: Pentominos: eine deLuxe Denksportaufgabe

#134
From: Matthias Urlichs
Date: Sun, 13 Sep 1992 14:14
209 lines
10732 bytes 
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)/
Technical Details
Message-ID: <18vibsINN4tk@smurf.smurf.sub.org>
Path: arc1-ca.pugleaf.net!sparky!uunet!elroy.jpl.nasa.gov!sdd.hp.com!nigel.msen.com!yale.edu!ira.uka.de!smurf.sub.org!news
References: <1992Sep12.175946.14706@wega.rz.uni-ulm.de>

Show Full Headers
Complete Article Headers 
Path: arc1-ca.pugleaf.net!sparky!uunet!elroy.jpl.nasa.gov!sdd.hp.com!nigel.msen.com!yale.edu!ira.uka.de!smurf.sub.org!news
From: urlichs@smurf.sub.org (Matthias Urlichs)
Newsgroups: de.comp.misc
Subject: Re: Pentominos: eine deLuxe Denksportaufgabe
Date: 13 Sep 1992 16:14:20 +0200
Organization: University of Karlsruhe, FRG
Lines: 209
Message-ID: <18vibsINN4tk@smurf.smurf.sub.org>
References: <1992Sep12.175946.14706@wega.rz.uni-ulm.de>
NNTP-Posting-Host: 127.0.0.1
Reply to Parent Message