Klodse-pakke-fest

Bill Cutlers >Block-Packing Jambalaya=

oversat af Ole Poul Pedersen


Gennem årene har min hovedinteresse været tømmerknuder, men der er en anden lille kategori af puslerier, som tiltrækker mig særligt. Det er 3-dimensionel pakning i æsker, hvor æsken og alle brikkerne er rektangulære legemer. Antallet af sådanne puslerier, som jeg har kendskab til, er ret lille, men de
>tricks= eller særlige indslag, som puslerierne bruger, er mange og varierede. Jeg kender ingen anden lille gruppe af puslerier, som spænder over så stor en rigdom af idéer.

Her præsenteres 11 sådanne puslerier med pakning af klodser. Trickene ved de fleste puslerier omtales, men komplette løsninger gives ikke.

Puslerierne er grupperet efter, om der er hulrum i det samlede pusleri, og efter, om alle brikkerne er ens eller forskellige.

For hvert pusleri er det samlede antal brikker i parenteser. Pusleriets opfinder, designdato og fremstiller er angivet i det omfang, de er kendt.

I. Ingen hulrum, alle brikker ens

AEr disse puslerier ikke trivielle?@ spørger du. Jo, du er ikke langt fra at have helt ret, men der er nogle interessante problemer. David Klarner har en gennemgribende diskussion heraf i [5]. Følgende er mine favoritter:

  (1) unavngivet (44) (Singmaster-Klarner):
      Æske:    8 x 11 x 21
      Brikker: (44) 2 x 3 x 7

  (2) unavngivet (45) (de Bruijn):
      Æske:    5 x 6 x 6
      Brikker: (45) 1 x 1 x 4

II. Ingen hulrum, begrænset antal brik-typer

De puslerier, jeg kender i denne kategori, følger et fælles princip: Grundlæggende er der to slags brikker, et stort antal af den ene slags og et begrænset antal af den anden. De sidstnævnte er mindre og lettere at bruge, men må bruges effektivt for at løse pusleriet. Løseren må beslutte nøjagtigt hvor, det andet sæt brikke skal placeres, og så er resten let.

  (3) unavngivet (9) (Slothouber-Graatsma):
     
Æske:    3 x 3 x 3
      Brikker: (3) 1 x 1 x 1, (6) 1 x 2 x 2

  (4) unavngivet (18) (John Conway):
      Æske:    5 x 5 x 5
      Brikker: (3) 1 x 1 x 3, (1) 1 x 2 x 2,
               (1) 2 x 2 x 2, (13) 1 x 2 x 4

I det første af disse er de tre enkeltterninger indlysende lette at anbringe, men de må ikke spildes. Ved at analysere >skakbrætmønstre= af lagene i æsken er det let at se, at terningerne skal anbringes diagonalt. I det det andet design må de tre 1x1x3-brikker bruges sparsomt. Resten af brikkerne virker - selv om de ikke er helt ens - på samme måde som 1x2x2-brikkerne i det første pusleri. Se [2] eller [5] for flere oplysninger.

III. Ingen hulrum, hovedsageligt forskellige brikker

     (5) Quadron (18) (Jost Hanny, Naef):
       Æske 1:  5 x 7 x 8
       Brikker: 2 x 3 x 3, 2 x 3 x 5, 2 x 4 x 5, 2 x 4 x 6,
                3 x 3 x 4, 3 x 3 x 5, 3 x 3 x 7
       Æske 2:  5 x 7 x 10
       Brikker: 1 x 3 x 4, 1 x 3 x 6, 1 x 3 x 7, 1 x 3 x 10,
                1 x 4 x 5, 2 x 3 x 4, 2 x 3 x 6, 2 x 3 x 7,
                2 x 4 x 7, 3 x 3 x 3, 4 x 4 x 4
       Æske 3:  7 x 9 x 10
       Brikker: Alle 18 brikker fra de to første æsker

Quadron bruger ingen specielle tricks, som jeg kender, men det udgør et pænt sæt puslerier. De 18 brikker er alle forskellige, og de tre æsker giver en bred række sværhedsgrader. Den lille æske er meget let. De 7 brikker kan lægges i æsken på 10 forskellige måder, når man ikke medregner rotationer og/eller spejlinger. En fuldstændig, streng analyse kan gøres ved håndkraft på et kvarters tid. Æsken i mellemstørrelse er svær - der er kun én løsning. Den store æske er mellemsvær og har mange løsninger.

Quadron kan også være en god tilgang til området for computeranalyse af puslerier og begrænsningerne i sådanne programmer. Programmøren kan bruge algoritmer, som bruges til pentomino-problemer, men der er mere effektive algoritmer, som kan bruges til klodsepakninger. Jeg skrev et sådant program på min første computer, en Commodore 64. Ved brug af farvegrafik viste programmet æskens status på ethvert tidspunkt. Jeg farvede brikkerne i et virkeligt pusleri for at matche displayet. Resultatet var en fantastisk demonstration af, hvordan en computer kan bruges til at løse sådant et pusleri. Commodore 64 er en vidunderligt langsom maskine - når programmet bliver kørt i en BASIC-fortolker, bliver en brik tilføjet eller fjernet fra æsken en gang i sekundet! Ved brug af oversat BASIC stiger hastigheden til 40 gange i sekundet.

Når man kører disse programmer på mere kraftfulde computere, er der en overvældende forskel på de tre æsker: Den første æske kan analyseres fuldstændigt på en lille brøkdel af et sekund. Den anden anden æske kan analyseres på et minuts tid på en mainframe computer. I begyndelsen af 1996 lavede jeg en fuldstændig analyse af den tredie æske. Der er 3.450.480 løsninger, når rotationer og spejlinger ikke tælles med. Analysen blev udført på omkring 20 kraftige IBM workstations. Den samlede CPU-tid, som blev brugt, var omkring 8500 timer, hvilket svarer til et år på en enkelt maskine. Ved kørslernes afslutning havde maskinerne konstrueret 22 billion forskellige delvist fyldte æsker.

   (6) Parcel Post Puzzle (18) (Ukendt designer;
                kopieret fra model i Abel Garcia
s samling):
       Æske:    6 x 18 x 28
       Brikker: 2 x 4 x 9, 2 x 5 x 18, 2 x 5 x 21, 2 x 6 x 7,
                2 x 6 x 10, 2 x 6 x 13, 2 x 7 x 18, 2 x 8 x 18,
                2 x 9 x 11, 2 x 9 x 13, 2 x 10 x 11, 2 x 11 x 11,
                (2) 2 x 5 x 9, (2) 2 x 7 x 8, (2) 2 x 7 x 13

Da alle brikkerne har samme tykkelse og æskens dybde svarer til 3 tykkelser, er det fristende at løse pusleriet ved at danne 3 lag brikker. Der kan dannes et eller to selvstændige lag, men processen kan ikke gøres færdig. Løsningen inddrager brugen af følgende indlysende trick (er det et oksymoron?): En/flere brik(ker) lægges sidevis i æsken. Af de 18 brikker er 10 for brede til at passe ind sidevis og 4 er 5 brede, hvilket ikke er godt til formålet. Det efterlader 4 brikker, som kunne lægges sidevis. Der er 4 løsninger på pusleriet, alle meget ens, og i alle er 3 af de 4 brikker lagt sidevis.

       (7) Boxed Box (23) (Cutler, 1978, Bill Cutler Puzzles):
       Æske:    147 x 157 x 175
       Brikker: 13 x 112 x 141, 14 x 70 x 75, 15 x 44 x 50,
                16 x 74 x 140, 17 x 24 x 67, 18 x 72 x 82,
                19 x 53 x 86, 20 x 40 x 92, 21 x 52 x 65,
                22 x 107 x 131, 23 x 41 x 73, 26 x 49 x 56,
                27 x 36 x 48, 28 x 55 x 123, 30 x 54 x 134,
               
31 x 69 x 78, 33 x 46 x 60, 34 x 110 x 135,
                35 x 62 x 127, 37 x 83 x 121, 38 x 42 x 90,
                45 x 68 x 85, 57 x 87 x 97

Brikkernes dimensioner er alle forskellige tal. Brikkerne passer i æsken uden ekstra rum. 23 er det mindste antal, for hvilket det kan gøres. Der er mange andre løsninger med 23 brikker, som er kombinatorisk forskellige fra det ovennævnte design. Næsten 15 år efter fascinerer pusleriet mig stadigvæk. Se [1] eller [3] for flere oplysninger.

IV. Hulrum, brikkerne ens eller ensartede

    (8) Hoffman=s Blocks (27) (Dean Hoffman, 1976):
        Æske:    15 x 15 x 15
        Brikker: (27) 4 x 5 x 6

