Niels L. Ellegaard skrev:
> Hvordan mon man laver et hurtigt program til at regne det ud? Her er
> en halv ide
>
> Man kan starte med at numerere alle de mulige konfigurationer af et
> enkelt lag. Derefter kan man begynde at undersøge om to lag kan limes
> sammen. Eksempelvis kan de følgende to lag godt limes sammen til en
> samenhængende figur på fire klodser
>
> #### #### <--- lag 1
> #### #### <--- lag 2
>
> Følgende to lag kan godt være del af en sammenhængende figur 1), men
> de kan også være en del af en figur der ikke hænger sammen 2)
>
> #### #### <--- lag 1
> #### #### <--- lag 2
>
> 1) Her en den sammenhængende figur, der indeholder disse to lag
>
> ####
> #### #### <--- lag 1
> #### #### <--- lag 2
> ####
>
> 2) Her er til gengæld en usammenhængende figur, der indeholder de
> samme to lag
>
> ####
> #### #### <--- lag 1
> #### #### <--- lag 2
> ####
>
> Man kan skrive problemet om til grafteori. Situation 1) svarer
> eksempelvis til følgende graf (I denne figur svarer hver stjerne til
> en klods og stjernerne er forbundne med streger, hvis de tilsvarende
> klodser hænger sammen... sådan en figur hedder en graf).
>
>
> *
> / \
> * *
> | |
> * *
> |
> *
>
> Det burde være muligt at bruge den ovenstående analyse til at lave et
> smart program, men jeg kan ikke finde ud af hvordan man laver en smart
> datastruktur. Er der ikke en datalog på linien der kan hjælpe?
>
> Så vidt jeg kan se på google, hedder graferne "layered
> graphs". Pointen er at en klods i lag n kan kun kan hænge sammen med
> en klodser i lagene n-1 og
> n+1.
http://www.nist.gov/dads/HTML/layeredgraph.html
>
>
> Niels
Sådan har jeg ikke selv gjort. Den metode du nævner minder mere om Søren
Eilers'. Jeg har indført et koordinatsystem og ladet klods[1] starte i
(0,0,0,1,3). Det betyder, at dens hjørne med lavest (x,y)-koordinat ligger i
(0,0) og at dens udstrækning i x- hhv. y-aksens retning er (1,3) i forhold
til dens hjørne med lavest (x,y)-koordinat.
Herefter undersøger programmet hvor klods[2] kan sidde. Alle stederne lagres
i et array. Den først fundne placering bliver den aktuelle, dvs. at vi nu
har en konstruktion af 2 klodser. Den vil hedde 1: (0,0,0,1,3), 2:
(-1,-3,1,3).
Herefter findes alle placeringer af klods[3] på konstruktionen af 2 klodser.
Den første vælges og en konstruktion på 4 klodser haves. Således fortsættes
indtil alle den 6. klods' placeringer på den første konstruktion af 5
klodser er talte. Nu vælger den 5. klods sin anden placering og igen tælles
alle placeringer af den 6. klods. Når den 5 klods har stået på alle sine
placeringer på konstruktionen med 4 klodser vælger den 4. klods sin anden
placering. På denne måde fortsættes vha. backtracking.
Det tager mit program ca. 3 timer at udregne alle konstruktionerne med 6
klodser. Med 7 har Søren Eilers og jeg anslået, at der er 70-80 mia. Der er
den ulempe ved min metode at nogen konstruktioner findes flere gange. Lad bk
være antallet af klodser i konstruktionens 1. lag. Hvis en konstruktion ikke
har nogen rotationssymmetri tælles den med 2*bk gange. Hvis den har 180
graders rotationssymmetri tælles den med bk gange. Hvis den har 90 graders
rotationssymmetri tælles den med bk/2 gange. Konstruktioner med 90 graders
rotationssymmetri kan for u-kvadratiske klodser kun laves hvis 4 går op i
antallet af klodser og hvis antallet af klodser er større end eller lig 8.
Det tog mit program en uge at tælle de 29446248496 måder man kan sætte 11
1x2-klodser sammen med hinanden på. Jeg delte arbejdet op i 7 dele (de 7
positioner for 1. klodser) og brugte 3 pc'er til at arbejde på det i
døgndrift! Vi arbejder på at bestemme hvor mange måder 12 kan sættes sammen
på. Det kommer til at ligge på omkring 435 mia.
Søren Eilers og jeg er begge helt sikre på, at vores programmer virker, og
vi får de samme resultater for alle de antal klodser vi har sammenlignet,
til og med 6 2x4-klodser og 8 1x2-klodser.
Venligst
Mikkel Abrahamsen
(ham der var med i tv2-nyhederne)