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

[IAssemble]

what was the solution and what does it find for OLL parity?

I left it running overnight and it found a 31 OBTM solution to 11-flip (although by default it does not actually display the solution so I will re-run it with that enabled)...

 

[IAssemble]

I know this question wasn't directed at me, but I'm curious how many moves it takes your solver to solve the following cases:
[1] Rw' U' R' U' Rw F' R' F' Rw'
[2] Lw F2 U2 l' U2 Lw U' R U l U2 l' U R' U Lw' F2 Lw'
[3] And just a "potential bad case" to check: the case generated by this set of algorithms.

The question was not directed at anyone in particular... I'm interested to hear from anyone who has ideas about what makes 4x4x4 positions "hard".

Many thanks. I'll try my algorithm on these positions later and let you know.

what was the solution and what does it find for OLL parity?

By "OLL parity" you mean a single, pure edge flip?

 

[cuBerBruce]

Using my solver, I found a 28-move solution for for the 11-dedge flip using BTM. We know there exist positions requiring 29 block turns, so it's definitely not antipodal in BTM either.

M S r U2 r F2 r' D2 r E2 r U' f2 Rw2 U f2 U' Rw2 f2 D' B2 R2 B2 L2 D2 Fw2 U2 Fw2

 

[ben1996123]

By "OLL parity" you mean a single, pure edge flip?

yes

 

[Christopher Mowla]

We know there exist positions requiring 29 block turns, so it's definitely not antipodal in BTM either.

It looks like it isn't for BQTM either:
d E M R D R' Bw f M d' M' Fw b M' F Uw M' R' S L F' U R D' R' E S2 R F' z' y (30 q-b ,29 h-b)

But for q-w, I'm not sure:
x' Rw' U F2 U' Lw' U2 Rw' U2 Rw' F' U2 F Rw' B2 L2 D2 L' F2 R' U' B' D L' F D U B2 R2 F D2 F' U2 (44 q-w, 32 h-w)
x l F U2 F' Rw U2 Rw U2 Rw U2 F U2 F' U2 r D' L2 U2 F2 R2 L F U' B' R U D B L2 F B' (44 q-w, 33 h-w)
r F U2 F' Rw U2 Rw U2 Rw R U2 F U2 F' U2 r B' U2 R B' L2 F' L' U F' U2 B L' R' U2 D B (44 q-w, 34 h-w)

Maybe Mr. Rokicki's 3x3x3 solver could solve the 3x3x3 part of the algorithms above in fewer qtm to possibly lower the move count to 41 q-w, where it needs to be (note that 19 htm is optimal for the 3x3x3 part of the 32 h-w alg, unfortuantely. It took over half an hour for cube explorer to find it).

 

[ben1996123]

something like this seems like it might need a lot of moves

 

[cmhardw]

I've always thought that having every center group have 2 centers on a diagonal with matching colors, then have the other 2 colors on the other diagonal match each other but not the colors from the first diagonal would lead to difficult positions. I have absolutely no proof for this, it just seems intuitively difficult to solve.

 

[mark49152]

I've always thought that having every center group have 2 centers on a diagonal with matching colors, then have the other 2 colors on the other diagonal match each other but not the colors from the first diagonal would lead to difficult positions. I have absolutely no proof for this, it just seems intuitively difficult to solve.

Yes I was thinking something similar, combined with 3x3 superflip around the outside. So each edge requires taking out, flipping and reinserting relative to its adjacent corner, as mentioned earlier, but lots of center slicing means lots of potential destruction to the edge pairing as well (or extra moves avoiding it). Again, no proof, just intuitive speculation.

 

[Gabriel H]

i think that is something about 40 or 50 moves, because we have to do de centers, after de edges, and after we solve like the 3x3(20 moves god's number) and the parityes

 

[Username]

i think that is something about 40 or 50 moves, because we have to do de centers, after de edges, and after we solve like the 3x3(20 moves god's number) and the parityes

Why would it automatically be solved with reduction? That made absolutely no sense

 

[Gabriel H]

Why would it automatically be solved with reduction? That made absolutely no sense

I'm saying about the speedsolving, because i think that is very difficult to solve the 4x4 without Method, we have to use some method, so i think that's impossible to solve it without at least 40 or 50 moves.

 

[ben1996123]

we have to use some method, so i think that's impossible to solve it without at least 40 or 50 moves.

optimal solving methods are not reduction

 

[IAssemble]

I've always thought that having every center group have 2 centers on a diagonal with matching colors, then have the other 2 colors on the other diagonal match each other but not the colors from the first diagonal would lead to difficult positions. I have absolutely no proof for this, it just seems intuitively difficult to solve.

Something like this U' B' Rw' D Uw' Bw2 B' F' Lw L' Bw' F D' U R B U?

Yes, intuitively I would have expected that it could be hard but as you can see from the 17 turn OBTM solution it is not

 

[IAssemble]

Yes I was thinking something similar, combined with 3x3 superflip around the outside. So each edge requires taking out, flipping and reinserting relative to its adjacent corner, as mentioned earlier, but lots of center slicing means lots of potential destruction to the edge pairing as well (or extra moves avoiding it). Again, no proof, just intuitive speculation.

This is probably not as bad as you might think because even with a reduction algorithm, the act of solving the centrers will disturb the 3x3x3 superflip so it is unlikely to be as hard to solve the 3x3x3 after the edges are re-paired. Intuitively, I would not expect this to be particularly hard.

And as an example, here is a 31 turn OBTM solution generated quite quickly by my solver U' L' Fw Uw' U B Fw2 F Lw R' Dw R' B2 R F2 R2 U2 F D' B R' L2 U' L2 U L2 B' R B D2 L

 

[kcl]

Apparently you missed what the page says:
"it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation"



How fast?

Very. Think about it.. In the past ten years, technology has evolved at an incredible rate. The iPod was invented. The iPhone. New computers, new chips, processors, software. Cloud storage. The price of flash memory is less than 50c per GB now. That's an excellent example. Several years ago, a 1GB card could cost over $100. Now, a 128GB costs almost half of that. These are just a few examples I can think of off the top of my head.

 

[mark49152]

This is probably not as bad as you might think because even with a reduction algorithm, the act of solving the centrers will disturb the 3x3x3 superflip so it is unlikely to be as hard to solve the 3x3x3 after the edges are re-paired. Intuitively, I would not expect this to be particularly hard.

Solving the centers would not break the edges away from their adjacent corners, but after thinking about it further, when flipped those edges need to be moved to the opposite corner anyway so you are right that this disruption could help. (As was also already pointed out earlier, but I missed it.)

Here's another idea on similar principle. Imagine the centers intact, and corners and edges in their correct relative positions but with each "tripod" of four rotated +1 around the corner tip. Thus, every center needs to be separated from its adjacent edges, breaking every tripod leg and requiring it to be restored. For good measure, three of the centers could be cycled.

 

[IAssemble]

This is probably not as bad as you might think because even with a reduction algorithm, the act of solving the centrers will disturb the 3x3x3 superflip so it is unlikely to be as hard to solve the 3x3x3 after the edges are re-paired. Intuitively, I would not expect this to be particularly hard.

And as an example, here is a 31 turn OBTM solution generated quite quickly by my solver U' L' Fw Uw' U B Fw2 F Lw R' Dw R' B2 R F2 R2 U2 F D' B R' L2 U' L2 U L2 B' R B D2 L

I've been thinking further...

Bringing together ideas discussed so far (and again some "intuitive" thoughts):

Edge parity is a relationship between the edges and the centres. It is "hard" because 8 of the centre pieces have to be re-positioned relative to the others I believe.

The diagonal centre position that cmhardw suggested does seem relatively hard to solve purely in terms of the centres (because putting any two centres together does not put any adjacent centre together at the same time?)

So perhaps the composition of these two is "hard"?

Does anyone here have some mathematically-based reasoning that they can apply to this?

My solver does not immediately find particularly good solutions to this in OBTM although this is no real indicator of how long its optimal solution might be. Anyone else with a solver care to try?

Here is a 50 OBTM solution: Dw' B' Lw' Dw' D Bw L Dw L2 R F' Dw R B F' Uw' L' U2 B Dw2 R' U' F2 R F2 Dw2 Bw2 R F' R' Bw2 R B D' R U' F' R2 U F D L2 B2 D2 L' D2 B2 L' B L'

It has so far only found a 31 turn reduction that eliminates the parities (without the 3x3x3).

This makes me think... has anyone considered an optimal solver for just the reduction phase (including fixing the parities)? I realise that this would not lead directly to an optimal solver but it might be one way of reducing the upper bound on God's Number for a 4x4x4.

 

[Carrot]

Very. Think about it.. In the past ten years, technology has evolved at an incredible rate. The iPod was invented. The iPhone. New computers, new chips, processors, software. Cloud storage. The price of flash memory is less than 50c per GB now. That's an excellent example. Several years ago, a 1GB card could cost over $100. Now, a 128GB costs almost half of that. These are just a few examples I can think of off the top of my head.

What techonological leap are you implying? Wasn't the iPod just an mp4 player? and the iPhone... wasn't that just a phone with camera, touch screen and music library (I'm pretty sure similar things were already around)?

 

[qqwref]

How about that diagonal center pattern, but with "2-cycles" of centers instead of 3-cycles (e.g. white-red, red-white, green-yellow, yellow-green, blue-orange orange-blue)? Maybe if we add OLL parity to the mix it will be pretty tricky.

Also, an idea: your solver seems to directly solve reduction and then 3x3x3, so what about finding a position that is very hard to reduce and then making it solve a 20f* 3x3x3 position after it?

 

[irontwig]

How about just a scramble where (if possible) there's no one move pairs (wing-wing,wing-corner, wing-centre or centre-centre)?