Subject: Pentacube Packing Date: Wed, 16 Dec 1998 05:20:41 GMT From: path@multipro.NOcomSPAM.au (Patrick Hamlyn) Newsgroups: rec.puzzles In case anyone is still struggling with it, I just finished searching for a packing of all 29 pentacubes into this shape which I posted here as a challenge a year or two ago (use monospaced font): level 1 level 2 level 3 level 4 level 5 xxx xxx xxx xxx xxx xxx x xxx xxx xxx x xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxxxxxxxxxx xxx xxx xxx x x x x xxx xxx xxx xxx xxx xxx xxx xxx xxx x xxx xxx xxx xxx xxx xxx x xxx xxx xxx This is five 3x3x3 cubes, placed like the X-pentomino but with one minicube spacing them, and joined to one another at the center of each face by one minicube, then each 3-cube has also one extra mini-cube at top centre, except the middle one, which has two. As expected, there were no solutions. Thanks to michael reid at Brown University for suggestions which chopped the solving time from many years down to around 15 hours. -- Patrick Hamlyn, Multiprogramming Pty Ltd Posting from Perth, Windsurfing capital of Australia ---------------------------------------------------------------------------- This figure must fall apart into: Torsten Sillke, 1998-12-16 figure A: four times xxx xxx xxx ... xxx xxx xxx .x. xxx xxx xxx ... x x figure B: xxx x.x xxx ... ... xxx .x. xxx .x. .x. xxx x.x xxx ... ... Impossible proof: Figures A and B are subfigures of figure C: x o ... ... xox ooo xox ... ... .x. .o. ooo xooooox ooo .o. .x. ... ... xox ooo xox ... ... o x There are 'x' marked cubes in figure C. The shapes A and B as subsets of C have 9 marked cubes. In total all four times A and B have 5*9=45 marked cubes. How many marks can be fitted with each pentacube? The following table gives the maximum for each piece. The sum of these maximal values is 44. Therefore it is impossible to fit all 45 marked cubes. 1 1 1 3 2 2 2 2 1 1 1 1 1 1 1 1 2 2 0 2 2 1 1 2 2 2 2 2 2 :max x-mark 0 1 2 3 0 1 2 0 1 2 3 4 5 6 7 0 1 2 0 1 0 1 0 1 2 0 1 2 0 :b Pentacube 1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 4 4 4 5 5 6 6 7 7 7 8 8 8 9 :a 10a+b Computing without weight functions: ----------------------------------- How many subset pack shape A? There are 66136 different subsets, which pack A. It took me 10 minutes to find them. Which subset build shape B? There are 66 subsets of the pentacubes which pack B. 12 13 21 22 31 12 13 22 42 81 12 21 71 81 90 21 22 37 41 81 12 13 21 22 32 12 13 22 42 90 12 22 41 81 90 21 22 37 41 90 12 13 21 22 41 12 13 22 60 90 12 22 42 81 90 21 22 37 42 81 12 13 21 22 42 12 13 22 61 81 12 22 60 81 90 21 22 37 42 90 12 13 21 31 81 12 13 22 61 90 12 22 72 81 90 21 22 41 61 90 12 13 21 32 81 12 13 41 81 90 13 21 33 80 90 21 22 42 61 90 12 13 21 32 90 12 13 42 81 90 13 21 37 80 81 21 33 41 81 90 12 13 21 41 81 12 13 60 81 90 13 21 61 81 90 21 37 41 81 90 12 13 21 41 90 12 13 61 81 90 13 21 71 80 90 21 37 42 81 90 12 13 21 42 90 12 21 22 41 81 13 22 34 80 90 21 41 71 81 90 12 13 21 60 90 12 21 22 42 81 13 22 37 80 81 21 80 81 82 90 12 13 21 61 81 12 21 22 60 90 13 22 61 81 90 22 34 42 81 90 12 13 21 61 90 12 21 22 71 81 13 22 72 80 90 22 37 41 81 90 12 13 22 31 81 12 21 22 72 81 13 41 51 81 90 22 37 42 81 90 12 13 22 31 90 12 21 41 81 90 13 42 51 81 90 22 42 72 81 90 12 13 22 32 81 12 21 42 81 90 13 61 80 81 90 22 80 81 82 90 12 13 22 41 90 12 21 60 81 90 Pieces not used in any subset are: 10, 11, 20, 30, 35, 36, 40, 50, 70. The most time consuming part is the partitioning step. Here you can use further tricks. As B don't use 9 different pentacubes these must be used by the A shapes. Therefore at least 3 of the 9 pentacubes {10, 11, 20, 30, 35, 36, 40, 50, 70} must be in one subset of A (by the pigeonhole principle). There are only 382 subsets of this kind. But backtracking still takes 3.5 hours. The pentacubes: (the number are the K"unzell Notation) x x x x x x x x x x x x x x x x x x x x 10 11 12 13 x x z z x x x x x x x x x 20 21 22 x x z z x x y y x x x x x x z x x z z x x z z x x x x x x x x z 30 31 32 33 34 35 36 37 x x x x x x x x x x z z x 40 41 42 x x x x x z x x x 50 51 x x x x x x x z x 60 61 x x x x x x x x z z x x x 70 71 72 x x x z x x x x x x x x z 80 81 82 x x x x x 90 The used notation has the advantage over the ascanding numbering, to group the pentacubes. It is derived from their form. The pieces 10, 20, 30, 40, 60, and 70 are easy to recognize, as the form of the piece has similarities with the first digit. The no. 50 reminds at the 5 points on the dice.