20120301, 23:06  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16E2_{16} Posts 
Devil's Number for 2x2x2 Rubik's Cube
According to http://anttila.ca/michael/devilsalgorithm/
Definition: A Devil's Algorithm is defined as a set of moves that when applied, repeatedly if necessary, will eventually return a Rubik's Cube to a solved state regardless of the starting configuration. Definition: The Devil's Number is the number of moves in the shortest Devil's Algorithm. 1. What is the devil's number for the 2x2x2? Can anyone improve on the lower and upper bounds on http://anttila.ca/michael/devilsalgorithm/ 2. What is the minimal number of moves including repetitions that someone can detail and prove? On http://anttila.ca/michael/devilsalgorithm/ this ties in with the upper bounds he gave. 3. Can anyone prove or disprove that all 3674160 positions can be hit in 3674159 moves? If disproved what is the minimal number of moves? 
20120302, 04:15  #2 
Romulan Interpreter
Jun 2011
Thailand
10010010100111_{2} Posts 
Didn't get the last part. If you want to go through ALL positions, then you HAVE to make ALL1 moves. There is no move which will give you two different positions. Is like reaching all 120 permutations of 1,2,3,4,5. You will need 119 lines to write down all the moves.
If you ask about reaching ANY of the ALL position, then the number is much lower, it must be bigger then 9, because you have 6 basic moves for a 2Rubik, and 6^9~=10M<36M (I did not check if this is the total number, but I trust you, I did not click your links yet, but I was always interested on the Rubik cube, I found out how to solve it by myself in '84'85, without any formulas, during my highschool, it was big fashion that time). So, practically, if you can prove it is solvable in 10 moves (6^10~=60M, >36M) then you are done. I believe this is called God Number, and it should be known for a 2Rubik. For a normal 3Rubik is 20 and it was proved in August 2010. 
20120302, 06:35  #3 
Oct 2011
7·97 Posts 
I look at the table they show to get the 3674160 and can't help thinking this is wrong. A 2x2x2 cube has 8 pieces, each of which can be in any of the 8 corners, which gives 40320 (1*2*3*4*5*6*7*8). 3674160 / 40320 = 91.125. While each corner can be in 3 different positions, you cannot just use 3^8, as just flipping one corner would break the metric of the puzzle. You can however flip one corner CW and one CCW and maintain the metric. Since the corners have to be paired to create the 3 positions, and you can pair each corner to 7 corners, I believe you end up with 3^7 combinations (2187). Multiplying 40320 and 2187 gives 88179840. Now, having 6 sides, you will repeat these patterns 6 times, so 88179840/6 gives you 14696640 possible combinations.

20120302, 06:51  #4 
Romulan Interpreter
Jun 2011
Thailand
11·853 Posts 
The number is right, see this link. Meantime I read the OP's links and did a little web research. I was right about 20 being the God number for a normal Rubik cube, but I was wrong about 10 being the same for a Pocket cube. The right value seems to be 14 (quarterturns, only 11 halfturns, but I still find it difficult to believe that so many moves are necessary to solve such a simple toy!).
Meantime I also understood the third question, the given value is the minimum value, and the question is if ALL positions can be cycledthrough with THIS number of moves, or you may need more moves to do so. My initial understanding was that the OP is looking for a smaller number of moves, that was impossible. About this question I am still thinking, but the first impression is that you CAN NOT cycle all positions, using any convenient cycle of ALL1 moves. There is a very simple heuristic argument based on the powers of 6, and the fact that moves graph is bipartite (all cycles are even) but I want first to be sure. The question is if one can find a hemiltonian cycle in such a graph and the answer is probably no. Last fiddled with by LaurV on 20120302 at 06:59 
20120302, 16:21  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20120302, 18:31  #6  
Oct 2011
7×97 Posts 
Quote:
The complexity of the puzzle is easy to show though, if you take the 2x2x2 cube and have white on top, and use the simple metric of turning the forward face of the cube clockwise 1/4 turn and then rotate the whole cube 1/4 turn clockwise (keeping 'white' on top) and repeat, in 12 repitions of this the white top face is back together, but it takes 60 repitions to restore the cube. 

20120302, 18:51  #7 
Romulan Interpreter
Jun 2011
Thailand
11·853 Posts 
Please read the definition of a quarterturn and halfturn move.

20120302, 19:01  #8  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
where I used find in your link :
Quote:


20120302, 19:16  #9 
Romulan Interpreter
Jun 2011
Thailand
11×853 Posts 
Yeah, that is a "mislead" from wikipedia, they call "q" and "f" moves, hinting to "quarter move" and "full move", which is wrong. The "f" came from "face". That is common sense. You can only rotate the faces of a cube, and each face you can rotate it to the left (counterclockwise) or to the right (clockwise) with 90 degrees  that would be called a quartermove  or you can rotate it 180 degrees in any direction, that would be called "halfmove". The argue come from the fact that you only do one move, no matter if is quarter or half. To rotate two faces, you need two moves. But to rotate one face, you need one move. Other people won't accept this and say that a "halfmove" is in fact two moves. But the first group can argue that, saying that in this case a rotation with 90 degrees "viceversa" (that is 270 degrees in "normal" direction) should be counted like 3 moves. Which would be absurd.
For details, see here, and especially here (the half move is explained in right the first paragraph), and dig around the links. 
20120302, 19:43  #10  
Oct 2011
7×97 Posts 
Quote:


20120302, 19:51  #11 
Romulan Interpreter
Jun 2011
Thailand
10010010100111_{2} Posts 
Haha, that is, in fact, how you are doing it on any highway or motorway. If I want to turn right (here we drive on the left side) then I have to go left first, and make a 270 which pass under or over the highway. That is why I have 34 km to my job every morning, and only 27 in the evenings when I return. There is exactly the same way, but when I come back I have to make 4 times left, but in the morning I have to make 3 times 270, plus about 800m for an uturn. Any solution for the original problem? :P

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The Devil's Pictionary  only_human  Soap Box  478  20201104 19:10 
Rubik's cube and variations  henryzz  Lounge  110  20180522 03:42 
Perfect Cube Repunits  NBtarheel_33  Puzzles  32  20130910 17:37 
Cube Mountains  davar55  Puzzles  9  20080603 22:36 
Cube root  mfgoode  Homework Help  10  20071005 04:12 