Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am writing a program to solve a Rubik's cube, and would like to know the answer to this question.

There are 12 ways to make one move on a Rubik's cube. How many ways are there to make a sequence of six moves?

From my project's specification: up to six moves may be used to scramble the cube. My job is to write a program that can return the cube to the solved state. I am allowed to use up to 90 moves to solve it. Currently, I can solve the cube, but it takes me over 100 moves (which fails the objective)... so I ask this question to figure out if a brute force method is applicable to this situation.

If the number of ways to make six moves is not overly excessive, I can just make six random moves, then check to see if the cube is solved. Repeat if necessary.

share|improve this question
4  
Are you asking for how many distinct results are there after 6 moves? Or just for how many ways you can make 6 moves, regardless of their uniqueness? –  Brandon Carter Nov 9 '10 at 19:07
    
I think we should assume we are looking for distinct configurations, since this makes the problem a lot harder/interesting and is more practical for the programming application. –  Matt Calhoun Nov 10 '10 at 15:55
    
I'm editing the OP to give full details. –  dfetter88 Nov 10 '10 at 20:36
    
Rather than brute forcing it you could try and implement a solving algorithm from the ones known until now. I'm sure there are some which can get down to less than 50 moves. For example this: ws2.binghamton.edu/fridrich/cube.html Just making random moves until it's done seems it could make lots of unuseful moves, and I guess the 90 limit moves needs some intelligent algorithm. –  Beni Bogosel Apr 27 '12 at 9:04
add comment

3 Answers 3

I would leave this as a comment, but I do not have the reputation ...

What do you consider a move? The normal way of understanding the Rubik's cube, is that you can do 18 or 27 moves at each step. That is; you can move each side 90 degrees in two different directions, or make a 180 degree move. In total 3 moves per side, and you have 6 or 9 sides depending on whether you count the "middle slices" of the cube as valid sides or not.

When you arrive at 12 legal moves, do you only consider the 90 degree moves on the "outer" sides as legal?

share|improve this answer
    
I think you are right, as that leads to 12. We still don't have an answer from OP to Brandon Carter's good question. –  Ross Millikan Nov 10 '10 at 14:35
    
Yes, only considering outside face twists. This is due to my project specifications. Axis rotations also count, but I am not taking them into account here because they do not change the actual state of the cube... unless you see a reason to include them in my calculations? –  dfetter88 Nov 10 '10 at 20:43
add comment

12^6 is just under 3 million. So it would probably not work to randomly try six unscrambles. But it wouldn't be too hard to make a data file of all the positions and their unscramble twists if you can find a reasonable way to search it, like some hash function on a description of the position.

share|improve this answer
    
Creating a hash table of 3 million cube states and their respective solutions? Maybe not "difficult", but definitely a large task. –  dfetter88 Nov 10 '10 at 22:34
    
But I think a computer can do it in not too much time. Loop over the possibilities for the moves, calculate the final state of the cube, calculate your hash function, store the solution in a table. I've done much more calculation than that for some of the Project Euler problems, though the program was simpler. –  Ross Millikan Nov 10 '10 at 23:04
    
+1 because that is the most practical way to go about solving this problem (for up to 6 moves). –  evgeny Sep 20 '11 at 5:40
add comment

There are 7,618,438 diferent positions after six movements according to this site, but they use face movements. By the way they show that the Rubik's cube can be solved in 20 face movements or less.

share|improve this answer
    
I think there may be more: that number excludes positions which can be reached in six moves but which can also be reached in fewer. –  Henry Sep 25 '11 at 21:34
    
@Henry: You are right. actually the number I gave allows 18 legal moves while the OP ask for 12 (90 deg twists) so the number of different positions after at most 6 moves is a lot smaller: 1056772. Actually the method given by him (make six random moves until the puzzle is solved) fails for the 96696 positions after 5 moves if it does not take this into account. –  Esteban Crespi Sep 26 '11 at 15:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.