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

[whauk]

this is probably not big news... but i get a lower bound of 33 in OBTM by counting. there are 9 axes (R, U, L, D, F, B, Rw, Uw, Fw) and 3 possible turns on every axis (cw, ccw, 180°). so after n turns we have 27^n positions. so we want to find n such that 27^n > number of permutations on a 4x4x4. solving this inequality for n yields n > 32.04... > 32 so n must be 33 as it is a natural number.
i guess this can't be improved by more than 2-3 moves by removing symmetries, trivial identities...

 

[TDM]

i get a lower bound of 33 in OBTM

If 33 is a lower bound, then

(Amount of layers-1) * 10, +1 for even layered cubes. So
1x1x1 = (1-1) * 10 = 0
2x2x2 = (2-1) * 10 + 1 = 11
3x3x3 = (3-1) * 10 = 20
4x4x4 = (4-1) * 10 + 1 = 31

You could try adding n-1 instead of adding 1 for even numbers. That way, a 4x4x4 would give (4-1)*10+(4-1)=33. For a 10x10x10, you'd get 99. Also "10x10x10 cube in 101 moves" using your formula comes out as 91, not 101 as you said.

 

[ben1996123]

If 33 is a lower bound, then

You could try adding n-1 instead of adding 1 for even numbers. That way, a 4x4x4 would give (4-1)*10+(4-1)=33. For a 10x10x10, you'd get 99. Also "10x10x10 cube in 101 moves" using your formula comes out as 91, not 101 as you said.

that formeuler is silly

I want to know optimal movecount for megaminx superflip too

 

[qqwref]

and by "we" you mean "you and a couple of other people in the speedcubing community that understand math" and actually write things like "Θ" online, right?

I was referring more to the cube theory community as a whole - not in the sense that specific people know the information, but that it is information which has been publicly published and which we have access to.


Optimal megaminx patterns are likely to remain unknown for a while - there are just too many ways of going around the cube, and you can't apply 3x3x3 techniques like you can for 4x4x4 (at least for patterns occupying most of the minx).

 

[IAssemble]

I was referring more to the cube theory community as a whole - not in the sense that specific people know the information, but that it is information which has been publicly published and which we have access to.


Optimal megaminx patterns are likely to remain unknown for a while - there are just too many ways of going around the cube, and you can't apply 3x3x3 techniques like you can for 4x4x4 (at least for patterns occupying most of the minx).

At least ben1996123 didn't ask for God's Number for the Megaminx!

According to wikipedia there are close to 1.01x10^68 positions on a 12 colored Megaminx.

I calculate that there are 4x12 possible first moves and after that 4x11 possible moves to continue without trivial cancellation (although many short sequences would be equivalent) (4 angles for each of 12 or 11 faces)

So N moves would reach no more than 4x12x(4x11)^(N-1) unique positions.

So for a (very weak) lower bound:

For 41 turns this would be ~2.6x10^67 which is not enough to reach all possible positions.
For 42 turns this would be ~1.1x10^69

I believe this means God's Number for the 12 colored Megaminx is at least 42

EDIT1: I should have googled it first!

EDIT2: and reading this I now see a flaw in my reasoning about positions that are reachable in fewer than N moves... perhaps I should read up about this a bit more!

 

[Jakube]

this is probably not big news... but i get a lower bound of 33 in OBTM by counting. there are 9 axes (R, U, L, D, F, B, Rw, Uw, Fw) and 3 possible turns on every axis (cw, ccw, 180°). so after n turns we have 27^n positions. so we want to find n such that 27^n > number of permutations on a 4x4x4. solving this inequality for n yields n > 32.04... > 32 so n must be 33 as it is a natural number.
i guess this can't be improved by more than 2-3 moves by removing symmetries, trivial identities...

By ignoring cases like R R', R L R2, ... you get a lower bound of 35.
I build a recursive function: a(n) = 5832*a(n-4)+2268*a(n-3)+432*a(n-2), a(0) = 0, a(1) = 27, a(2) = 648, a(3) = 15066.
I had a few beers earlier, but it should be correct. I will check it tomorrow again though.

 

[mDiPalma]

This is probably a stupid question, but...

can it be proven/disproven that all 4x4x4 states can be reached by applying a 3x3x3 scrambling sequence followed by a 2x2x2 scrambling sequence (holding 2 layers as 1)?

That might suggest a very low upper bound.

 

[Username]

This is probably a stupid question, but...

