# God's Ultimate Algorithm



## Tony Fisher (May 13, 2021)

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 (May 13, 2021)

Very tough challenge indeed.


----------



## Cale S (May 13, 2021)

A Hamiltonian circuit for Rubik's Cube


----------



## abunickabhi (May 13, 2021)

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 (May 13, 2021)

abunickabhi said:


> 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 (May 13, 2021)

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


----------



## Cubing Forever (May 13, 2021)

qwr said:


> 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 (May 13, 2021)

Cubing Forever said:


> 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 (May 13, 2021)

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 (May 13, 2021)

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 (May 13, 2021)

White KB said:


> 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 (May 13, 2021)

qwr said:


> 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 (May 14, 2021)

White KB said:


> 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 (May 14, 2021)

qwr said:


> 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 (May 14, 2021)

White KB said:


> 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 (May 15, 2021)

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


----------

