Rubik's Cube

# Rubik's Cube

Page 4 / 4
(@hurrikane)
New Member
Joined: 5 months ago
Posts: 3
2019-08-05 5:53 pm
Posted by: @robo-pi

@hurrikane

Since you brought this up I did some searches.   Based on what I have found the Rubik's Cube can actually be solved from any of its 43,252,003,274,489,856,000 states in exactly 20 moves.

God's Number is 20

God's Number for Rubik's Cube

The guy in the video offered an algorithm that uses 25 moves.   It could have still be a crank video.   But apparently solving the Rubik's cube in even as few as 20 moves is possible.

Unless these web pages I've finding are also crank websites?

As I say, I don't have a Rubik's Cube here to even try these algorithms on.  So I have no direct experience with any of this.

It may be true that any cube can be solved in 20 moves, but what those exact moves and their exact sequence is dependent on the initial state and orientation of the cube, and it will be a unique sequence based on that state and no 20 odd step universal fixed algorithm is going to work. I didn't mean to push any buttons here, it's just that I've seen several variations on this prank and although this one was pretty well done in hiding the scrambling, (which I suspect was a cube swap during the final time lapse sequence with a cube that had been reverse scrambled using the algorithm.) it's still impossible to "statistically" solve the cube from any state with a fixed 20-odd step algorithm. I can solve the cube, but it usually takes me about 2 minutes since I solve it top down and go through different sequences depending on the cube's state. That does not mean there is only one way to solve the cube, or even that there are only 25 ways to solve the cube, merely that there are 43 x10^18 possible sequences and a huge percentage of those will not result in a solved cube. I believe the author of the video even admits it's a prank. Just sayin...

(@robo-pi)
Noble Member
Joined: 6 months ago
Posts: 1048
2019-08-05 6:35 pm
Posted by: @squeaky

It did seem a bit too attractive …. I had wondered why people, in several videos  that I have watched, had gone to the expense of buying these little cameras when it appeared that they were not really needed.  I am doing some initial trials with a colour recognition sensor and I am looking at the twisted torus project.

If you ever decide to go the route of having a Rubki's Cube solve itself internally you may be able to incorporate some other "cheats" from within the Cube based on knowing the current orientation of all the moving parts.   Looking at if from that perspective would be a different problem since you would have different information to work with.   It sounds like an interesting project to be sure.

(@robo-pi)
Noble Member
Joined: 6 months ago
Posts: 1048
2019-08-05 6:49 pm

On the "God's Number" for the Rubik's Cube.

From what I saw thus far it appears that mathematicians have somehow proven that a Rubik's Cube can always be solved in no more than 20 moves.   I'm sure they did that using mathematical relationships.

However, that wouldn't be the final answer then.  Apparently what they have shown is that given any state of a Rubik's Cube a solution can be had in 20 steps or less.   But how many different sets of 20-step solutions are there?  It would seem to me that to be complete their analysis would need to include that number as well.  Although since I haven't studied this problem it may very well be that they have the answer to that question as well.

In fact, they must have a full answer if people have already built machines that solve the Rubik's Cube.  They could hardly build machines to solve it if they don't have algorithms that lead to a solution.

(@stven)
Trusted Member
Joined: 6 months ago
Posts: 64
2019-08-05 7:30 pm

While there is a lot of historical information about the God's number bveing 20, I can find no similar corroborating evidence about the 25-move algorithm. I think you are correct that this is a hoax. It did not re-solve a solved cube, even after three iterations.

I have seen a single move algorithm that works, but only after making the same move hundres of times. I'm fairly convinced there is no 25-move guarantee, the vidoe just starts at a known position.

The super flip described here is an interesting starting position.

https://ruwix.com/the-rubiks-cube/gods-number/

(@stven)
Trusted Member
Joined: 6 months ago
Posts: 64
2019-08-05 7:36 pm

Most Rubiks solving macnhines leverage the Cube Explorer software in one way or another. The algorithm used by this software must be complex... and it may go down a log of wrong paths before it gets to the right one, similar to a chess playing machine that looks ahead to find best move....

There is a good description of the algorithm under "The Two-Phase Algorithm" on the official web page here:

http://kociemba.org/cube.htm

(@stven)
Trusted Member
Joined: 6 months ago
Posts: 64
2019-08-05 7:41 pm

Fom the inventor of the Cube Explorer algorithm (this is what I would call dedication to a result):

The Two-Phase-Algorithm gives near optimal solutions

I generated 1 million random cubes on a 3 GHz Pentium 4 PC, trying to find a cube which was not solvable within 20 moves with the Two-Phase-Algorithm.

But the Two-Phase-Algorithm solved all generated random positions within 20 moves. More precisely, it solved about 30000 random cubes per hour and the final distribution of the maneuver length was:
13: 4, 14: 18, 15: 81, 16: 609, 17: 3893, 18: 23411, 19: 141366, 20: 830618.

Nevertheless the computation of God's number showed, that there some very rare positions which are quite hard to solve within 20 moves with the two-phase algorithm, for example the cube generated by the maneuver
L R2 U2 B' D2 L D2 F' U' R U2 L' F' D' R' B2 D2 R' U' F2 . On my machine this one takes 16 minutes (in triple search mode).

(@stven)
Trusted Member
Joined: 6 months ago
Posts: 64
2019-08-05 7:46 pm

Perhaps these links are particularly useful for robot enthusiasts:

For those who are interested to build their own Rubik's cube solving robot, want to write cube solving software or just are interested in the way the two-phase-algorithm works in detail can have a look at my fully developed two-phase-solver written in Python. On a Raspberry Pi 3 it solves random cubes within a few seconds with less than 20 moves on average.

https://github.com/hkociemba/RubiksCube-TwophaseSolver

I meanwhile added some functionality to read the facelet colors with a webcam. This also works with the Raspberry Pi and the Raspberry Pi camera module. See here for some more information how to use the interface.

I adopted the code to just solve a 2x2x2 Rubik's cube optimally. This is computationally quite inexpensive.

https://github.com/hkociemba/Rubiks2x2x2-OptimalSolver

(@stven)
Trusted Member
Joined: 6 months ago
Posts: 64
2019-08-05 7:54 pm

Chuckle, I find the 2x2x2 cube much more difficult to solve than a standard 3x3x3. I can always solve the odd order cubes, but the even ones can have parity problems that require extensive algortithms I have not memorized. For example you may end up with two facelets that are in the right places but flipped, and fixing that can be challenging. I can solve 3x3x3, 5x5x5, 7x7x7 cubes without much difficulty - the bigger ones take longer of course. Even ones like 2x2, 4x4x4 are all challenging to me. I can get close but the parity problems at the end have me running in trial and error mode potentially for a long time. Or else I look up the algorithm and use it to get out of gridlock...

(@robo-pi)
Noble Member
Joined: 6 months ago
Posts: 1048
2019-08-05 7:56 pm
Posted by: @stven

While there is a lot of historical information about the God's number bveing 20, I can find no similar corroborating evidence about the 25-move algorithm. I think you are correct that this is a hoax. It did not re-solve a solved cube, even after three iterations.

Shoot me for not having read the video description.  He says right in the description that his video is a joke.  I didn't even read the description I just watched the video and thought it was for real.

I get in trouble quite a bit for being so naive to actually trust people. 😎   Apparently this isn't something we should be doing.  I'll have to train myself to become more suspicious of people.  🤣

Page 4 / 4