Thread: "Doing a class presentation on Rubik's Cube and Group Theory... suggestions?"

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. I want to extend that
to also deriving a solution to the 4D Magic Cube.

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.

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

thanks!
dave

On Tuesday, November 13, "iatkotep" 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.

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. 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.

On 14 Nov 2007 10:27:02 +0000, David Vanderschel wrote:
>
>
>
>
>
>
> On Tuesday, November 13, "iatkotep" 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.
>
>

On Wednesday, November 14, "Jenelle Levenstein" 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 wrote:
> On Tuesday, November 13, "iatkotep" 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.

------=_Part_7834_6400278.1195142765027
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

I talked to my professor... he has seen the stuff I'm already doing... I'm
starting by categorizing all the possible twists of a hypercobe face into
it's own group... and he said while what I had done so far was really great,
it's a hell of a lot of work. and he said he was fine with me presenting
what I have learned of the cube from a group theory perspective and the
questions that I now have.

soooo... I'm open to modifying the presentation a bit. perhaps DERIVING
isn't really a practical idea given my timeframe. maybe instead I could
take existing solution algorithms and point out their significance to group
theory?



On 14 Nov 2007 23:39:39 -0600, David Vanderschel wrote:

> 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 >
> wrote:
> > On Tuesday, November 13, "iatkotep" >
> 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.
>
>
>

------=_Part_7834_6400278.1195142765027
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

I talked to my professor... he has seen the stuff I'm already doing... I'm starting by categorizing all the possible twists of a hypercobe face into it's own group... and he said while what I had done so far was really great, it's a hell of a lot of work.  and he said he was fine with me presenting what I have learned of the cube from a group theory perspective and the questions that I now have.


soooo... I'm open to modifying the presentation a bit.  perhaps DERIVING isn't really a practical idea given my timeframe.  maybe instead I could take existing solution algorithms and point out their significance to group theory?