Thread: "Video puzzle"

--e89a8f2348bf53827604bf67cac0
Content-Type: text/plain; charset=ISO-8859-1

Hi Melinda,

To help solve the "God's Number" problem, the cube20
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",
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 " (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.
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 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.
>
>
>
>
>

--e89a8f2348bf53827604bf67cac0
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable