mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2012-03-01, 23:06   #1
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·29·101 Posts
Default 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?
henryzz is offline   Reply With Quote
Old 2012-03-02, 04:15   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

83×113 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2012-03-02, 06:35   #3
bcp19
 
bcp19's Avatar
 
Oct 2011

12478 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
bcp19 is offline   Reply With Quote
Old 2012-03-02, 06:51   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

222438 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-03-02, 16:21   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by bcp19 View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-03-02, 18:31   #6
bcp19
 
bcp19's Avatar
 
Oct 2011

7×97 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
bcp19 is offline   Reply With Quote
Old 2012-03-02, 18:51   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

83×113 Posts
Default

Please read the definition of a quarter-turn and half-turn move.
LaurV is offline   Reply With Quote
Old 2012-03-02, 19:01   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-03-02, 19:16   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

937910 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2012-03-02, 19:43   #10
bcp19
 
bcp19's Avatar
 
Oct 2011

7×97 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
bcp19 is offline   Reply With Quote
Old 2012-03-02, 19:51   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

937910 Posts
Default

Quote:
Originally Posted by bcp19 View Post
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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Devil's Pictionary only_human Soap Box 478 2020-11-04 19:10
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

All times are UTC. The time now is 05:32.

Mon Apr 19 05:32:24 UTC 2021 up 11 days, 13 mins, 0 users, load averages: 1.46, 1.49, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.