• 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?

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
Do you mean by no parity issue that the 3x3x4 can always be solved without having to split any of the 2x2x1 and 2x1x1 sub-blocks

I was thinking of this and yes, you can take apart and randomly assemble it and it can always be solved. Kinda like a double Domino. Simulating it on a 4x4x4 would allow more movements (like R F, where the above puzzle would block the F turn, you can't really do R but just R2), and maybe that would be interesting, too, though it's not what I had in mind.

Does this mean you have an efficient (or even optimal?!?) solver for the final phase?

No, sorry. But I think it has (fixing one corner as reference, and not reduced by symmetries) 2*7!*8!*8!*8!/2^4 = 4.1e16 states, significantly higher than 2x2x2 and "a little" less than 3x3x3. So an optimal solver should be doable and fast.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
I have also thought about reducing to 2x2x2 (i.e. solving all 2x2x2 corner groups independent of their position). It is easy to implement an optimal solver for the final 2x2x2 phase, and this would also have no parity issues. But there is more work required to reduce to a 2x2x2 state since obviously there fewer positions of the 2x2x2 than a 3x3x3. I have some ideas about how the reduction phase(s) could be implemented but not actually tried any coding yet. Does anyone use this form of reduction on 4x4x4 or perhaps even bigger cubes? e.g. reduce 8x8x8 to 4x4x4 and then 2x2x2?!?
Many people have tried something like this for fun, but it never leads to decent times. It is simply very inefficient as well as hard to recognize (in your 8x8x8 example, reducing centers to four 3x3 blocks each is certainly not easier for a human than reducing them to one 6x6 block each). Perhaps these problems will be easier to overcome on a computer solver, but I do feel like a lot of moves will be required to reduce to 2x2x2.
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
The answer to this question might help us in some way lower the upperbound for the 4x4x4. What's the current upperbound of the 3x3x3 supercube (in htm and qtm)? Or has God's number been calculated for that already (if so, what's God's number for it)? I am not sure if this would help, but what is the upperbound if all corners are solved, and only centers need to be rotated and edges need to be solved?
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I just thought I would make it clear that there are two reduction parities (for normal 3x3x3 reduction), and it's only the edge piece permutation parity (seen after reduction as a dedge orientation parity, and called OLL parity) that is not related to the state of the centers.

The other parity, commonly called PLL parity, pretty much requires reduction to be completed to be well-defined. It might be referred to as a dedge permutation parity, but it's really related to the fact that on the 3x3x3, the total permutation parity of corners, edges, and centers must be even. So on a 4x4x4, the total permutation parity of corners, dedges, and composite centers must be even for PLL parity to be even. If we regard the solved centers as defining the orientation of the cube, then the composite centers are automatically even parity, and PLL parity then is just the total parity of corners and dedges.

Just another note, sometimes people use the word "edge" to mean a single edge piece, and sometimes people use the word "edge" to mean a composite edge (or dedge on the 4x4x4). Saying "edge piece" or "dedge" can be helpful in making it clear which one you mean to avoid any possible confusion.

The answer to this question might help us in some way lower the upperbound for the 4x4x4. What's the current upperbound of the 3x3x3 supercube (in htm and qtm)?

Well, it's known that 21f* positions exist. There is a 21f* position needing only centers rotated. It is also known (statistical evidence) that positions requiring more than 22 moves are a very small percentage. (A 2-phase solver solved 1000 random positions with none of the solutions being more than 22 moves.) I'm not aware of any firm upper bounds.
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Well, it's known that 21f* positions exist. There is a 21f* position needing only centers rotated. It is also known (statistical evidence) that positions requiring more than 22 moves are a very small percentage. (A 2-phase solver solved 1000 random positions with none of the solutions being more than 22 moves.) I'm not aware of any firm upper bounds.
Thanks, cuBerBruce. If I assume it to be 24f, would I be safe (seriously, to use it as an undeniable basis to establish an upperbound for another problem)?

I know this is technically off-topic from this thread, but in my second to last post, I mentioned cuBerBruce's 15 BQTM OLL Parity (only) solution for the center formation at the quarter turn. Well, by doing so, I can finally say that I understand that solution completely, and, naturally, I have reproduced the procedure, making longer algorithms, of course.

My shortest solution so far is a (19,18), but I most likely will attempt to try again later.
Rw U D' M' R U' D' U R U' Dw2 r' Dw2 U' L2 D' R' U' R L2 U Rw = Uw S L D' R Uw u l' Uw u L2 D' R' U' M L' F Rw z' (OLL Parity only)

However, I made some long but interesting Roux algs using the same idea. So, for those who have never looked at cuBerBruces algorithm as something pretty, perhaps the structure of these two algs might make you change your mind, because they really do have the same exact structure as cuBerBruce's alg, despite how unbelievable that might be. Note that I made an effort to have the conjugates around the quarter turn be Uw2 instead of u2, Uw u, etc., despite that second 3x3x3 part of the first algorithm cancels with the Uw2.

OLL Parity (only)
r U' M' U M' U' M' U' M Uw2 r Uw2 U' M' U2 M' U M U2 M U M' U M U M' U' l' (31,28)

Double Parity
r' U M' U' M' U M' U M Uw2 l' Uw2 M' U M U' M' U M' U M U2 M' U2 r (29,25)

I cannot claim these to be optimal, but I suspect they are probably pretty close for this algorithm structure and move set. They are basically double the moves as cuBerBruce's alg in block quarter turns!
 

ch_ts

Member
Joined
Apr 25, 2008
Messages
251
No, sorry. But I think it has (fixing one corner as reference, and not reduced by symmetries) 2*7!*8!*8!*8!/2^4 = 4.1e16 states, significantly higher than 2x2x2 and "a little" less than 3x3x3. So an optimal solver should be doable and fast.

How about this for an efficient but not optimal approach:
1. Reduce 4x4x4 to 3x3x4
2. Reduce 3x3x4 to 3x3x3 with E layer edges oriented.
3. Kociemba phase 2
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
How about this for an efficient but not optimal approach:
1. Reduce 4x4x4 to 3x3x4
2. Reduce 3x3x4 to 3x3x3 with E layer edges oriented.
3. Kociemba phase 2

If you do that, I guess phases 2 and 3 could be combined like Kociemba's algorithm combines its two phases, so could be good maybe. But with 1000 times fewer positions than 3x3x3, I really think a "normal" optimal solver for 3x3x4 should be feasible.
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Hey guys,

I have a few more questions.

[1] Besides cuBerBruce's post here, is there any history of previous (higher) upperbounds for the 4x4x4 (established by other people). If so, can you provide links?

[2] Is 22 slice half turns (I'm guessing this is h-b/btm,BHTM) still the upperbound to solve the centers? How about in other move metrics?

[3] Assuming that all centers are solved first so that there is an even permutation in the wing edges, has anyone ever tried to see what's the maximum number of inner layer slice turns (e.g., r, r2, not speaking of M,E,S) required to pair all edges without creating PLL parity? I doubt that this can help us compute god's number, but I thought I should mention it just in case no one has ever thought of it and we maybe able to use it somehow in the future...(plus it's a new variation of reduction)
[1] If all centers are solved so that there is an even permutation in the orbit of wing edges,
[2] If it is possible to solve at least one wing edge of all 12 dedges (where the "solved" wing edge can be "unoriented" or "oriented", as long as one of the two is there), for example (just look at the cube, not the generating solution!) using only 3x3x3 moves and possibly: ONE application of a 3-cycle algorithm in two dedges, for example, OR Stefans PLL parity algorithm r2 F2 U2 r2 U2 F2 r2 at the end of the edge pairing solution,
then
all dedges can be paired (without inducing PLL parity AND preserving the colors of the centers) using a maximum of 6 inner slice half turns. (Of course, this is allowing any number of 3x3x3 moves in between.)

Note that an easy way to disprove my conjecture is to just find one counterexample which violates [2].
A potentially "worst" case is a wing edge scramble like this. Here's a solution I came up with to pair all dedges using only 6 inner layer half turn slices.
Rw2 L' D L2 F' Rw R2 F Uw F' Fw2 D2 R2 U F Rw2 R' B2 R' Fw' Uw U2 Fw2 R Fw' U L' D Rw Uw' L Uw' D' Fw B R2 Uw' R2 L B

R L Uw R B Uw D Lw B Lw' U Lw' B Lw B' L Uw2 L' Fw L2 f' B' D' Lw S2 Lw' z' y//center solution

R B2 L2 D2 L' B2 U2 R2 F U2 L' F' U' F R F2 D' R D2//edge setup and solve corners.
L B r F D'L F' D r' D' F L' D F' B' L'//3-cycle edge pairing alg

F' U2 L2 B' R2 B2 D L' B D' R' F L R' B2 L' F U F' L' U//edge setup for iteration 1
b2u
U' L F U' F' L B2 R L' F' R D B' L D' B2 R2 B L2 U2 F//undo setup for iteration 1 (but don't affect the composite centers/3x3x3 supercube algorithm)

L2 R2 B2 U R2 B2 L' R B L R' B2 L' F2 D B2 D2 B' L' D U' F2//setup for iteration 2 (but don't affect the composite centers/3x3x3 supercube algorithm)
u' b2
D' R' B' D B2 D2 U2 B' U' F' D' F2 R2 B' L U' L // (solve as a 3x3x3, PLL parity and OLL parity is not present and composite centers can be rotated in any fashion)

Which can simplify to (using CubeExplorer)

Rw2 L' D L2 F' Rw R2 F Uw F' Fw2 D2 R2 U F Rw2 R' B2 R' Fw' Uw U2 Fw2 R Fw' U L' D Rw Uw' L Uw' D' Fw B R2 Uw' R2 L B

R L Uw R B Uw D Lw B Lw' U Lw' B Lw B' L Uw2 L' Fw L2 f' B' D' Lw S2 Lw' z' y

U2 B' U2 R2 D2 L2 D' B2 D F' L2 F D' F L' U' R' D B'
r F D'L F' D r'
F2 U' B R' D' L' B F' L2 D2 B L' F' L' F D' B U'
b2u
F D2 L2 D2 R2 F' L2 B2 U2 F R' F2 D L F2 D' B2 R' U2 B F' L' B'
u' b2
D' R' B' D B2 D2 U2 B' U' F' D' F2 R2 B' L U' L
Here's an alternate solution to the centers which creates a wing edge case which can be solved without an edge-pairing 3-cycle algorithm (in two dedges), but, since the corners need to be in an odd permutation to have half of all dedges solved, we get PLL parity, which we can cleverly cancel moves with at the end of the algorithm before the final 3x3x3 solving portion to use a total of 5 half turn inner slice moves. And of course center solution exists which generate cases that don't need PLL parity or an edge pairing algorithm to leave us with a 4 or fewer inner half turn slice dedge pairing solution.

If statement [2] is correct, then note that, since we "solve" at least 12 wing edges (again, for example) and since the wing edges are in an even permutation, my conjecture would be proven TRUE (which might be a useful fact or not so useful).

It turns out (I have done all of the calculations, but here are the results) that all 39 even permutation cycle classes for 12 objects can be solved using two iterations of a 4-cycle, 2 2-cycle, 4 2-cycle, or a 4-cycle + 2 2-cycle. (Note that some cycle classes can be solved using more than one of these cycle class iterative solutions, but the cycle classes are listed under the solution cycle classes which solve them in the fewest number of moves)

4-cycle (The move r, for example)
{3}
{2,2}
{5}
{4,2}
{3,3}
{7}
{4,4}

2 2-cycle (The move r2, for example)
{3,2,2}
{2,2,2,2}

4 2-cycle (The moves r2 u2, for example)
{6,2}
{5,3}
{9}
{5,2,2}
{4,3,2}
{3,3,3}
{7,3}
{6,4}
{5,5}
{4,2,2,2}
{3,3,2,2}
{7,2,2}
{6,3,2}
{5,4,2}
{5,3,3}
{4,4,3}
{3,2,2,2,2}
{6,2,2,2}
{5,3,2,2}
{4,3,3,2}
{3,3,3,3}
{2,2,2,2,2,2}

4-cycle + 2 2-cycle (The moves u r2, for example)
{8,2}
{11}
{10,2}
{9,3}
{8,4}
{7,5}
{6,6}
{4,4,2,2}

  • Therefore all even permutations of 12 objects can be solved using at most 4 inner layer slice half turns.
  • We cannot cancel any of the inner slice turns above with the edge pairing algorithm unless the wing edges involved are in the axes of the axes of the inner layer slice turn...you all are probably clueless as to what I'm saying, but just take note that my assumption of 6 moves or less assumes that the 4 moves to solve every case does NOT always cancel with one of the two moves from the edge pairing algorithm, so we have a total of 4 + 2 = 6.
  • The order of the slice moves in both iterations doesn't matter. For example, if we are solving an 11-cycle (represented by {11}), then we could either do u r2 in iteration 1 and r2 u' in iteration 2, to abbreviate, (u r2, r2 u') OR (r2 u, u' r2) OR (r2 u',u r2) OR (u' r2, r2 u). Since this is the case, if we
  • Cancel the last two inner layer slices (before the final 3x3x3 stage) with Stefan's PLL parity alg. r2 F2 U2 r2 U2 F2 r2, it leaves us with a maximum of 5 moves.
EDIT:

Here's another example solve which includes an edge pairing algorithm but I moved the edge pairing algorithm to the beginning of the edge pairing process to reduce the number of moves (not that this makes a difference in what my conjecture is about, but...)

The same scramble cuBerBruce solved with his solver here.
L' Fw' L' Fw D' R2 D' Uw' L2 B' F2 L Rw2 F' Rw R2 B Fw Uw U2 L R' D R Uw2 B2 Fw F2 D' L Fw' Rw R2 B2 D2 F' D' L' D2 B'//scramble

D2 r2 B' L Uw Bw' D2 Bw R Uw R' U' Fw' U2 Fw U2 F' Lw' Rw' D2 Rw F2 Rw' D2 Rw U' Fw' L2 Fw x y2//center solution

U F' L U' F r F' U L' F U' r' //edge pairing algorithm

L2 U' F2 D' F D2 U2 F2 L U L' R' B2 U F2 L2 B2 R'
r u2 //4-cycle + 2 2-cycle (iteration 1)
B' R2 D2 R2 D2 B2 F D2 U' L' B2 R U2 F D2 U' R' D B F2 L D'
u2 r'//4-cycle + 2 2-cycle (iteration 2)
D F2 L2 U' L F' L D F2 L2 B D F D2 B R2 B D' //3x3x3


EDIT2:
In the example in the edit above, I used an edge pairing algorithm, but I was successful in solving half of the dedges just using 3x3x3 moves.

D2 r2 B' L Uw Bw' D2 Bw R Uw R' U' Fw' U2 Fw U2 F' Lw' Rw' D2 Rw F2 Rw' D2 Rw U' Fw' L2 Fw x y2
R' D2 F2 L' F D' L2 R B' L' R' D U2 L R' D L2


So why did I use an edge pairing algorithm? The cycle class this formation created was a 12-cycle (an odd permutation) because, as you can see by the cube in the link above, only one wing edge is "flipped" in DF, so despite that the permutation of all 24 wing edges is even, for the "unsolved" wing edges, it's an odd permutation (I didn't show this step previously).

And, recall that 4 inner slices are only required if we have even permutation cycle classes of 12 objects. Well, applying the edge pairing algorithm to the two edges that I did was like doing a 2-cycle to make it into an {8,4}, an even permutation.

Just thought I should mention that to point out that there are two reasons why we would need to use an edge pairing algorithm in some situations, if my conjecture is correct, of course
1) To essentially "flip" a single dedge (in this example).
2) To essentially swap two dedges. (in the first example containing an edge pairing algorithm).
 
