Devil's Number for 2x2x2 Rubik's Cube

henryzz · 2012-03-01, 23:06

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?

LaurV · 2012-03-02, 04:15

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.

bcp19 · 2012-03-02, 06:35

Quote:

Originally Posted by henryzz

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?

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.

LaurV · 2012-03-02, 06:51

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 (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.

science_man_88 · 2012-03-02, 16:21

Quote:

Originally Posted by bcp19

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.

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.

bcp19 · 2012-03-02, 18:31

Quote:

Originally Posted by LaurV

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 (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.

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.

LaurV · 2012-03-02, 18:51

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

science_man_88 · 2012-03-02, 19:01

Quote:

Originally Posted by LaurV

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

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:

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

LaurV · 2012-03-02, 19:16

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.

bcp19 · 2012-03-02, 19:43

Quote:

Originally Posted by LaurV

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.

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 should 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.

LaurV · 2012-03-02, 19:51

Quote:

Originally Posted by bcp19

Then, when you are driving and you make a left turn, why did you not go around the block and make 3 rights?

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

2012-03-01, 23:06	#1
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 17ED₁₆ 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?

2012-03-02, 06:51	#4
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2⁴×643 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 (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. Last fiddled with by LaurV on 2012-03-02 at 06:59

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The Devil's Pictionary	only_human	Soap Box	479	2021-09-29 11:41
Rubik's cube and variations	henryzz	Lounge	110	2018-05-22 03:42
Perfect Cube Repunits	NBtarheel_33	Puzzles	32	2013-09-10 17:37
Cube Mountains	davar55	Puzzles	9	2008-06-03 22:36
Cube root	mfgoode	Homework Help	10	2007-10-05 04:12

2012-03-02, 04:15	#2
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2⁴·643 Posts	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.

2012-03-02, 18:51	#7
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2⁴·643 Posts	Please read the definition of a quarter-turn and half-turn move.

2012-03-02, 19:16	#9
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2⁴×643 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.