TAOCP 7.2.2.1 Exercise 344
The packing problem is an exact cover instance in which each of the 25 solid Y pentominoes contributes an option consisting of the 5 unit cubes it occupies, and each unit cube of the $5\times 5\times...
Section 7.2.2.1: Dancing Links
Exercise 344. [10] $[10]$ In how many different ways can a $5 \times 5 \times 5$ cube be packed with 25 solid Y pentominoes? (See Fig. 73.) Discuss how to remove the 48 symmetries of this problem.
Verified: no
Solve time: 1m18s
The packing problem is an exact cover instance in which each of the 25 solid Y pentominoes contributes an option consisting of the 5 unit cubes it occupies, and each unit cube of the $5\times 5\times 5$ container is an item that must be covered exactly once. A direct application of Algorithm X or dancing links yields the total number $N$ of raw solutions, where each solution corresponds to a placement of the 25 pieces without regard to geometric symmetries of the cube.
The symmetry group of the cube acts on the set of packings by rigid motions of the $5\times 5\times 5$ cube. This group has $24$ orientation-preserving elements and $24$ orientation-reversing elements, for a total of $48$. If reflections are considered equivalent, then the relevant group has order $24$; if mirror images are also identified, then the full group of order $48$ is used. To remove the $48$ symmetries one either divides the raw count $N$ by the size of each orbit under this group action, or imposes a canonical constraint such as fixing a distinguished corner of the cube and forcing a chosen orientation of the Y pentomino that occupies it, thereby restricting the search space so that each equivalence class is represented exactly once. The final number of essentially distinct packings i