Cube Symmetries

General discussions and topics

Cube Symmetries

Postby jorenheit » Mon Aug 08, 2011 3:42 pm

Hello!

I've been working on a cube solver (in Matlab, but that's irrelevant) and I'm now trying to implement Thistlethwaite's 52-move algorithm (http://www.jaapsch.net/puzzles/thistle.htm#p1). In order to do this, I need hash tables to get from one phase to another. These tables are included in the website to which I just linked, but I found out that there are errors in these tables (not very surprising when you realize that these are manually copied from a letter) so I need to generate my own. For example, it is known that in order to get from phase 2 to phase 3, one needs 10 moves at max. A hash table in this case is a table that lists the effect on corner/edge orientation/permutation of every sequence of 10 moves or less. One determines the state of the cube, then looks it up in the hash table and performs the moves in order to complete the stage. Now, in order to generate such a table, all sequences of 10 moves or less have to be applied to the cube and the resulting states are recorded in a database. However, the number of possible sequences is quite vast when the number of moves is 10 at max. This number is slightly reduced by considering identities as LR=RL, but still enormous and requiring a lot of computational expense. To further reduce the number of sequences to check, one may consider cube symmetries. For example, performing the sequence FL is the same as performing FR after a 180 degree rotation of the entire cube. Since there are 24 possible orientations of the cube (each with its mirror version), the number of sequences can be reduced by a factor 48. This brings me to my question: is there a way to generate all sequences <=10 moves without symmetric twins? One way to do this would be by first generating all of them, and then removing the doubles, but this means that the number of necessary iterations is still just as large! Remember, the calculations have to be performed on an ordinary desktop PC...

I really hope that I've been clear enough and that someone can shed some light on this subject!

Thanks in advance!!

Joren
jorenheit
 
Posts: 3
Joined: Mon Aug 08, 2011 3:21 pm

Re: Cube Symmetries

Postby Sharkretriver » Mon Aug 08, 2011 8:23 pm

Are you asking for a way to generate everything without crashing your PC? Also note that this forum doesn't have a lot of cubers that can help you on this topic. I suggest you go to speedsolving.com forums to ask this question.
lol, here to help ^_~
Sharkretriver
 
Posts: 367
Joined: Thu Jul 14, 2011 10:11 pm
Location: Toronto, Canada

Re: Cube Symmetries

Postby jorenheit » Mon Aug 08, 2011 10:13 pm

Haha my PC won't crash, but it would take him (or her...) a bit too long :P What I'm asking for is a method that allows me to search through all sequences without encountering ones that can be achieved by rotating the cube. At length 2, the computer would perform FR (for example), and then it should know in advance that FL,FU and FD are forbidden, leaving only FB. This gets increasingly difficult at higher algorithm lengths. If such a method exists, it would drastically decrease the number of iterations...but I can't think of any such method :-( Thanks anyway, I'll post the same question on speedcubing.com!
jorenheit
 
Posts: 3
Joined: Mon Aug 08, 2011 3:21 pm

Re: Cube Symmetries

Postby Zeotor » Tue Aug 09, 2011 3:07 am

I can't help, but maybe Cube Explorer can. I don't know much about the program, but I think it can be used to generate algorithms and do other things too. You can go to the website, kociemba.org/cube, and see if it can help. I think that the program, or at least its creator, was involved in finding 20 to be God's Number.

Also, on the website you posted, you can view the original scan. These may not have the errors you mentioned. Near the upper right of each page on that website, there are buttons labeled "View original scan" that take you to the scan.
User avatar
Zeotor
 
Posts: 363
Joined: Thu Jan 13, 2011 5:12 am

Re: Cube Symmetries

Postby jorenheit » Tue Aug 09, 2011 7:49 am

Thanks for the reply! I have taken a look at the original scans, and in some cases I could identify the error but in other cases I couldn't. I just think it would be wise to generate the tables myself, moreso because this would further decrease the maximum necessary number of moves to 45 (Thistlethwaite had to make the tables readable by humans using setup moves).
I just thought of a way that might resolve my issue. Since the algorithm I use to run through all the move sequences is an Iterative Deepening Algorithm (IDA, meaning that the computer first checks all moves of length 1, then 2, then 3 etc), I can check for all unique sequences at depth 1 (resulting in only F) and then use this as the base for depth 2. All approved sequences at depth 2 (starting with F) will be the base of depth 3 etc. This will require more memory but that should not be a problem. Still, if anyone has more efficient suggestions I would be more than happy to hear them!

Thanks again for looking in to this! :D
jorenheit
 
Posts: 3
Joined: Mon Aug 08, 2011 3:21 pm

Re: Cube Symmetries

Postby rubixcuber » Fri Aug 12, 2011 2:52 am

Add a TL;DR, im an impatient guy rofl.
rubixcuber
 
Posts: 701
Joined: Sun Nov 09, 2008 3:06 pm

Re: Cube Symmetries

Postby Sharkretriver » Fri Aug 12, 2011 11:58 am

rubixcuber wrote:Add a TL;DR, im an impatient guy rofl.

Then this subject of group theory isn't for you XD
lol, here to help ^_~
Sharkretriver
 
Posts: 367
Joined: Thu Jul 14, 2011 10:11 pm
Location: Toronto, Canada


Return to General Rubik's Discussion

Who is online

Users browsing this forum: Google Adsense [Bot] and 2 guests

cron