# Message #2109

From: Roice Nelson <roice3@gmail.com>

Subject: Re: [MC4D] Calculating the number of permutation of 2by2by2by2by2 (2^5)

Date: Sun, 06 May 2012 20:00:03 -0500

Hi Melinda,

To help solve the "God’s Number" problem, the cube20

<http://www.cube20.org> guys

used the trick of considering states that *only differ by a symmetry of the

cube* to be the same. I think this is precisely what you are describing.

Their site links to a cube lovers post titled "The real size of cube

space<http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__The_real_size_of_cube_space.html>",

which writes:

In the sense that (for instance) there is really only one position 1 QT

> from start, even though that QT may be applied in twelve different ways,

> this task amounts to counting the true number of positions of the cube.

By identifying states like this, they reduced the number of states they had

to search by a factor of 48 (a factor of 24 from cube rotations and an

extra factor of 2 from reflections). The cube lovers post has more detail

about counting numbers of particular states that are equivalent when looked

at from this perspective. This is also described in the paper "25 Moves

Suffice for Rubik’s Cube <http://arxiv.org/abs/0803.3435>" (and probably in

their later papers as well, though those don’t look to be available on the

arxiv).

So in the 4D case, the state space size would get reduced by 384 (192

rotational symmetries of the hypercube * 2 for reflections). For any

dimension, the factor can be calculated as:

2^n * n!

I grabbed that formula from the wikipedia page on the hyperoctahedral

group<http://en.wikipedia.org/wiki/Hyperoctahedral_group>.

For other shapes besides hypercubes, we could also use the size of the

underlying symmetry group to find out how many states there are which are

"the same" in this sense. So for Klein’s Quartic, we’d get to divide by a

factor of 336.

Cheers,

Roice

On Sun, May 6, 2012 at 6:39 PM, Melinda Green <melinda@superliminal.com>wrote:

>

>

> I may have answered my own question which is that to account for color

> symmetry we can simply divide by (n - 1)! where n is the number of colors.

> For a 2-colored puzzle there is only one color permutation whereas for 3

> color puzzles there are two because we can fix one color and either swap or

> not swap the other two. (n - 1)! gives the number of unique color swapping

> patterns. Is that right? I usually don’t expect to fully understand the

> equations here.

>

> -Melinda

>

>

> On 5/6/2012 4:18 PM, Melinda Green wrote:

>

> I feel that it’s not just tricky but it is wrong in most

> conceptualizations of the idea of puzzle state spaces. Taking this natural

> idea one step further, I would argue that states that have identical

> patterns of stickers should be thought of as the same state. For example,

> if you scramble any twisty puzzle and then swap all red and green stickers,

> then I feel that you still have the same state in terms of permutations

> since anything you can say about one version also applies to the other. For

> example, twist one face of a Rubik’s cube. For our purposes, it doesn’t

> matter which face was twisted. When talking about that state with each

> other we will never think to ask about the particular colors.

>

> Would anyone like to attempt to find the formula for the 3D and 4D cubes

> with this extra "color symmetry" constraint?

>

> -Melinda

>

> On 5/6/2012 2:35 PM, Andrew Gould wrote:

>

> The choice between 31 and 32 comes down to how you define the locations

> of pieces. If you define all their locations relative to one of the pieces

> it’s 31, but if you define what moves and what doesn’t for each twist you

> can make it 32. I note that for 32, it would be tricky to say that

> rotating the entire puzzle doesn’t change the state.

>

>

>

>

>