"Happy Cube" puzzles each have six square pieces, to be assembled into a hollow cube.

> >I was given several "Happy Cube" puzzles.  Each puzzle has six square
> >pieces and the puzzle is to assemble them into a hollow cube.

I have seen these, but have not tried any of them.

> >1. How do they measure difficulty?  They have eighteen puzzles
> >supposedly ranked in increasing difficulty.  How do they measure this?
> >
> >   My guess has something to do with the product of the number of
> >edges that fit together.  (Obviously, some edges do not fit with other
> >edges.  The puzzles that seemed the most difficult were the ones with
> >the most possibilities.)

I'd think so too. I guess you could count the number of possible
false starts (with 2,3,4 or even 5 sides - if possible), and rank
them according to this list. How the manufacturer has ranked them
we can't know without asking them, though.

> >2. Excluding rotations and flips, how many different possible puzzle
> >pieces are there?  In the three puzzles I have, no shape is repeated.
> >I wonder if this is true for all eighteen puzzles?

Tim Chow and Bill Taylor have recently had excellent articles on
something called the POLYA counting theorem - I append Bill Taylor's
article after this post.

Using this we see that counting possible pieces is equivalent to
counting the 2-color (present/absent) colorings of the 16 edge
squares - with the one restriction that if corner square is
present, both adjoining squares cannot be absent, ie. these
3 squares have only 7 possible colorings, not 8.

We do not want to count rotations and reflections as different,
like in Bill Taylor's example, we have a group of rigid motions
containing 8 elements - in fact the same 8 as in his example.
These are - together with the number of colorings preserved
by each:

MOTION          # COLORINGS

identity       7^4*2^4   = 38416
rotate 1/4     7*2       =    14
rotate 3/4     7*2       =    14
rotate 1/2     7^2*2^2   =   196
vert flip      7^2*2^3   =   392
horiz flip     7^2*2^3   =   392
m-diag flip    7*3^2*2^2 =   252 ( Only 3 corner colorings are
o-diag flip    7*3^2*2^2 =   252   preserved when flipped through
                                   "their" diagonal)
                           -----
        sum of # ways...   39928   ==> 39928 [Editor: "39914" in the
                                       original] /8 = 4991 distinct ways.
                               -----                 ################
I hope this is correct.

Bill Taylor's article on POLYA counting:

