Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Thu Apr 17, 2014 5:08 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Cheating a Rubik's Cube?
PostPosted: Sun Mar 31, 2013 9:58 pm 
Offline

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
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Sun Mar 31, 2013 10:09 pm 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Sun Mar 31, 2013 10:28 pm 
Online
User avatar

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 move-long 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
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Sun Mar 31, 2013 10:49 pm 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Sun Mar 31, 2013 11:55 pm 
Offline
User avatar

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

If you want a 20-move-or-less algorithm to solve your cube, hop over to http://kociemba.org/cube.htm
and 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 quarter-move 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 non-trivial 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 Video
cisco wrote:
Yeah, Uwe is Dalai Lama and Paganotis is mother Teresa of Calcutta.


Top
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Mon Apr 01, 2013 12:26 am 
Offline
User avatar

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 non-repeating 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
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Mon Apr 01, 2013 12:36 am 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Mon Apr 01, 2013 1:13 am 
Offline
User avatar

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 non-repeating 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 20-move 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 non-repeating 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 one-millionth 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, If-Then-Else 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 encyclopedic-sized volume in printed form, it would still only require a few megabytes of space in memory, a drop in the bucket compared to modern-day 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 Video
cisco wrote:
Yeah, Uwe is Dalai Lama and Paganotis is mother Teresa of Calcutta.


Top
 Profile  
 
 Post subject: Re: Cheating a Rubik's Cube?
PostPosted: Mon Apr 01, 2013 1:46 am 
Offline
User avatar

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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Google Adsense [Bot] and 5 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

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group