Rubik's Cube - Devising an Algorithm

Ask questions about projects relating to: computer science or pure mathematics (such as probability, statistics, geometry, etc...).

Moderators: MelissaB, kgudger, Ray Trent, Moderators

Rubik's Cube - Devising an Algorithm

Postby thedentist » Sat Feb 02, 2013 12:38 pm

Hello, everybody!

First of all, I'd just like to point out that I'm from Sweden, so I'm sorry about my English.

Now that we've got that out of the way, we can begin. As a school project I'm doing the "Devising an Algorithm for Solving Rubik's Cube" idea (http://www.sciencebuddies.org/science-f ... p025.shtml). I thought it was interesting so I gave it a shot. I began at the very beginning, which is getting to know the Rubik's cube. Here I learned all about the different notations, e.g. F is the front side, R is right side and so on. After that I looked up two different ways of solving the Rubik's cube on the Internet. I did both solutions 10 times each. I also wrote plenty about mathematics behind the Rubik's cube, and I'm planning on writting more about that.

At this point I have a good understanding about the whole cube and I can solve it in about three minutes. However, when I began doing the "devising an algorithm" part I got stuck. Immediately. I've tried the three different sets of moves and they all work but to devise and algorithm with only these three sets requires a lot of work, which I am willing to put in, but I just can't get anywhere.

Anyway, so here I am, stuck at this part. Any help I can get is appreciated.

Thank you!
thedentist
 
Posts: 3
Joined: Sun Jan 27, 2013 11:40 am
Occupation: Student
Project Question: I'm trying the "Devising an Algorithm for Solving Rubik's Cube". However, I'm stuck.
Project Due Date: 2013.05.02 (Year.Month.Day)
Project Status: I am conducting my research

Re: Rubik's Cube - Devising an Algorithm

Postby vysarge » Sat Feb 02, 2013 7:42 pm

Hello thedentist! This seems like an interesting project.

I know a bit about the Rubik's cube, so hopefully I'll be able to help.

I looked over the project design, and I noticed some interesting features.

1) When solving a Rubik's cube, it's necessary to move both the corner and edge pieces to the correct positions, as the center pieces can't really be moved. In a solved Rubik's cube, what has to be true about the corner pieces? If you have a mixed-up Rubik's cube, you might be able to make some progress by using Move Sequence #2 to make the corner pieces match the center ones on each face. (Does this make sense? For example, if you have a white center piece, you'd have to get all of the corners with white sides on the top of the cube, then you'd have to get those corners' sides to match.) You might be able to make some progress by looking at how Move Sequence #2 affects the corners of an unsolved cube, and how it could be used for a cube with only two corners out of place, or only three corners out of place. At this stage, I wouldn't worry too much about the edge pieces.

2) After you figure out how to solve the corners, the rest is manipulating the edges. Move Sequence #1 actually switches edge pieces from one edge to another; you could use it when edges are entirely out of place. Move Sequence #3 just flips edge pieces. So, could you make progress by trying to get the edge pieces in the correct places first, then flipping them until the cube is solved?

In general, one of the main strategies that you may have run across is to do the corners first, then the edges. I think that for an algorithm, especially if you're stuck, this could be a good place to start from.

Hope this helped, and good luck- if this isn't quite clear, or you have more questions, do ask!
-Vysarge

~~~~~~~~~~~~~
Nature uses only the longest threads to weave her patterns, so that each small piece of her fabric reveals the organization of the entire tapestry.
-Richard Feynman
vysarge
Expert
 
Posts: 63
Joined: Tue Sep 27, 2011 4:56 pm
Occupation: Student: 12th grade
Project Question: Student volunteer.
Project Due Date: N/a: see above.
Project Status: Not applicable

Re: Rubik's Cube - Devising an Algorithm

Postby thedentist » Sun Feb 03, 2013 4:39 am

vysarge wrote:Hello thedentist! This seems like an interesting project.

I know a bit about the Rubik's cube, so hopefully I'll be able to help.

I looked over the project design, and I noticed some interesting features.

1) When solving a Rubik's cube, it's necessary to move both the corner and edge pieces to the correct positions, as the center pieces can't really be moved. In a solved Rubik's cube, what has to be true about the corner pieces? If you have a mixed-up Rubik's cube, you might be able to make some progress by using Move Sequence #2 to make the corner pieces match the center ones on each face. (Does this make sense? For example, if you have a white center piece, you'd have to get all of the corners with white sides on the top of the cube, then you'd have to get those corners' sides to match.) You might be able to make some progress by looking at how Move Sequence #2 affects the corners of an unsolved cube, and how it could be used for a cube with only two corners out of place, or only three corners out of place. At this stage, I wouldn't worry too much about the edge pieces.

2) After you figure out how to solve the corners, the rest is manipulating the edges. Move Sequence #1 actually switches edge pieces from one edge to another; you could use it when edges are entirely out of place. Move Sequence #3 just flips edge pieces. So, could you make progress by trying to get the edge pieces in the correct places first, then flipping them until the cube is solved?

In general, one of the main strategies that you may have run across is to do the corners first, then the edges. I think that for an algorithm, especially if you're stuck, this could be a good place to start from.

Hope this helped, and good luck- if this isn't quite clear, or you have more questions, do ask!
Thank you, for your quick response!

Yes, I have been thinking about the exact same thing, to use Move Sequence #2 first to get all the corner pieces in the correct position. If I want to do this I'll have to do one side at a time, for example: first yellow, then red etc. While I can get all the corner pieces on one side to the correct position (orange side) I can't get them to have the correct orientation (they are flipped the wrong way). How should I solve that? Furthermore, I have a problem when I want to begin solving the corners of another face (e.g. blue), since that will mess everything up that I did with the previous face (orange, in this case).

Maybe you've got any ideas on how to solve this?

Everything is appreciated.

Thank you!
thedentist
 
Posts: 3
Joined: Sun Jan 27, 2013 11:40 am
Occupation: Student
Project Question: I'm trying the "Devising an Algorithm for Solving Rubik's Cube". However, I'm stuck.
Project Due Date: 2013.05.02 (Year.Month.Day)
Project Status: I am conducting my research

Re: Rubik's Cube - Devising an Algorithm

Postby vysarge » Sun Feb 03, 2013 8:11 am

You're welcome!

I think that solving one face at a time might not be the best way to attack the problem- as you said, there's always the issue of messing up what you've already done. Rather, by combining uses of the sequence in different orientations, might you be able to invent combination sequences that only modify two or four corners? For example, if you do the sequence once, then rotate the cube 90 degrees and try again, what is the result?

(If you get really stuck, you could always try searching for a corners-first solving method online to get some inspiration.)

For flipping, take note of the fact that "Repeating [Move Sequence #2] fifteen times restores the cube to it's original position." Since there are five corners involved and the movement makes a loop, repeating the sequence five times restores each corner to its original place- but not its original orientation. So doing the sequence five times should flip the corners, while keeping them in the same places.

Hope this helped! (And again, any more questions/etc, just ask!)
-Vysarge

~~~~~~~~~~~~~
Nature uses only the longest threads to weave her patterns, so that each small piece of her fabric reveals the organization of the entire tapestry.
-Richard Feynman
vysarge
Expert
 
Posts: 63
Joined: Tue Sep 27, 2011 4:56 pm
Occupation: Student: 12th grade
Project Question: Student volunteer.
Project Due Date: N/a: see above.
Project Status: Not applicable

Re: Rubik's Cube - Devising an Algorithm

Postby thedentist » Sun Feb 03, 2013 9:53 am

vysarge wrote:You're welcome!

I think that solving one face at a time might not be the best way to attack the problem- as you said, there's always the issue of messing up what you've already done. Rather, by combining uses of the sequence in different orientations, might you be able to invent combination sequences that only modify two or four corners? For example, if you do the sequence once, then rotate the cube 90 degrees and try again, what is the result?

(If you get really stuck, you could always try searching for a corners-first solving method online to get some inspiration.)

For flipping, take note of the fact that "Repeating [Move Sequence #2] fifteen times restores the cube to it's original position." Since there are five corners involved and the movement makes a loop, repeating the sequence five times restores each corner to its original place- but not its original orientation. So doing the sequence five times should flip the corners, while keeping them in the same places.

Hope this helped! (And again, any more questions/etc, just ask!)


Great idea, thank you. I will try rotating the cube and see where it leads me.

However, you are not correct regarding the orientation. Since the sequence rotates five corner pieces and three edge pieces you only have to repeat it three times for the edge pieces to be in their original position (with original orientation) but the corner pieces are not, since there are five of them. This means that if you repeat it two more times (five, total) the corner pieces will be at the original position and have their original orientation, but not the edge pieces. The lowest common denominator for 3 and 5 is 15, thus "Repeating [Move Sequence #2] fifteen times restores the cube to it's original position." So sadly, by repeating it five times, won't change the orientation.

Although I'm pretty sure I'll change the orientation by rotating the cube and then doing the sequence again.

Anyway, I'll just have to try doing what you wrote and maybe I'll see some success. If you have any other ideas, they're always welcome. And again, thank you!
thedentist
 
Posts: 3
Joined: Sun Jan 27, 2013 11:40 am
Occupation: Student
Project Question: I'm trying the "Devising an Algorithm for Solving Rubik's Cube". However, I'm stuck.
Project Due Date: 2013.05.02 (Year.Month.Day)
Project Status: I am conducting my research

Re: Rubik's Cube - Devising an Algorithm

Postby vysarge » Sun Feb 03, 2013 4:45 pm

Ah, you're right- I didn't even think about that! That's too bad, it would have been convenient.

But yes, changing the orientation should help some. And perhaps (if that doesn't work) moving from corner to corner with the sequence could do some good as well.

In any case, good luck!
-Vysarge

~~~~~~~~~~~~~
Nature uses only the longest threads to weave her patterns, so that each small piece of her fabric reveals the organization of the entire tapestry.
-Richard Feynman
vysarge
Expert
 
Posts: 63
Joined: Tue Sep 27, 2011 4:56 pm
Occupation: Student: 12th grade
Project Question: Student volunteer.
Project Due Date: N/a: see above.
Project Status: Not applicable


Return to Grades 9-12: Math and Computer Science

Who is online

Users browsing this forum: Yahoo [Bot] and 1 guest