• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

What is God's number on a 4x4 Rubik's cube?

aronpm

Member
Joined
Sep 9, 2009
Messages
2,010
here's a 4x4 solve

Scramble: U R L2 u' f' F L F2 L2 u' D R' L U' R2 f' u' r2 L2 f' F' r' F2 B2 U' r2 R' D2 f' F' r2 U2 F R' B u F u2 R2 r'

F r u B2 r' F2 u2 L' U' D2 r' U u2 B D' r2 U2 F r2 D' f2 u2 // reduction (22 moves)
D2 R' B U2 D' F2 U R2 B' U L F L U R B R2 // 3x3 (17 moves)
 

cubecraze1

Member
Joined
Aug 1, 2011
Messages
625
Location
Australia
WCA
2011OMAH01
YouTube
Visit Channel
here's a 4x4 solve

Scramble: U R L2 u' f' F L F2 L2 u' D R' L U' R2 f' u' r2 L2 f' F' r' F2 B2 U' r2 R' D2 f' F' r2 U2 F R' B u F u2 R2 r'

F r u B2 r' F2 u2 L' U' D2 r' U u2 B D' r2 U2 F r2 D' f2 u2 // reduction (22 moves)
D2 R' B U2 D' F2 U R2 B' U L F L U R B R2 // 3x3 (17 moves)
did that really happen?
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
Indeed... and there are about 10^26 million times as many 4x4 positions as there are 3x3 positions (that's a hundred million million million million). So even if it was as easy to solve a 4x4 scramble optimally as it is to solve a 3x3 scramble optimally, we'd still need a hundred million million million million times as long to get God's Algorithm as we took to do it for the 3x3...

Considering we're only a few orders of magnitude from the atomic computing limit, I feel like I can predict that this computation cannot be done using our current knowledge of optimal-solving techniques.

We're not just making computers faster, we're also making their memory bigger. IIRC, Tom told me a while ago that search speed scales about proportional to memory size. So if you take a computer "only" a million million times faster and memory "only" a million million times bigger, that could suffice.
 

AbstractAlg

Member
Joined
Oct 30, 2011
Messages
373
Location
Belgrade, Serbia
WCA
2012OKAN02
YouTube
Visit Channel
Thank you for this insightful information. We now know God's number for the 4x4.

:D

But, some of the solving-all-the-permutations programs used approach not to solve each permutation, but to scramble the cube to each permutation.
I mean, you don't scramble the cube and then try to solve it optimally, but force a scramble to get to each and every permutation of the cube.
All the previous permutation pattern being stored into some array and checked whether or not the previous best (shortest) scramble for the given pattern has lower move count than the current one.
 

guusrs

Member
Joined
Aug 4, 2007
Messages
686
Location
Netherlands
WCA
1982RAZO01
Back in the 80's I once made some statistic calculations on the number of moves for God's algorithm. This was based on the number of independent and identically distributed (iid) scrambles you need to make 90% sure to cover all possible scrambles. For the 3x3x3 I estimated 21 moves and for 4x4x4 at was something like 35 or so (I don't remember exactly anymore). I have to dig up some old papers.

Note that if you choose x^n iid scrambles out of x possible scrambles your covering precentage is (100% x (1 – ((1/e)^n))). Where e is the mathematical constant, approximately equal to 2.71828

So for n=1 the precentage is about 63%.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
God's Number for 4x4x4

yeah, I read this on cube20.org. It says the computers they used could solve 0.36 positions/sec optimally, but 3900 positions/sec in <=20 moves.

This is for single random positions. For cosets of Kociemba's subgroup, we could solve about a billion positions a second in <= 20 moves.

It does seem inconceivable to brute-force God's Number for the 4x4x4, but I think we are learning new and better techniques all the time. As long as all we care about is the diameter, I think optimally solving positions with significant symmetry will most likely give us at least one of the antipodes. From there we can plan how to prove all positions can be solved in that number of moves. And as Stefan points out, optimally solving single positions speeds up as the product of memory size and CPU speed. And optimally solving all highly symmetrical positions is much easier than n * solving one highly symmetrical position (using coset techniques).

I mean, if you think about it, it was only a few short years ago that Kunkle and Cooperman proved 26 was an upper bound in the half-turn metric; progress has been surprisingly (and unexpectingly) rapid since then, much more so than simple technology would dictate.
 

whauk

Member
Joined
Sep 28, 2008
Messages
464
Location
Germany
WCA
2008KARL02
YouTube
Visit Channel
a 4x4 has no group-structure because of the same colored centers. i dont know much about the theory behind finding god's number but i assume this could be a problem.
 
Top