can it be proven/disproven that all 4x4x4 states can be reached by applying a 3x3x3 scrambling sequence followed by a 2x2x2 scrambling sequence (holding 2 layers as 1)?

That might suggest a very low upper bound.

Does comparing the amount of 4x4 positions with gods number on 2x2 and 3x3 help at all with this?

 

[mDiPalma]

Does comparing the amount of 4x4 positions with gods number on 2x2 and 3x3 help at all with this?

I don't think so directly. There may or may not be a state that requires both an 11 move 2x2 scramble and a 20 move 3x3 scramble. The upper bound could be 30 or ever 29, considering cancellations.

But my proposal is nearly completely implausible.

 

[ben1996123]

This is probably a stupid question, but...

can it be proven/disproven that all 4x4x4 states can be reached by applying a 3x3x3 scrambling sequence followed by a 2x2x2 scrambling sequence (holding 2 layers as 1)?

That might suggest a very low upper bound.

dispruf: there are 3674160 states on a 2x2 and 43252003274489856000 on a 3x3, multiply them to represent combining a 2x2 and 3x3 scramble = 1589147803509597097320960000 wich is alot less than 7401196841564901869874093974498574336000000000

 

[qqwref]

Can we get to all 4x4x4 positions by applying a 3x3x3 scramble, then a 2x2x2 scramble, then another 3x3x3 scramble?

EDIT: Never mind, any positions with solved centers and unpaired edges are impossible


EDIT2:

By ignoring cases like R R', R L R2, ... you get a lower bound of 35.
I build a recursive function: a(n) = 5832*a(n-4)+2268*a(n-3)+432*a(n-2), a(0) = 0, a(1) = 27, a(2) = 648, a(3) = 15066.
I had a few beers earlier, but it should be correct. I will check it tomorrow again though.

I get that 34 turns are enough (there are 3.422... * 10^46 positions). Also, for the 4x4x4 supercube, with 7.072 * 10^53 positions, 40 turns are enough. These results echo ones I have from several years back, which is cool.

Similarly, if anyone's curious, 50 turns are enough for the 5x5x5, and 63 are enough for the 5x5x5 supercube.

 

[cuBerBruce]

Lower bounds for up to 20x20x20 cubes for six different metrics can be found here. Also, lower bounds for 100x100x100 are given. (q/h-s = single-layer turns, q/h-w = outer block turns, q/h-b = block turns = any block of contiguous layers turned together)

 

[qqwref]

Would I be correct in supposing that that approach treats RL and LR as the same? My numbers above did not do that, but just worried about not using cancelling moves such as RwRRw. (Also, I think your equivalent of my metric is h-w.) Using a canonical ordering for moves on the same axis, the four numbers I gave (34, 40, 50, 63) become 35, 41, 52, 65. The 35 and 52 match yours.

 

[cuBerBruce]

Would I be correct in supposing that that approach treats RL and LR as the same?

Yes. For example, on the 4x4x4 from a given position, there are generally 4^3-1 = 63 new positions reachable from just making moves along one axis. (One layer can be regarded as a fixed reference.) The analysis uses one optimal (for the given metric) representation for reaching each of these 63 new states. So LR would not be considered distinct from RL. (But if the L face is treated as the fixed layer, a 3-layer wide R turn would be used in its place of L.)

My numbers above did not do that, but just worried about not using cancelling moves such as RwRRw. (Also, I think your equivalent of my metric is h-w.) Using a canonical ordering for moves on the same axis, the four numbers I gave (34, 40, 50, 63) become 35, 41, 52, 65. The 35 and 52 match yours.

I note that these were not my numbers. (Nor did I invent these abbreviations for the metrics - h-w, etc.) I note that I have produced actual God's algorithm numbers up to a distance of at least 7 for the six metrics in this thread.

 

[windhero]

I dont really get the measurement CPU year as in it's very vague. It doesnt tell anything about the computing power now does it? What ever is the case I would atleast hope that a high end desktop CPU for regular customers would match whatever "super computer" they used a few years back. The technology does evolve at a very fast rate and improving is still very possible regardless of physical limitations that may slow it down in the future.

Does anyone know the computing power of the used CPUs? I know this is just the hardware and someone should actually go ahead and make a much better code for this to happen in our lifetime regardless of the technology advancing, but I'm still curious. I'm not sure if someone has suggested this but it would be fun to think that people would join in on this like on the group projects that are done on the PS3.

 

[Stefan]

