Community Hub0 Subscribers
Community hub
Polycube
View on Wikipediafrom Wikipedia
A polycube is an orthogonal polyhedron formed by joining one or more equal cubes face to face. Polycubes are the three-dimensional analogues of the planar polyominoes. The Soma cube, the Bedlam cube, the Diabolical cube, the Slothouber–Graatsma puzzle, and the Conway puzzle are examples of packing problems based on polycubes.[1]
Enumerating polycubes
[edit]
Like polyominoes, polycubes can be enumerated in two ways, depending on whether chiral pairs of polycubes (those equivalent by mirror reflection, but not by using only translations and rotations) are counted as one polycube or two. For example, 6 tetracubes are achiral and one is chiral, giving a count of 7 or 8 tetracubes respectively.[2] Unlike polyominoes, polycubes are usually counted with mirror pairs distinguished, because one cannot turn a polycube over to reflect it as one can a polyomino given three dimensions. In particular, the Soma cube uses both forms of the chiral tetracube.
Polycubes are classified according to how many cubical cells they have:[3]
| n | Name of n-polycube | Number of one-sided n-polycubes (reflections counted as distinct) (sequence A000162 in the OEIS) |
Number of free n-polycubes (reflections counted together) (sequence A038119 in the OEIS) |
|---|---|---|---|
| 1 | monocube | 1 | 1 |
| 2 | dicube | 1 | 1 |
| 3 | tricube | 2 | 2 |
| 4 | tetracube | 8 | 7 |
| 5 | pentacube | 29 | 23 |
| 6 | hexacube | 166 | 112 |
| 7 | heptacube | 1023 | 607 |
| 8 | octacube | 6922 | 3811 |
Fixed polycubes (both reflections and rotations counted as distinct (sequence A001931 in the OEIS)), one-sided polycubes, and free polycubes have been enumerated up to n=22. Specific families of polycubes have also been investigated.[4][5]
Symmetries of polycubes
[edit]As with polyominoes, polycubes may be classified according to how many symmetries they have. Polycube symmetries (conjugacy classes of subgroups of the achiral octahedral group) were first enumerated by W. F. Lunnon in 1972. Most polycubes are asymmetric, but many have more complex symmetry groups, all the way up to the full symmetry group of the cube with 48 elements. There are 33 different symmetry types that a polycube can have (including asymmetry).[2]
Properties of pentacubes
[edit]12 pentacubes are flat and correspond to the pentominoes. 5 of the remaining 17 have mirror symmetry, and the other 12 form 6 chiral pairs.
The bounding boxes of the pentacubes have sizes 5×1×1, 4×2×1, 3×3×1, 3×2×1, 3×2×2, and 2×2×2.[6]
A polycube may have up to 24 orientations in the cubic lattice, or 48, if reflection is allowed. Of the pentacubes, 2 flats (5-1-1 and the cross) have mirror symmetry in all three axes; these have only three orientations. 10 have one mirror symmetry; these have 12 orientations. Each of the remaining 17 pentacubes has 24 orientations.
Octacube and hypercube unfoldings
[edit]
The tesseract (four-dimensional hypercube) has eight cubes as its facets, and just as the cube can be unfolded into a hexomino, the tesseract can be unfolded into an octacube. One unfolding, in particular, mimics the well-known unfolding of a cube into a Latin cross: it consists of four cubes stacked one on top of each other, with another four cubes attached to the exposed square faces of the second-from-top cube of the stack, to form a three-dimensional double cross shape. Salvador Dalí used this shape in his 1954 painting Crucifixion (Corpus Hypercubus)[7] and it is described in Robert A. Heinlein's 1940 short story "And He Built a Crooked House".[8] In honor of Dalí, this octacube has been called the Dalí cross.[9][10] It can tile space.[9]
More generally (answering a question posed by Martin Gardner in 1966), out of all 3811 different free octacubes, 261 are unfoldings of the tesseract.[9][11]
Boundary connectivity
[edit]Although the cubes of a polycube are required to be connected square-to-square, the squares of its boundary are not required to be connected edge-to-edge. For instance, the 26-cube formed by making a 3×3×3 grid of cubes and then removing the center cube is a valid polycube, in which the boundary of the interior void is not connected to the exterior boundary. It is also not required that the boundary of a polycube form a manifold. For instance, one of the pentacubes has two cubes that meet edge-to-edge, so that the edge between them is the side of four boundary squares.
If a polycube has the additional property that its complement (the set of integer cubes that do not belong to the polycube) is connected by paths of cubes meeting square-to-square, then the boundary squares of the polycube are necessarily also connected by paths of squares meeting edge-to-edge.[12] That is, in this case the boundary forms a polyominoid.
Unsolved problem in mathematics
Can every polycube with a connected boundary be unfolded to a polyomino? If so, can every such polycube be unfolded to a polyomino that tiles the plane?
Every k-cube with k < 7 as well as the Dalí cross (with k = 8) can be unfolded to a polyomino that tiles the plane. It is an open problem whether every polycube with a connected boundary can be unfolded to a polyomino, or whether this can always be done with the additional condition that the polyomino tiles the plane.[10]
Dual graph
[edit]The structure of a polycube can be visualized by means of a "dual graph" that has a vertex for each cube and an edge for each two cubes that share a square.[13] This is different from the similarly-named notions of a dual polyhedron, and of the dual graph of a surface-embedded graph.
Dual graphs have also been used to define and study special subclasses of the polycubes, such as the ones whose dual graph is a tree.[14]
See also
[edit]References
[edit]- ^ Weisstein, Eric W. "Polycube." From MathWorld
- ^ a b Lunnon, W. F. (1972), "Symmetry of Cubical and General Polyominoes", in Read, Ronald C. (ed.), Graph Theory and Computing, New York: Academic Press, pp. 101–108, ISBN 978-1-48325-512-5
- ^ Polycubes, at The Poly Pages
- ^ "Enumeration of Specific Classes of Polycubes", Jean-Marc Champarnaud et al, Université de Rouen, France PDF
- ^ "Dirichlet convolution and enumeration of pyramid polycubes", C. Carré, N. Debroux, M. Deneufchâtel, J. Dubernard, C. Hillairet, J. Luque, O. Mallet; November 19, 2013 PDF
- ^ Aarts, Ronald M. "Pentacube". From MathWorld.
- ^ Kemp, Martin (1 January 1998), "Dali's dimensions", Nature, 391 (27): 27, Bibcode:1998Natur.391...27K, doi:10.1038/34063
- ^ Fowler, David (2010), "Mathematics in Science Fiction: Mathematics as Science Fiction", World Literature Today, 84 (3): 48–52, doi:10.1353/wlt.2010.0188, JSTOR 27871086, S2CID 115769478,
Robert Heinlein's "And He Built a Crooked House," published in 1940, and Martin Gardner's "The No-Sided Professor," published in 1946, are among the first in science fiction to introduce readers to the Moebius band, the Klein bottle, and the hypercube (tesseract).
. - ^ a b c Diaz, Giovanna; O'Rourke, Joseph (2015), Hypercube unfoldings that tile and , arXiv:1512.02086, Bibcode:2015arXiv151202086D.
- ^ a b Langerman, Stefan; Winslow, Andrew (2016), "Polycube unfoldings satisfying Conway's criterion" (PDF), 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2016).
- ^ Turney, Peter (1984), "Unfolding the tesseract", Journal of Recreational Mathematics, 17 (1): 1–16, MR 0765344.
- ^ Bagchi, Amitabha; Bhargava, Ankur; Chaudhary, Amitabh; Eppstein, David; Scheideler, Christian (2006), "The effect of faults on network expansion", Theory of Computing Systems, 39 (6): 903–928, arXiv:cs/0404029, doi:10.1007/s00224-006-1349-0, MR 2279081, S2CID 9332443. See in particular Lemma 3.9, p. 924, which states a generalization of this boundary connectivity property to higher-dimensional polycubes.
- ^ Barequet, Ronnie; Barequet, Gill; Rote, Günter (2010), "Formulae and growth rates of high-dimensional polycubes", Combinatorica, 30 (3): 257–275, CiteSeerX 10.1.1.217.7661, doi:10.1007/s00493-010-2448-8, MR 2728490, S2CID 18571788.
- ^ Aloupis, Greg; Bose, Prosenjit K.; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Douïeb, Karim; Dujmović, Vida; Iacono, John; Langerman, Stefan; Morin, Pat (2011), "Common unfoldings of polyominoes and polycubes", Computational geometry, graphs and applications (PDF), Lecture Notes in Comput. Sci., vol. 7033, Springer, Heidelberg, pp. 44–54, doi:10.1007/978-3-642-24983-9_5, hdl:1721.1/73836, ISBN 978-3-642-24982-2, MR 2927309.
External links
[edit]- Wooden hexacube puzzle by Kadon
- Polycube Symmetries
- Polycube solver Program (with Lua source code) to fill boxes with polycubes using Algorithm X.
- Kevin Gong's enumeration of polycubes
| Polyominoes | |
|---|---|
| Higher dimensions | |
| Others | |
| Games and puzzles | |
Polycube
View on Grokipediafrom Grokipedia
Fundamentals
Definition
A polycube is a three-dimensional orthogonal polyform composed of one or more congruent unit cubes, each with edge length 1, joined face-to-face to form a connected solid figure on the integer lattice .[1][7] The cubes must share entire faces for adjacency, ensuring the structure is face-connected rather than merely edge- or vertex-connected, which maintains the solidity and prevents disconnected or loosely bound components.[8] Polycubes generalize the concept of polyominoes, which are two-dimensional figures formed by joining unit squares edge-to-edge on a square lattice, to the third dimension using cubes instead of squares.[1] Similarly, they extend polyiamonds, built from equilateral triangles on a triangular grid, into volumetric forms while preserving the principle of lattice-based connectivity.[8] This analogy highlights polycubes as part of the broader family of polyforms, adapting planar tiling and puzzle challenges to spatial arrangements. The term "polycube" was coined by mathematician Solomon Golomb in the early 1950s, building on his foundational work with polyominoes.[9] Basic examples include the monocube (a single unit cube, order ), the dicube (two cubes joined face-to-face, ), and the two tricubes for : the straight chain (I-tricube) and the L-shaped or V-form (V-tricube).[8] These simple cases illustrate the combinatorial growth and geometric variety inherent in polycube construction.Types of Polycubes
Polycubes are classified into various types based on equivalences under translations, rotations, and reflections, which influence their enumeration and applications in combinatorial studies.[10] These distinctions arise from considering different symmetry operations, leading to counts that reflect varying levels of geometric freedom.[10] Fixed polycubes treat assemblies as distinct unless they can be superimposed solely by translation, thereby counting all rotational and reflectional orientations as separate entities.[10] This approach yields the highest numbers in enumerations, as it ignores any reorientations beyond rigid shifts in space.[10] Free polycubes consider two assemblies equivalent if one can be transformed into the other by any symmetry of the cube, including rotations and reflections, via the full octahedral group comprising 48 distinct orientations.[10] This classification counts unique shapes, treating mirror images as identical. One-sided polycubes consider assemblies equivalent under rotations only, via the rotation group of 24 orientations, thus distinguishing mirror-image forms that cannot be rotated into each other.[10] The count for one-sided polycubes can be derived from free polycubes by separating the chiral contributions, effectively doubling the count for chiral pairs while retaining achiral ones.[10] Chiral polycubes form non-superimposable mirror-image pairs under rotations alone, with such pairs first emerging at order 5 among the 29 one-sided pentacubes, where 6 pairs are identified alongside 17 achiral forms.[11] These chiral structures highlight the three-dimensional complexity beyond planar figures.[11] Plane polycubes constitute a subset confined to a single plane, consisting of cubes joined face-to-face in a monolayer, and are directly equivalent to polyominoes in two dimensions.[12] Their dual graph lies flat, emphasizing connectivity without depth.[12]Enumeration
Counting Methods
Counting free and one-sided polycubes relies on Burnside's lemma applied to the action of the cube's rotation group, which has order 24, by averaging the number of polycubes fixed by each group element to determine the number of distinct orbits under rotations.[10] This group-theoretic approach accounts for symmetries without generating all orientations explicitly, enabling the classification of polycubes up to rotational equivalence.[10] For fixed polycubes, which disregard symmetries, exhaustive enumeration is achieved using a generalization of Redelmeier's 1981 algorithm originally developed for polyominoes.[13] The method generates all connected sets of n unit cubes on the cubic lattice by systematically adding cubes to unoccupied faces while maintaining connectivity and using bounding techniques to prune invalid branches, allowing computation up to n=28 as of 2025.[14] Duplicates are avoided through canonical representations, such as normalizing the position of the minimal coordinate cube.[13] Computational enumeration typically employs recursive construction, starting from a single cube and iteratively attaching new cubes to exposed faces of the current structure, with backtracking to explore all valid extensions while ensuring no overlaps or disconnections occur.[13] This depth-first search, enhanced by symmetry-avoidance heuristics in later stages, efficiently traverses the exponential search space for small n. The number of fixed polycubes exhibits asymptotic growth of the form , where is an empirical constant derived from the known sequence values.[15] This subexponential correction term arises from the singularity structure of the generating function in lattice animal enumeration. The exponential growth in both time and space complexity severely limits exact counts beyond n=28, as the number of structures scales with .[15] For larger n or higher dimensions, approximations employ transfer-matrix methods, which encode boundary configurations to compute generating functions iteratively and estimate growth constants without full enumeration.Numbers for Small Orders
The enumeration of polycubes for small orders distinguishes between one-sided polycubes, where rotations are considered the same but reflections are distinct, and free polycubes, where both rotations and reflections are identified. These counts provide foundational data for understanding the rapid growth in the number of distinct polycube configurations as the order increases. The values up to are well-established, with extensions to higher available through computational sequences.[2][16] The following table summarizes the exact counts for one-sided and free polycubes for to :| One-sided | Free | |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 2 | 2 |
| 4 | 8 | 7 |
| 5 | 29 | 23 |
| 6 | 166 | 112 |
| 7 | 1023 | 607 |
| 8 | 6922 | 3811 |
Symmetries
Symmetry Operations
The symmetries applicable to polycubes are the isometries of the three-dimensional cubic lattice that map unit cubes to unit cubes, preserving adjacency and connectivity. These symmetries form subgroups of the octahedral symmetry group of the cube. The rotational symmetries, which preserve orientation, constitute the chiral octahedral group of order 24. This group includes the identity element; nine non-trivial rotations by , , and about three axes passing through the centers of opposite faces (three rotations per axis); eight rotations by and about four axes through opposite vertices (two rotations per axis); and six rotations by about axes through the midpoints of six pairs of opposite edges (one rotation per axis).[17][18] The full symmetry group of the cube, incorporating reflections and inversions, is the achiral octahedral group of order 48. This group extends the rotational symmetries by including mirror reflections across planes (such as those through opposite edges or faces) and improper rotations (rotoreflections), effectively doubling the order through the addition of an inversion center. For polycubes, these operations preserve the underlying lattice structure, ensuring that transformed polycubes remain valid assemblies of edge-connected unit cubes on the integer grid.[17][19] In the context of polycubes, these symmetry operations are used to determine equivalence classes of configurations, where two polycubes are considered identical if one can be mapped onto the other by a lattice-preserving isometry. This application is central to enumeration techniques, such as those employing Burnside's lemma to count distinct forms under group actions. Chiral polycubes exhibit handedness, where left- and right-handed enantiomers cannot be superimposed by rotations alone but can be by reflections; such pairs arise when the symmetry subgroup lacks reflection elements.[19][10] A representative example is the straight tricube, formed by three unit cubes aligned linearly along one axis. This polycube possesses the symmetry of the point group (order 16), including fourfold rotations about the long axis through the central cube's faces and twofold rotations and reflections perpendicular to it, rendering it achiral.[19]Classification by Symmetry
Polycubes are classified according to their symmetry groups under the actions of the octahedral group, resulting in 33 distinct symmetry types that account for rotations and reflections.[20] This classification system, developed by Lunnon in 1972, labels types using point group notations such as C1 for complete asymmetry (with only the identity operation, order 1) up to Oh for the full octahedral group (order 48), encompassing subgroups like Cs (mirror symmetry, order 2), C2 (180° rotation, order 2), and Td (tetrahedral with reflections, order 24).[10] Among high-symmetry cases, the solid cube polycube achieves Oh symmetry, as it is invariant under all 48 operations of the group.[20] Certain cross-shaped polycubes, such as the specific hexacube configuration invariant under tetrahedral rotations and diagonal reflections, exhibit Td symmetry with 24 elements, representing one of the maximal achiral subgroups short of full octahedral invariance.[20] The distribution of polycubes across these classes shows that the overwhelming majority are asymmetric (C1 class) for any given order n, with fixed polycube counts in this class dominating the totals—for instance, over 90% for n ≥ 6.[10] Chiral polycubes, which lack reflection symmetry and occur in enantiomeric pairs, become increasingly prevalent as n grows, with pair counts rising from 1 at n=4 to billions by n=16, reflecting the combinatorial explosion of handed configurations.[10] These symmetry classes are particularly useful in puzzle construction, where pieces with targeted symmetries simplify assembly constraints; for example, the Soma cube puzzle employs seven polycube pieces (one tricube and six tetracubes) featuring specific symmetries, including a chiral pair and several with mirror or rotational invariance, to form a 3×3×3 cube in 240 distinct ways (120 up to reflection).[21]Specific Polycubes
Tetracubes and Smaller
The monocube is the simplest polycube, consisting of a single unit cube. It serves as the fundamental building block for all larger polycubes and has no variations under rotation or reflection.[1] The dicube comprises two unit cubes joined face-to-face, forming a straight 1×1×2 rectangular prism. There is only one distinct dicube, as any orientation yields the same shape.[1][2] For tricubes, there are two free tricubes (considering rotations and reflections as identical) and two one-sided tricubes (considering rotations as identical but reflections as distinct). The straight tricube, often denoted I3, is a 1×1×3 rectangular prism. The other, denoted V3 or L-tricube, features three cubes where two form a base and the third attaches to the side of one, creating an L-shaped configuration in a 1×2×2 bounding volume. Both are planar, meaning they lie flat in one layer.[8][16][2] Tetracubes number eight in one-sided form and seven in free form, with the reduction due to a single chiral pair—the left- and right-handed skew tetracubes (denoted A4 and B4), which are non-superimposable mirror images. The one-sided tetracubes include five planar shapes analogous to tetrominoes extruded to unit thickness: the straight I4 (1×1×4 prism), the square O4 (2×2×1), the L4 (a 3×2×1 L-shape), the T4 (a 3×2×1 T-shape), and the skew S4 (a 3×2×1 Z-shape). The three non-planar tetracubes are the branched P4 (a central cube with three adjacent cubes along perpendicular faces, spanning 2×2×2), and the chiral pair A4/B4 (each resembling a twisted skew, with cubes stacked in a helical manner over 2×2×2). These shapes were enumerated early in polycube studies, with the chiral pair highlighting the introduction of handedness in 3D polyforms.[8][1][2][16] Physical models of tetracubes and smaller polycubes have been central to early polycube puzzles since the 1950s, when Solomon Golomb formalized the concept. For instance, the Soma cube puzzle, devised by Piet Hein in the 1930s and later analyzed with polycube theory, employs one tricube (V3) and six tetracubes (excluding the straight I4 and square O4, but including both A4 and B4 of the chiral pair, along with L4, T4, S4, and P4) to assemble a 3×3×3 cube in 240 distinct ways. These models demonstrate basic assembly properties, such as how the planar tetracubes fill rectangular layers while non-planar ones enable 3D interlocking.[8][22]Pentacubes
Pentacubes are polycubes composed of five unit cubes joined face-to-face. There are 23 distinct free pentacubes, where rotations and reflections are considered equivalent, and 29 one-sided pentacubes, which distinguish mirror images as distinct.[16][2] Of these, 12 are planar pentacubes, which lie entirely within a single plane and correspond directly to the 12 free pentominoes extruded to unit thickness.[23] The remaining 17 non-planar pentacubes exhibit greater three-dimensional complexity: 5 are achiral, possessing mirror symmetry, while the other 12 form 6 chiral pairs that lack such symmetry and are non-superimposable on their mirror images. Examples of chiral pentacubes include the F-pentacube, which resembles the letter F in certain orientations and is part of one such pair. The bounding boxes of pentacubes vary based on their configuration, ranging from the linear 5×1×1 for the straight-chain I-pentacube to more compact 3×2×2 for branched forms like the T-pentacube.[8] Each pentacube can adopt a number of distinct orientations under the 24-element rotation group of the cube, ranging from 3 for highly symmetric forms like the I- and X-pentacubes to 24 for asymmetric ones like the F- and Y-pentacubes, with the exact count determined by the stabilizer subgroup order for each shape.[8] Pentacubes find applications in packing puzzles, particularly the 12 planar varieties, which have a total volume of 60 unit cubes and can tile rectangular cuboids such as the 2×3×10 (with 12 solutions), 2×5×6 (with 264 solutions), and 3×4×5 (with 3940 solutions).[24]Hexacubes and Larger
Hexacubes are polycubes composed of six unit cubes. There are 166 distinct one-sided hexacubes (considering rotations as identical but reflections as distinct) and 112 free hexacubes (considering both rotations and reflections as identical).[2][16] These counts were first computed systematically by W. F. Lunnon in 1972 using computer-assisted enumeration techniques.[25] Octacubes, consisting of eight unit cubes, number 6922 one-sided and 3811 free.[2][16] Among these, 261 specific tree-like octacubes can be folded in four dimensions to form the surface of a tesseract, representing all possible 3D unfoldings (nets) of the 4D hypercube.[26] This enumeration was established by Peter D. Turney in 1984 through an exhaustive analysis of paired tree structures corresponding to the hypercube's connectivity.[26] For polycubes larger than octacubes, complete enumerations become computationally intensive due to the exponential growth in configurations. Polycubes up to translation only have been enumerated up to order 22, with the count for n=22 being 306,405,169,166,373,418, computed by Phillip Thompson in 2024.[27] These results build on early work by Lunnon and were extended through distributed computing efforts, including contributions from Kevin Gong in the 1990s and 2000s. Free polycubes are enumerated up to n=16, beyond which the symmetry reductions become prohibitively complex without further advancements.[16] Detailed shape catalogs for orders greater than 6 are sparse, as the focus shifts to asymptotic growth rates and specific subclasses rather than exhaustive listings. Hexacubes and larger polycubes feature prominently in dissection puzzles. The Diabolical cube, a 3×3×3 assembly puzzle, incorporates one specific hexacube alongside smaller and one larger polycube piece to fill the 27-unit volume, offering a challenging extension of simpler polycube packings. The Bedlam cube employs 13 pieces—12 pentacubes and one tetracube—to interlock into a 4×4×4 cube, demonstrating how near-hexacube sizes enable intricate, non-trivial assemblies with over 19,000 solutions. Such puzzles highlight the utility of mid-order polycubes in creating bounded-space challenges, though full sets of hexacubes (e.g., all 112 free forms) are typically explored in open-ended construction tasks rather than fixed-target assemblies.[28]Properties
Boundary Connectivity
In polycubes, the boundary consists of the exposed unit square faces of the constituent cubes that are not adjacent to another cube. These structures must be face-connected, with each unit cube sharing at least one full face with an adjacent cube along one of the six orthogonal directions: , , or . This 6-directional connectivity ensures the polycube forms a solid, orthogonal polyhedron without edge- or vertex-only attachments. Complement connectivity addresses the topology of the surrounding space in . In strict definitions, the exterior space must remain connected, preventing enclosed internal voids or holes that would disconnect the complement into multiple components. However, broader formulations permit polycubes with specified internal voids, such as thin horizontal or cubic holes, allowing for more complex structures while maintaining face-connectivity of the cubes themselves. The boundary of a polycube typically forms a simply connected surface, topologically equivalent to a sphere in the genus-0 case, without self-intersections or higher-genus features that complicate unfolding or parameterization. This polyomino-like boundary property facilitates applications like surface mapping and ensures the exposed faces cohere into a manifold. The surface area of a polycube with unit cubes and shared faces is given by
where each cube contributes 6 unit faces initially, and each shared face conceals 2 unit areas from the boundary. The number of shared faces corresponds to the internal connections, which can be analyzed via the dual graph representing cube adjacencies.
An unresolved open problem concerns whether every polycube possessing a connected boundary admits an edge unfolding into a polyomino that tiles the plane by translations, as explored through criteria like Conway's for periodic tiling.