| A week ago there was a query:   How many distinct ways are there to put
|                                 3 black and 3 white stones on a 3x3 board ?
|
| Tim Chow gave a long and detailed reply about how the Polya counting theorem
| could be used to calculate such things.    As Tim said...
|
| > This deserves to be better known,
|   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| Indeed it does !
|
| Tim's excellent post was perhaps a bit abstract or advanced for some readers,
| so I give here an alternative version of the method.  It can be derived from
| Tim's generating-function approach; and also derived from first principles,
| as I indicate below, though a little group theory knowledge is still needed.
| This method has the added advantage that no recourse to Maple (etc) is needed;
| all the calculations can be simply(?) done by hand.
|
| Polya's theorem applies to coloring, with any given set of colors, any
| geometrical object with given symmetries.    So it can be used e.g. to count
| the number of necklaces with a given set of beads of various colors; the
| number of ways of painting a cube with a specific set of colors; and so on.
|
| --------------------
|
| Polya's Theorem
| ~~~~~~~~~~~~~~~  The number of distinct ways of coloring the object is...
|
| number = [sum-of(# ways kept unchanged by group element)] / (# of elements) .
|
| ...where the sum is over all the group elements, (i.e. the motions of the
|    object that are not thought to change the "distinctness" of the colorings).
|
| --------------------
|
| So in our tictactoe example, we have a 3x3 grid, which we must color as
| 3 black, 3 white & 3 plain cells.  We do not consider reflections and
| rotations and their combinations as distinct, so our group is the group
| of all such rigid motions.  This group, (dihedral on a square, D_4), has
| 8 elements.  So the denominator in the Polya count is 8.  The elements are
|
| identity (no move)
| rotate 1/4 clockwise
| rotate 3/4 clockwise
| rotate 1/2                   (these first four keep the square's "handedness");
|
| flip over vertical axis
| flip over horizontal axis       (these second four reverse the orientation,
| flip over main diagonal          so would not be included if reflections
| flip over other diagonal         counted as different).
|
| The number of colorings preserved by the identity is...  all of them, namely
| (9 choose 3,3,3) = 9!/(3!.3!.3!) = 1680.
|
| The number preserved by the vertical flip is 3x2x3x2 = 36. (The centre
| strip must have one of each color, 3! ways; ditto the right hand strip.)
|
| Similarly with the other three flips; all have 36 colorings.
|
| The three rotations do not preserve any 3-3-3 colorings; (though they would
| preserve some 5-4-0 colorings, for example).
|
| As Tim implied in his post, these numbers can be obtained fairly simply by
| noting the "signature" of each motion - that is the numbers of cells
| cycled by the permutation of the motion.  All this is summarized here...
|
| MOTION         SIGNATURE      # COLORINGS
|
| identity     1 1 1 1 1 1 1 1 1  1680
| rotate 1/4    1 4 4                0
| rotate 3/4    1 4 4                0
| rotate 1/2    1 2 2 2 2            0
| vert flip     1 1 1 2 2 2         36
| horiz flip    1 1 1 2 2 2         36
| m-diag flip   1 1 1 2 2 2         36
| o-diag flip   1 1 1 2 2 2         36
|                                -----
|               sum of # ways...  1824   ==>  1824/8 = 228 distinct ways.
|                                -----                 #################
|
| Recall - each number in the right-hand column is obtained by considering
| the # of ways of putting 3 black 3 white & 3 plain marbles into labelled
| boxes whose sizes are the signature numbers, so that each box is mono-colored.
|
| To make sure you follow the method, check out this calculation for the
| number of distinct (3x3) positions with 4 black, 4 white, & 1 plain cell...
|
| MOTION         SIGNATURE      # COLORINGS
|
| identity     1 1 1 1 1 1 1 1 1   630         ...(9 choose 4,4,1)
| rotate 1/4    1 4 4                2
| rotate 3/4    1 4 4                2
| rotate 1/2    1 2 2 2 2            6         ...(4 choose 2, for e.g. black)
| vert flip     1 1 1 2 2 2         18
| horiz flip    1 1 1 2 2 2         18         these flip numbers are...
| m-diag flip   1 1 1 2 2 2         18           3  x ( 3      +   3 )
| o-diag flip   1 1 1 2 2 2         18        plain  black(1-1) white(1-1)
|                                -----
|               sum of # ways...   712   ==>   712/8 = 89 distinct ways.
|                                -----                 ################
|
| -------------------
|
| Finally, why does this calculation work ?   As I said, this can be dragged
| out of Tim's generating-function version of the Polya theorem; but here is
| a direct way of seeing it; via a simpler example.
|
| Consider how many ways of coloring a line of 5 cells, with 3 black & 2 white,
| so that reflections are not counted as distinct.
|
| There are (5 choose 2) = 10  colorings in total.  But there are only about
| half of these counting as distinct, that is about 5 distinct ways; because
| each coloring has a reflection which shouldn't be counted.  Hence about half.
|
| But this is not exact; because some colorings are *their own* reflections.
|
|  W W b b b        b b b W W       Here are the 10 colorings, which produce
|  W b W b b        b b W b W       not 5 but 6 distinct colorings.
|  W b b W b        b W b b W
|  b W W b b        b b W W b       There are 8 colorings in reflecting pairs,
|  W b b b W                        and 2 self-reflecting colorings.
|  b W b W b
|
| So how do we get 6 from the original 10; by halving ?    A moment's thought
| shows that if we just *add in* an extra 2 for the self-reflecters, and
| *then* halve, we will get exactly the right total.  (10 + 2)/2 = 6.  Correct.
|
| And likewise in general, for more complicated groups, we will have to add in
| an extra one to the total for each symmetry each coloring has; before dividing
| by the total number of symmetries (motions) there are.
|
| And this gives the Polya theorem as stated above, and illustrated.
|
| -----------------
|
| It is easily observed that for the 3x3 grid, really only 4 subcalculations
| are done; for the identity, either 1/4 rot, the 1/2 rot, and (any) flip.
| This further reduces the writing-out needed when doing it by hand, (which
| is a fairly trivial job anyway).  But for more complex geometrical objects,
| for ease one must gather up all the similar types of motions. ......(*)
|
| EXERCISE:  Use this method to calculate the number of ways of painting a
|             cube with 2 red and 4 yellow faces.     Then 3 & 3.
|
| Ditto for an octahedron with 2 red & 6 yellow;   3 & 5;    4 & 4.
| (This is the same as coloring the corners of a cube.)
|
| Answers can easily be checked by direct counting - the numbers are small.
|
| HINT:  The cube group (= octahedron group) has 48 elements; 24 unflipped and
|        24 flipped.  They come in similar types (as mentioned in (*) above)
|        with numbers  1,3,6,6,8  of both flipped and unflipped.
|
|               Bill Taylor              wft@math.canterbury.ac.nz

-- Stein Kulseth <stein.kulseth@tf.tele.no>