Devil's Number for 2x2x2 Rubik's Cube
 

According to [URL]http://anttila.ca/michael/devilsalgorithm/[/URL][B]
Definition:[/B] A [I]Devil's Algorithm[/I] 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.
[B]Definition:[/B] The [I]Devil's Number[/I] 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 [URL]http://anttila.ca/michael/devilsalgorithm/[/URL]

2. What is the minimal number of moves including repetitions that someone can detail and prove? On [URL]http://anttila.ca/michael/devilsalgorithm/[/URL] 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?

Didn't get the last part. If you want to go through ALL positions, then you HAVE to make ALL-1 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 2-Rubik, 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 2-Rubik. For a normal 3-Rubik is 20 and it was proved in August 2010.

[QUOTE=henryzz;291468]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?[/QUOTE]

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.

The number is right, see [URL="http://en.wikipedia.org/wiki/Pocket_Cube"]this link[/URL]. 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 (quarter-turns, only 11 half-turns, 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 cycled-through 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 ALL-1 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.

[QUOTE=bcp19;291530]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.[/QUOTE]

I would beg to ask what's more annoying 1 chain that may need to be repeated that's >=102060 moves or 3674160 chains that are at most 14 moves totalling 39190008 moves.

[QUOTE=LaurV;291532]The number is right, see [URL="http://en.wikipedia.org/wiki/Pocket_Cube"]this link[/URL]. 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 (quarter-turns, only 11 half-turns, 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 cycled-through 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 ALL-1 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.[/QUOTE]

The 11 1/2 turn, 14 1/4 turn solution is kind of confusing to me. If I were to take a cube and make 5 1/4 turns, it could be solved using up to 11 1/2 turns? Seems like there would need to be at least 1 1/4 turn in the mix.

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.

Please read the definition of a quarter-turn and half-turn move.

[QUOTE=LaurV;291606]Please read the definition of a quarter-turn and half-turn move.[/QUOTE]

where I used find in your link :

[QUOTE]The maximum number of turns required to solve the cube is up to 11 full turns, or up to 14 quarter turns.[1]
The number f of positions that require n full twists and number q of positions that require n quarter turn twists are:[/QUOTE]

is the only part with hits, half has no hits on that page.

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 [URL="http://en.wikipedia.org/wiki/Rubik%27s_Cube"]here[/URL], and especially [URL="http://en.wikipedia.org/wiki/How_to_solve_the_Rubik%27s_Cube"]here[/URL] (the half move is explained in right the first paragraph), and dig around the links.

[QUOTE=LaurV;291611]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 [URL="http://en.wikipedia.org/wiki/Rubik%27s_Cube"]here[/URL], and especially [URL="http://en.wikipedia.org/wiki/How_to_solve_the_Rubik%27s_Cube"]here[/URL] (the half move is explained in right the first paragraph), and dig around the links.[/QUOTE]

I see your point, I always thought 1/4 turn would be considered a move. I disagree that a CCW 1/4 turn would be considered a CW 3/4 turn, unless the rules for your solution stated that you could only turn each face clockwise. To the people who state it [I]should[/I] be counted as 3 moves, my counterarguement would be "Then, when you are driving and you make a left turn, why did you not go around the block and make 3 rights?" While studies have shown (at least for delivery drivers) that it is actually more efficient to perform the 3 right turns due to traffic patterns in larger cities, I highly doubt people would view it as being how it should be.

[QUOTE=bcp19;291618]Then, when you are driving and you make a left turn, why did you not go around the block and make 3 rights?[/QUOTE]
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 u-turn. Any solution for the original problem? :P

I did some looking, while there are a lot of programs you can use to solve a scrambled cube, I did not find any that you could use to repeat the same moves over and over easily. While performing repetitive moves on my 3x3 cube, as expected you can solve a lot faster than a 2x2, but it was kind of amazing how long it would take for 2 or 4 repeating turns. On a 2x2 if you hold the cube steady in space and rotate the front CW and then the right side clockwise, you have to repeat this pattern 15 times (30 twists) on a 2x2 to return back to solved, while you have to perform it 105 times on a 3x3. If you expand this out to 4, going front, right, back, left, it still takes 15 repetitions (60 twists) to return to solved, and I am guessing it would take 105 on the 3x3 except I messed up in the process (was checking the 8 corners every 60) and it became unsolvable. It would be interesting to have a program you could use to see what would give you more repetitions til solved for 3/4/5/etc length patterns.

First of all, I announced a Hamiltonian cycle for the 2x2x2 cube back in December. (I note that it does make use of making the same quarter-turn two or three times in a row, but nothing on the web site referenced in the initial post in this thread prohibits that). A specification of such a cycle can be found at [URL]http://www.speedsolving.com/forum/showthread.php?34318[/URL].

I note that in that Hamiltonian cycle, the first 787,320 quarter-turn moves are repeated for the next 787,320 quarter-turn moves. Therefore, the last 3,674,160 - 787,320 = 2,886,840 quarter-turn moves satisfies what that author of that web site calls a Devil's Algorithm. Thus, 2,886,840 is an upper bound on the Devil's Number.

I also point out what I consider a flaw in the lower bound proof. The web site claims that the highest order for any sequence of moves is 36. However, there are maneuvers of order 45 if you are allowed to turn all six faces. This web site, [URL]http://mzrg.com/rubik/orders.shtml[/URL], lists R L2 U' as an example of an order-45 maneuver. Assuming all six faces can be turned, an similar argument proves a lower bound of 81,648. If moves are restricted to three mutually adjacent faces (so that one cubie remains in a fixed position and orientation), then that web site's lower bound of 102,060 would be valid.

I also note that I've found a Hamiltonian cycle for the Rubik's cube. See [URL]http://bruce.cubing.net/ham333/rubikhamiltonexplanation.html[/URL]. Within this Hamiltonian cycle I can find a sequence of 319,987,003,392,004 moves repeated twice in a row. This means that 43,251,683,287,486,463,996 is an upper bound for the Devil's Number for the Rubik's cube.