Message #435

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Re: [MC4D] Doing a class presentation on Rubik’s Cube and Group Theory… suggestions?
Date: Wed, 14 Nov 2007 23:39:39 -0600

On Wednesday, November 14, "Jenelle Levenstein" <jenelle.levenstein@gmail.com> wrote:
>If all you want to do is make a program solve a
>rublix cube you could always solve it using the brute
>force method where you try all possible combinations
>of moves until the you find the solution.

Note that dave explicitly stated that he wanted to use
techniques he was learning in his abstract algebra
class to _derive_ a solution.

>This works on the 2^3 and maybe on the 3^3 and only
>because the cube is always within about 15 moves of
>being solved.

Sorry, not for 3^3. The search tree expands way too
rapidly. Not only is a solution within 15 moves of an
arbitrary start, but so is every other possible
configuration of the cube. The number (on the order
of 10^20) is way too large to admit a brute force
approach. Fortunately, there exist more intelligent
approaches which do work. Indeed, Don Hatch has
posted a general one (for nD) here:
http://www.plunk.org/~hatch/MagicCubeNdSolve/

Brute force, when it works, can find the shortest
solution. Don’s method does not claim to be optimal.

Regards,
David V.

On 14 Nov 2007 10:27:02 +0000, David Vanderschel <DvdS@austin.rr.com> wrote:
> On Tuesday, November 13, "iatkotep" <iatkotep@gmail.com> wrote:
> >I’ve never solved a rubik’s cube. the idea for my
> >presentation is to take the techniques that I’m
> >learning in my abstract algebra class, and use them
> >to derive a solution to the cube.

> Good luck! I would be surprised if you succeed in
> this venture; but it will be an impressive achievement
> if you do succeed.

> Yes, Rubik’s Cube is a good example of a non-trivial
> group.

> You might want to start with a simpler permutation
> puzzle - like the 2x2x2 analogue of Rubik’s Cube.

> >I want to extend that to also deriving a solution to
> >the 4D Magic Cube.

> If you do succeed for the 3D puzzle, then extending
> for the 4D puzzle should not be so hard. Aside from
> the fact that there are a lot more pieces to fool
> with, there is a sense in which manipulating the 4D
> puzzle is actually easier than the 3D puzzle.

> >I’m at the beginning now… I know what properties of
> >the cube make it a mathematical group, but that’s as
> >far as I’ve gotten. I have a strong feeling that
> >jumping from the cube as a group to a full blown
> >solution involves the study of subgroups, but I’m not
> >really sure where to start.

> There is plenty of information out there which
> addresses the puzzle from the Group Theory point of
> view. The source of this sort to which I have paid
> the most attention is W. D. Joyner’s Web page here:
> http://web.usna.navy.mil/~wdj/rubik_nts.htm

> >do we have any math people in there that could kind
> >of point me in the right direction?

> The truth of the matter is that every method I have
> ever seen for working Rubik’s Cube approaches it from
> a rather empirical point of view. There are some
> important facts about what you can and cannot achieve
> that are implied by the theory, but you don’t really
> need to know the theory to take advantage of the facts
> themselves. (Indeed, the facts can eventually become
> apparent even without having known about the theory
> which implies them.)

> I first laid my hands on a Rubik’s Cube in 1979. I
> was actually pretty well trained in Group Theory at
> the time, and I did realize that the puzzle could be
> regarded as a representation of a group. However, my
> knowledge of Group Theory played little role in my
> figuring out how to work the puzzle. I suppose it did
> lead me to try things like commutators and
> conjugation; but I probably would have done so even if
> I had not known what such operations were called in
> Group Theory.

> Regards,
> David V.