God's Ultimate Algorithm

[Tony Fisher]

I propose a new challenge to find the minimum number of moves required to go through every permutation of a standard Rubik's Cube. I suspect we are many years away from having the computing power to even get close though maybe there's huge shortcuts that could be employed.
Just to be clear, I am not talking about repeatedly starting with a solved cube and then going to a different state 43 252 003 274 489 856 000 times, I am talking about single journey through each possible state with as few repeats as possible.
I have no idea if this has been considered before.

 

[ruffleduck]

Very tough challenge indeed.

 

[Cale S]

A Hamiltonian circuit for Rubik's Cube

 

[abunickabhi]

Its just the Hamiltonian cycle for the cube, which is just huge. As Tony said, it will take a lot of computational resources.

On a side note, I want to know the God's number for the 5x5 cube. I think it is around 45-55 moves.

 

[Cubing Forever]

Its just the Hamiltonian cycle for the cube, which is just huge. As Tony said, it will take a lot of computational resources.

What Tony's talking about is god's number for the hamiltonian circuit i.e the least number of moves that a hamiltonian circuit can have. I suspect that would take at least 10 more years to compute. Am I right @Tony Fisher?

 

[qwr]

The Hamiltonian circuit is a fixed size by definition because it visits each vertex exactly once.

 

[Cubing Forever]

The Hamiltonian circuit is a fixed size by definition because it visits each vertex exactly once.

Then according to your definition, the Hamiltonian circuit for 3x3 should be 43 252 003 274 489 856 000 moves long since it has to visit every vertex(state) exactly once.

 

[qwr]

Then according to your definition, the Hamiltonian circuit for 3x3 should be 43 252 003 274 489 856 000 moves long since it has to visit every vertex(state) exactly once.

That's correct. The linked page goes into detail on how the circuit is written in compacted form, because we don't want a 43 exabyte file.
See https://www.speedsolving.com/threads/hamiltonian-circuit-for-the-entire-2x2x2-cube-group.34318/ for an example. Note that since the 2x2 only has about 3.7 million states, it is feasible to write out the whole thing.

 

[Christopher Mowla]

And although not entirely related (but since Tony mentioned the word "repeated"), I started a thread on Twisty Puzzles a little while back on the maximum cyclic order of the nxnxn Rubik's cube (and the minx^3 = megaminx). We know the positions which we repeat algorithms to generate may take a maxiumum of 1260 times to repeat for the 3x3x3, but what about for the nxnxn?

 

[White KB]

For finding a number, I would suggest a lower bound of 43,252,003,274,489,856,000 (the number of combinations in a Rubik's Cube) and an upper bound of 1,730,080,130,979,594,240,000 (the number of moves it takes to get to a solution and back 43252003274489856000 times).

 

[qwr]

For finding a number, I would suggest a lower bound of 43,252,003,274,489,856,000 (the number of combinations in a Rubik's Cube) and an upper bound of 1,730,080,130,979,594,240,000 (the number of moves it takes to get to a solution and back 43252003274489856000 times).

what number are you talking about

 

[White KB]

what number are you talking about

I mean the number of moves long that the God's Ultimate Algorithm would be. I came up with the lower bound by taking the number of permutations in a Rubik's Cube. For the upper bound, I took the number of combinations in a Rubik's Cube and multiplied it by 20 (God's Number), then by 2 (getting there and back). I thought of lowering the upper bound using the chart found at this link, but I didn't have enough time this morning to do the math for that.

 

[qwr]

I mean the number of moves long that the God's Ultimate Algorithm would be. I came up with the lower bound by taking the number of permutations in a Rubik's Cube. For the upper bound, I took the number of combinations in a Rubik's Cube and multiplied it by 20 (God's Number), then by 2 (getting there and back). I thought of lowering the upper bound using the chart found at this link, but I didn't have enough time this morning to do the math for that.

The Hamiltonian circuit was already found 10 years ago. Did you see my post

 

[White KB]

The Hamiltonian circuit was already found 10 years ago. Did you see my post

Oh. I should have probably looked. It was cool math though, right?

 

[DGCubes]

For finding a number, I would suggest a lower bound of 43,252,003,274,489,856,000 (the number of combinations in a Rubik's Cube) and an upper bound of 1,730,080,130,979,594,240,000 (the number of moves it takes to get to a solution and back 43252003274489856000 times).

Just for reference, this upper bound can be divided by two without too much work; it takes a maximum of 20 moves to get from any state to any other state, so you never need to go back to your starting state. (20-move solutions themselves are extremely rare as well; most optimal solutions take 18 moves. But I get that you're just going for an upper bound here. )

 

[Tony Fisher]

Thanks all. I had no idea you could go through each state in one continuous non repeating sequence of moves.