Dette lyder som et let pusleri, men er det ikke. Det ekstra rum gør et væld af nye muligheder tilgængelige. Der er 21 løsninger, hvoraf ingen indeholder symmetri eller mønstre. Brikkernes mål kan ændres. De kan være hvilke som helst 3 forskellige tal, hvor det mindste er større end 1/4 af summen. Æsken er en terning, hvis side er lig med summen. Jeg kan lide de nævnte mål, fordi de lokker løseren til at stable brikkerne i 3 lag efter det midterste mål. Se [4].

    (9) Hoffman Junior (8) (Nob Yoshigahara, 1986,
                 Hikimi Puzzland):
        Æske:    19 x 19 x 19
        Brikker: (2) 8 x 9 x 10, (2) 8 x 9 x 11, (2) 8 x 10 x 11,
                 (2) 9 x 10 x 11

V. Hulrum, brikkerne forskellige

   (10) Cutler=s Dilemma, Forenklet (15) (Cutler, 1981,
                 Bill Cutler Puzzles):
        Æske:    40 x 42 x 42
        Brikker: 9 x 19 x 26, 9 x 20 x 20, 10 x 11 x 42,
                 10 x 12 x 26, 10 x 16 x 31, 10 x 19 x 25,
                 10 x 19 x 26, 11 x 11 x 25, 11 x 12 x 42,
                 11 x 16 x 19, 11 x 17 x 30, 11 x 19 x 25,
                 12 x 17 x 19, 16 x 19 x 21, 17 x 19 x 21

Det oprindelige design på Cutler=s Dilemma havde 23 brikker, og var konstrueret ud fra ovennævnte grundversion ved at skære nogle af brikkerne i 2 eller 3 mindre brikker. Slutresultatet var et pusleri, som er uhyre svært. Jeg vil ikke sige mere om dette design bortset fra, at det involverede trick er forskelligt fra alle de, der er brugt ved de andre designs i denne artikel.

VI. Diverse

   (11) Melting Block (8-9) (Tom O=Beirne):
        Æske:    58 x 88 x 133
        Brikker: 19 x 29 x 44, 19 x 29 x 88, 19 x 58 x 44,
                 38 x 29 x 44, 19 x 58 x 88, 38 x 29 x 88,
                 38 x 58 x 44, 38 x 58 x 88, og en kopi
                 af 19 x 29 x 44

Melting Block er mere et paradox end et pusleri. De otte brikker kan let sættes sammen til et rektangulært legeme på 57 x 87 x 132. Det passer i æsken med lidt plads hele vejen rundt, men for den tilfældige tilskuer ser det ud til at fylde æsken helt ud. Når den niende brik lægges til de andre, kan brikkerne flyttes rundt og danne et nyt rektangulært legeme på 58 x 88 x 133. (Denne anden konstruktion er lidt mere vanskelig). Det er et godt pusleri af vise Afolk, der ikke pusler@ og er en af mine favoritter.

For resten er ét af de ovennævnte puslerier uløseligt. Jeg vil ikke sige hvilket (det skulle være let at finde). Det er et værdifuldt våben i enhver pusle-samlers arsenal. Pak alle brikkerne, bortset fra én, i æsken, og sørg for, at det uudfyldte rum er stabilt og gemt i bunden. Sæt æsken på din pusle-hylde med den tiloversblevne brik skjult bag ved æsken. Nu er du klar til dit næste møde med en kedsommelig pusle-nød. (Nej, læsere, detter er ikke et andet oxymoron, men nærmere en tautologi til de 99% af verden, som aldrig ville have begyndt at læse denne artikel.) Tag æsken og den sidste brik med begge hænder og hold omhyggeligt den frafaldne brik skjult. Vis den fyldte æske til dit offer, og lad så brikkerne, inklusive den i din hånd, falde på gulvet. Det skulle holde ham beskæftiget i en rum tid!

Referencer

[1] W. Cutler, ASubdividing a Box into Completely Incongruent Boxes@, J. Recreational Math., 12(2), 1979-80, pp. 104-111.

[2] M. Gardner, Mathematical Games spalte i Scientific American, Februar 1976, pp. 122-127.

[3] M. Gardner, Mathematical Games spalte i Scientific American, Februar 1979, pp. 20-23.

[4] D. Hoffman, APacking Problems and Inequalities@, i The Mathematical Gardner, redigeret af D. Klarner (Wadsworth International, 1981), pp. 212-225.

[5] D. Klarner, ABrick-Packing Puzzles@, J. Recreational Math., 6(2), Spring 1973, pp. 112-117.

Skrevet i anledning af pusleri-udstillingen i Atlanta International Museum of Art and Design i januar 1993. Ændret og præsenteret ved AA Gathering for Gardner II@ i Altlanta, januar 1996. Yderligere ændringer april 1998.