Last edited:

IAssemble

Member
Joined
May 5, 2010
Messages
248
YouTube
Visit Channel
[3] Assuming that all centers are solved first so that there is an even permutation in the wing edges, has anyone ever tried to see what's the maximum number of inner layer slice turns (e.g., r, r2, not speaking of M,E,S) required to pair all edges without creating PLL parity? I doubt that this can help us compute god's number, but I thought I should mention it just in case no one has ever thought of it and we maybe able to use it somehow in the future...(plus it's a new variation of reduction)
[1] If all centers are solved so that there is an even permutation in the orbit of wing edges,
My solver only considers solutions for the centers that have even edge permutations. It's edge pairing methods preserve edge parity. :)

The rest of your post is thought provoking! I will re-read and try to digest the rest later.
 

qq280833822

Member
Joined
May 28, 2008
Messages
206
Location
China
WCA
2008CHEN27
[1] Besides cuBerBruce's post here, is there any history of previous (higher) upperbounds for the 4x4x4 (established by other people). If so, can you provide links?

With the three-phase reduction algorithm (which is used in the latest wca 4x4x4 scrambler/solver), the upper bound can be reducted to about 60 OBTM (40 moves' reduction + 20 moves' 3x3x3).

The three-phase reduction algorithm is enhanced from tsai's 8-step algorithm(http://cubezzz.dyndns.org/drupal/?q=node/view/73#comment-2588). I merged the step3 and step 4 in tsai's algorithm, and the god number of each phases are(OBTM):

step1: 8
step2: 14
step3/4: <=18?
step 5~8: 20 //3x3x3 without any parity, the oll party is fixed in step2, and the pll parity is fixed in step3/4

I haven't finished full calculation of the god number of step3/4. But after solving 100000 state randomly, I haven't found any state who need more than 16 moves.
Thus, the upper bound should be <= 8 + 14 + 18 + 20 = 60.
 

qq280833822

Member
Joined
May 28, 2008
Messages
206
Location
China
WCA
2008CHEN27
The god's number of 4x4x4 is no more than 57

After analyzing step3&4 of tsai's algorithm, the upper bound is reduced to 57 (OBTM) moves (step1: 8 moves, step2: 13 moves, step3&4: 16 moves, step5~8: 20 moves).
 

elrog

Member
Joined
Jan 31, 2013
Messages
518
Location
U.S.A.
YouTube
Visit Channel
I had a couple of crazy ideas a couple of days ago about finding gods number. I don't really expect either to help at all.

One idea I had was to find some kind of pattern that is always gods number of moves away from solved (something like superflip?). You could then just find the optimal solution to the pattern for whatever size cube. I know superflip itself won't work because a 2x2 would already be solved.

Another idea I had was to add up how many possible series of moves (like how cube explorer searches, but you wouldn't actually have to go through each position) you can have for that size cube until you reach its possible number of states. The problem with this though is cancelling out identical positions (like doing 2 different algs of the same permutation).
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
One idea I had was to find some kind of pattern that is always gods number of moves away from solved (something like superflip?). You could then just find the optimal solution to the pattern for whatever size cube. I know superflip itself won't work because a 2x2 would already be solved.
It would be awfully hard to prove that a given pattern always requires as many moves as possible. Sure, if we somehow did it it would help, but I'm not seeing any way it could be done, or any obvious patterns that would fit the bill.

Another idea I had was to add up how many possible series of moves (like how cube explorer searches, but you wouldn't actually have to go through each position) you can have for that size cube until you reach its possible number of states. The problem with this though is cancelling out identical positions (like doing 2 different algs of the same permutation).
This is exactly how people compute lower bounds for God's Algorithm.
 
Joined
Nov 29, 2008
Messages
214
It would be awfully hard to prove that a given pattern always requires as many moves as possible. Sure, if we somehow did it it would help, but I'm not seeing any way it could be done, or any obvious patterns that would fit the bill.


This is exactly how people compute lower bounds for God's Algorithm.

Yes. And here is a generating function I developed some times ago for the number of "canonical sequences" (where commutating moves and cancellations like U U' etc. are taken into account) in OBTM for all NxNxN cubes.
This means, the Taylor expansion of this functions gives the number of maneuvers with a certain length.

Mathematica Code:

gfh[n_,x_]:= 3/(6-4(3x+1)^(n-1))-1/2

In[12]:= Series[gfh[4,x],{x,0,7}]
Out[12]= 1+27 x+567 x^2+11745 x^3+243486 x^4+5047596 x^5+104639202 x^6+2169224064 x^7+O[x]^8

This means, on the 4x4x4 there are for example 567 maneuvers with length 2

The corresponding generating function for the summed up maneuver length is gfh[n,x]/(1-x)

In[13]:= Series[gfh[4,x]/(1-x),{x,0,7}]
Out[13]= 1+28 x+595 x^2+12340 x^3+255826 x^4+5303422 x^5+109942624 x^6+2279166688 x^7+O[x]^8

This means there are for example 595 maneuvers on the 4x4x4 with length at most 2 in OBTM.

Together with Chris Hardwick's(?) formula for the number of positions on the NxNxN it is now easy to get lower bounds.
Starting with 2x2x2 the lower bounds are

{9,18,35,52,75,99,128,158,193,229,270,312,359,406,458,511,568,626,690....}

Of course I cannot prove this (except for 2x2x2 and 3x3x3 :) ), but I am sure, that God's number is only 2 or 3 moves away from these lower bounds, so for 4x4x4 I assume 37 or 38.
 
Last edited:
Joined
Nov 29, 2008
Messages
214
That generating function looks awfully simple... can you explain how it works?

Only in OBTM it seems possible to derive a closed formula. Without loss of generality we fix the DBL cubie of the nxnxn cube and use only the outer block moves of the U, R and F axis. We note, that the OBTM for the 3x3x3 is equivalent to the standard half turn metric HTM.

The generating function (GF) for a single block move on a fixed axis is 1 + 3 x (there are 3 possibilities for a single move), the GF for an arbitrary number of moves on a fixed axis is (1+3x)^(n-1). I am aware that you have to think a bit about this fact until you believe it. On 3x3x3 (1+3x)^2= 1+6x+9x^2, so there are 6 ways to do 1 move on a fixed axis and 9 ways to do 2 moves on a fixed axis. Dan Hoey called such a sequence of commuting moves (all moves on a fixed axis commute) a syllable. If we ignore the "do nothing" syllable, the GF of a syllable then is (1+3x)^(n-1) – 1.

An arbitrary maneuver is just a sequence of syllables, where of course adjacent syllables have to be from different axes. Let's call a syllable of the U, R and F axis X, Y and Z. Any maneuver has the form X, Y, Z, XY, XZ, YX, YZ, ZX, XY, XYX, XYZ, YXY, YXZ,….. The nice thing with GF's is that you get the GF of a combination by multiplying the GF's of the parts. Lets call (1+3x)^(n-1) – 1 := a. Then the GF for XZ is for example a^2 and for YXZ for example a^3. To find the resulting GF we have to add all these together.We get

GF(x) = 1 + 3a + 3a*(2a) + 3a*(2a)^2 + 3a*(2a)^3 + …….

here 3a*(2a)^3 for example belongs to the 24 possible 4-syllable combinations.

GF(x) = 1 + 3a(1 + (2a) + (2a)^2 + (2a)^3 + …….) = 1+3a/(1-2a)

If your resubstitute a=(1+3x)^(n-1) – 1 you will get

GF(x)= 3/(6-4(3x+1)^(n-1))-1/2 q.e.d.

In quarter turn metric, the GF for single block moves is (1 + 2x + x^2) and this leads to

GF(x) =3/(6-4(x+1)^(2(n-1)))-1/2


Using a partial fraction decompositon it is even possible to give an explict formula for the coefficients in the power series expansion of GF(x), but this would carry things too far here.
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
This idea has probably been thought of before years before my time, but what I am about to say is what I believe to be a more concrete description of what god's algorithm really means on the 4x4x4.

The mere explanation sounds to be very costly for computing power (but what else is new?), but this is probably what we're going to have to do if we ever want to compute god's number for the 4x4x4.

The basis of this approach is to have all possible corner solutions for the 2x2x2 cube up to length x in htm (where we assume that x is god's number in block half turns).

Does anyone have any idea about how many unique solutions (where L R == R L, for example) there are for solving all corner positions of the 2x2x2 up to a length of, say, 35 htm?

It's probably a very large number, but if we could store all possible solutions up to that length in a data base in alphabetical order (sort by the starting moves), it might aid us brute force god's number or at least lower the upperbound significantly...producing a one-phase 4x4x4 cube algorithm.

Assuming the structure of god's algorithm for some of the worst positions moves corners throughout the entire solution, we have to make an assumption: should the shortest path for a given scramble end with an inner layer slice turn, wide turn, or outer layer turn.

With this decision made, if one has access to all possible corner solutions up to length 35 htm, then if god's number is indeed 35 block half turn moves (or maybe a few moves less), we need to figure out an algorithm which solves the wing edges using the one of the corner algorithm skeletons and one which solves the centers using one of the corner algorithm skeletons. If the corner skeleton used for the wing edge solution is different than "" used for the center solution (which will most likely be the case), we search for additional corner skeletons which would work for each separately...and eventually we would find a match.

If we don't find a match, then god's number must be larger than 35.
If a match is found, we have found the shortest path for that particular position.

With this approach, it would be more feasible to actually find god's algorithm for a given position, because obviously the number of corner solutions increases as the length of those solutions increase...but with this approach, the constraint of the interconnectedness of the wing edges, X-centers, and corners would actually help us and not work against us. Because...if the wing edges cannot be solved using a corner skeleton, we don't need to check if that same corner skeleton can be used to solve the centers (and vice versa). Lastly, since we could sort these corner skeleton solutions in alphabetical order, if the centers cannot be solved with the first move being U, for example, then we can automatically skip that in the search for which skeleton wing edges can be solved with.

EDIT:
In short, we can just search all corner skeletons to solve either the centers or wing edges (if one is less costly in computer time for whatever reason, we choose to search the corner solution skeletons to solve that piece type), and then we search all of the corner skeletons which worked for either the centers or wing edges to solve the other piece type, and we're done.
 
Last edited:
Top