I dont really get the measurement CPU year as in it's very vague. It doesnt tell anything about the computing power now does it? What ever is the case I would atleast hope that a high end desktop CPU for regular customers would match whatever "super computer" they used a few years back.

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"

The technology does evolve at a very fast rate and improving is still very possible regardless of physical limitations that may slow it down in the future.

How fast?

 

[spyr0th3dr4g0n]

Would it be possible to determine if its an odd or even number without extensive simulation?

 

[cubernya]

Would it be possible to determine if its an odd or even number without extensive simulation?

I doubt it, since it's normally not odd or even, but just within the upper and lower bounds.

 

[windhero]

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?

Ah my bad.

Well for an example
This: http://www.newegg.com/Product/Product.aspx?Item=N82E16813131817&Tpk=Z9PE-D8 WS&IsVirtualParent=1

with 2 of these
http://www.newegg.com/Product/Product.aspx?Item=N82E16819116492

makes 12 cores @ 3.8ghZ and its very overclockable even close to 4.8ghz.

Nehalem is a 45nm desktop cpu, wouldnt really call it a supercomputer even back in the day or ever. It's just a single CPU that used to be good a few years back. Now a cpu with that capacity can be even seen in low to mid end laptops. The options I suggested are regular desktop cpus as well.

Benchmarks:
3930K @ nearly 12.1k points
http://www.cpubenchmark.net/cpu.php?cpu=Intel+Core+i7-3930K+@+3.20GHz&id=902


Nehalem 2.8ghz quad core aka Xeon x5560 is at nearly 5.8k points
http://www.cpubenchmark.net/cpu.php?cpu=Intel+Xeon+X5560+@+2.80GHz&id=1301


Benchmarks dont tell everything but just by the contrast between the setups you can imagine how a setup with 2x 6-core 12k point benchmarked CPUs perform against a single quadcore at 5.8k benchmark points.

I know people with more expensive gaming rigs so I would say it's very accessible if sponsored by a big company.

When I heard it was sponsored by google I figured it was done by a computer that regular people or even high end gamers dont use but this proves that my assumption was wrong.


Also note that this is an example based on a very quick lookup. I'm sure there's a mobo out there that supports the new hashwell cpus with a dual cpu slot. That setup would be even more powerful (high end 22nm cpus with 8 core each).


EDIT: I noticed that the motherboard I suggested also supports the Xeon E5 series of processors which are the most powerful CPUs to this day that are also available for regular customers.


Also this is what a super computer means in 2012
Thats 72,000 cpus. With a computer like that I suppose it wouldnt even take a day to calculate the gods number for a 3x3 (if all the cpus in this super computers are equivalent to a X5560 it would take 4 hours infact). 4x4 obviosly is a completely different story, I understand that. I also understand that there is no way we could get someone to loan a super computer such as this one even for a minute, not to talk about days. This is why the PS3 (or now ps4) method would be awesome, each console has 8 cores and hundreds of thousands are sold.

The yellowstone supercomputer for one solves 1.5 quadrillion operations per second. I dont know how many operations one 4x4 case requires but I suppose it would be possible to do it even now. The yellowstone is expected to rank in the top 25 in the world so this is just an example of a great super computer in 2012.



The best in 2008 was at 1.7 PFlops. The best of 2013 is at 33.8PFlops. I'd say they evolve very fast.

Regular desktop CPUs evolve at an equal rate.

 

[qqwref]

Nehalem is a 45nm desktop cpu, wouldnt really call it a supercomputer
[wall of words]

That's entirely intentional. Think about it this way. Supercomputers can easily vary in computing power by orders of magnitude, the fastest one keeps changing, the computing speed is dependent on much more complex factors (algorithm parallelism, data transfer amount/speed between cores, etc.), and the speed of a supercomputer is hard to get an intuition for unless you've actually done a large computation on one. All this combines to mean that if you ask "how long will this algorithm take to execute on a supercomputer" you will get a wildly inaccurate, ever-changing, and basically irrelevant answer. And oh yeah, supercomputers can actually evolve even faster than personal computers, due to increasing numbers of cores and better networking technology between the cores. And all you have to do to get more cores is buy more, whereas there's a limit to what you can fit in a dekstop. And that's not even considering massive online "supercomputers" like GIMPS, whose speed is basically a product of the number of computers in use and the speed of the individual ones.

So that's why whenever people talk about how many years a computer would take they almost always use a commercially available desktop computer. It's a much better benchmark and is pretty close to the kind of thing many people have in their homes - so saying "this computation took 35 CPU-years" gives the reader a far better idea of how much computation was actually done.