View unanswered posts  View active topics

Page 1 of 1

[ 9 posts ] 

Author 
Message 
JackRTully

Post subject: Cheating a Rubik's Cube? Posted: Sun Mar 31, 2013 9:58 pm 

Joined: Sun Aug 26, 2012 10:01 am

Before I learnt how to solve a 3x3x3, I attempted shortcuts, or cheats; along the lines of "Repeat this move until solved!". And soon realized they were fake. However there has to be an algorithm (I'm not bothered how long) that when performed, on any legal state for the 3x3x3 will cause it to return to the solved position?
_________________ My YouTube, including a FF Siamese 2x2x2 Walkthrough


Top 


NXTgen

Post subject: Re: Cheating a Rubik's Cube? Posted: Sun Mar 31, 2013 10:09 pm 

Joined: Sun Dec 13, 2009 5:48 pm

There is one solution I know of that would accomplish this. Although you would need to be able to identify all possible combinations on a single 3x3. The solution is called "God's Algorithm" Here is a link: http://en.wikipedia.org/wiki/God%27s_algorithm
_________________ I should probably find a better signature....


Top 


benpuzzles

Post subject: Re: Cheating a Rubik's Cube? Posted: Sun Mar 31, 2013 10:28 pm 

Joined: Fri Dec 28, 2012 1:50 pm Location: Near Las Vegas, NV

I believe you are actually referring to the Devil's algorithm, a theoretical 43 quintillion movelong sequence that when performed to any scrambled 3x3, eventually at some point during the algorithm, the puzzle will become solved. I don't believe it has been generated yet but it would be very interesting to see it!
_________________ My Youtube channel My Shapeways Shop


Top 


Iranon

Post subject: Re: Cheating a Rubik's Cube? Posted: Sun Mar 31, 2013 10:49 pm 

Joined: Wed Apr 01, 2009 2:59 pm

Just to clarify:
"God's algorithm": the "algorithm" that solves any possible position in the lowest number of moves. Not so much an algorithm as it is a huge lookup table of the shortest possible solution to all 43 quintillion scrambles. "God's number": the maximum number of moves used in the above. Known to be 20 (every 3x3 scramble is solvable in 20 moves or less).
"Devil's algorithm": a move sequence, which when repeatedly applied, will cycle through all 43 quintillion possible positions (without repetition, although that's not important). "Devil's number": the length of the shortest such sequence. As far as I know an explicit devil's algorithm hasn't been calculated/proven for the 3x3, but they exist, and an optimal one exists.
For reference, god's number is 11 on a 2x2, and the devil's number for the 2x2 is known to be somewhere between 100,000 and 300,000. The 2x2 has ~3.7 million positions, so one would expect a devil's algorithm (which is what you're asking about) to be a good bit shorter than 43 quintillion moves long, but still ludicrously beyond the reach of human memory.


Top 


stardust4ever

Post subject: Re: Cheating a Rubik's Cube? Posted: Sun Mar 31, 2013 11:55 pm 

Joined: Sat Mar 24, 2007 6:58 pm Location: Louisiana, US

There's an easier way to cheat on a Rubik's Cube: Rotate U face 45 degrees and lift up the edge piece with a screwdriver or prybar. If you want a 20moveorless algorithm to solve your cube, hop over to http://kociemba.org/cube.htmand download Cube explorer version 5. And yes, it was very nice of Google to use their spare computing resources to brute force prove that every position of the cube could be solved in 20 moves or less. Now if only we had a solution for center parity. I know some solutions can take 23+ moves when center twists are involved. As for the devil's algorithm, while I'm not dismissing the idea, as there are quite likely infinitely many solutions, a truly optimal "devil's algorithm" requires that each position be achieved once and only once, for a total of ~43 quintillion moves. No computer on Earth has the memory resources to hold all ~43 quintillion positions in memory and develop a network between them, so what is necessary is to create a sequence of moves for a devil's algorithm that can be represented in much less space. Ideally, an optimal solution that can use parenthesis (...), multipliers (*x), whole cube rotations (which do not count as individual "moves" but enable sequences to be recycled and reused in creative ways) etc to define an optimal solution using the shortest expression possible. A quartermove notation will be necessary since half rotations automatically pass through one of two interim positions. Finally, some rigorous proof must be formulated that proves the sequence covers each and every position on the Rubik's Cube exactly once. The solution obviously has to be exactly ~43 quintillion moves long; determining this is the easy part, but proving that no positions are repeated will likely be a nontrivial process. And with current processor speeds, it will not be feasible, even over the course of a human lifetime, to compute every step of the process in order to verify the devil's algorithm.
_________________ My Creepy 3D Rubik's Cube Videocisco wrote: Yeah, Uwe is Dalai Lama and Paganotis is mother Teresa of Calcutta.


Top 


Brandon Enright

Post subject: Re: Cheating a Rubik's Cube? Posted: Mon Apr 01, 2013 12:26 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

JackRTully wrote: Before I learnt how to solve a 3x3x3, I attempted shortcuts, or cheats; along the lines of "Repeat this move until solved!". And soon realized they were fake. However there has to be an algorithm (I'm not bothered how long) that when performed, on any legal state for the 3x3x3 will cause it to return to the solved position? There is no short sequence that when repeated many times will visit every position. Of course there are nonrepeating sequences that will visit every position (not necessarily without duplicates) but the number of moves would be extraordinarily huge. The highest order sequences have an order of 1260. For example [U, R'2, L', F, L']x1260 To reach all of the positions of the Rubik's cube requires at least as many moves as there are positions. Since the highest order of any sequence is 1260 the fewest moves a repeated "devil's alg" could have is: ? ((8! * 12!) / 2 * (2^12 / 2) * (3^8 / 3)) / 1260 % = 34326986725785600 So unless you want to memorize 3.4*10^16 moves, there is no hope of repeating something over and over until you reach every state.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


Brandon Enright

Post subject: Re: Cheating a Rubik's Cube? Posted: Mon Apr 01, 2013 12:36 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

stardust4ever wrote: [...]with current processor speeds, it will not be feasible, even over the course of a human lifetime, to compute every step of the process in order to verify the devil's algorithm. Given current knowledge, I agree. A great many things have been proven in math that could never have been found via any form of brute force. For example, we can count the number of positions a Rubik's cube can reach (a huge number) without enumerating them all. If a "devil's algorithm" is ever found or shown not to exist, it will be due to great mathematical insights, not faster CPUs or more memory.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


stardust4ever

Post subject: Re: Cheating a Rubik's Cube? Posted: Mon Apr 01, 2013 1:13 am 

Joined: Sat Mar 24, 2007 6:58 pm Location: Louisiana, US

bmenrigh wrote: JackRTully wrote: Before I learnt how to solve a 3x3x3, I attempted shortcuts, or cheats; along the lines of "Repeat this move until solved!". And soon realized they were fake. However there has to be an algorithm (I'm not bothered how long) that when performed, on any legal state for the 3x3x3 will cause it to return to the solved position? There is no short sequence that when repeated many times will visit every position. Of course there are nonrepeating sequences that will visit every position (not necessarily without duplicates) but the number of moves would be extraordinarily huge. The highest order sequences have an order of 1260. For example [U, R'2, L', F, L']x1260 To reach all of the positions of the Rubik's cube requires at least as many moves as there are positions. Since the highest order of any sequence is 1260 the fewest moves a repeated "devil's alg" could have is: ? ((8! * 12!) / 2 * (2^12 / 2) * (3^8 / 3)) / 1260 % = 34326986725785600 So unless you want to memorize 3.4*10^16 moves, there is no hope of repeating something over and over until you reach every state. You are forgetting about nested parenthetical loops and whole cube rotations. A string of moves could be performed X times, then an additional moves could be added at the end. This entire long sequence could be repeated Y times. What is the largest minimum number of moves necessary for an algorithm of the form ((String A)*X + (String B))*Y to repeat itself, where "String A" and "String B" are individual sequences of moves? Now throw whole cube rotations into the mix. An extremely long sequence of moves could be generated using a small number of short sequences by nesting loops. I must iterate, whole cube rotations do not add to the move count, but allow common sequences to be executed and combined in unique ways. How about this one? ((A*X + B)*Y + C)*Z + D where A, B, and C are sequences of moves, and X, Y, and Z are integers? Suppose A, B, C, and D are each 20move optimal sequences which result in a pattern requiring 1260 repetitions to repeat, and X, Y, and Z are all equal to 1259? Then you have a sequence which is (((((20 *1259) +20) *1259) + 20) *1259) + 20 moves long. That is a potentially nonrepeating sequence of 39,944,066,400 moves, which could be potentially repeated 1258 more times for a grand total of 50,289,579,597,600 moves without further repetition, yet the entire expression, excluding parentheses and mathematical operations, only uses up 80 printed face moves. Nested operands are an absolute necessity to describe a working "devil's algorithm". The above algorithm, if it worked, at ~50 trillion moves, would eliminate a little over onemillionth of the possible positions on the Rubik's Cube, however the chances are likely that some positions would be repeated if strings A, B, C, and D are not chosen wisely. Stings A, B, C, D, E, etc can be stored as variables and further perturbations of the cube can result by combining them in different arrangements. Instead of using precise math notation, IfThenElse style logic loops, as well as For, While, and others can be strung together to result in a more customizable algorithm. For Example, in the expression (A + B)*X, string A could be substituted with C whenever X is divisible by 3, and B substituted with D whenever X  1 is divisible by 5. The objective here is to create an optimal "devil's algorithm" with exactly ~43 quintillion moves, and the exact expression needs to be defined by the smallest possible amount of code, whether readable by human or machine. even if the required code were to take up an entire encyclopedicsized volume in printed form, it would still only require a few megabytes of space in memory, a drop in the bucket compared to modernday computer memory capacity. In conclusion, I believe it would be entirely feasible to describe a sequence 43,252,003,274,489,856,000 cycles long in a relatively small amount of space, by using nested loops or other forms of logic.
_________________ My Creepy 3D Rubik's Cube Videocisco wrote: Yeah, Uwe is Dalai Lama and Paganotis is mother Teresa of Calcutta.


Top 


Brandon Enright

Post subject: Re: Cheating a Rubik's Cube? Posted: Mon Apr 01, 2013 1:46 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

stardust4ever wrote: You are forgetting about nested parenthetical loops and whole cube rotations. Constructions like this violate the initial criteria of "Repeat this move until solved!" however if we relax the restrictions to "follow this simple program" it might be possible. I'm not sure if a cycle of 1260 (or other long cycles) can itself be made up of much shorter sequence repetition and concatenation. I guess a related question is "What is the minimum amount of information needed to describe a program that visits every position of the Rubik's cube?" My guess is that the lower bound is hundreds of kilobytes. Edit: actually if efficiency is not a factor then I can think of relatively short but extraordinarily naive programs that would visit every position. I more interesting question would be what is min(sizeofprogram * numberofmovesituses).
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 



Page 1 of 1

[ 9 posts ] 

Who is online 
Users browsing this forum: No registered users and 3 guests 

You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum


