# God's number proven at 20



## blade740 (Aug 8, 2010)

Www.cube20.org


----------



## penfold1992 (Aug 8, 2010)

it was suspected to be 20 but mearly solving all cases still isnt satisfying... a nice mathematical explanation would do and the guy/girl who does it will probably get a group theory prize too


----------



## hawkmp4 (Aug 8, 2010)

O.O
Awesome! I look forward to hearing more of the results.


----------



## riffz (Aug 8, 2010)

Well this is awesome but disappointing at the same time. The fact that it was brute forced before proven mathematically is somewhat disappointing.


----------



## CUB3R01 (Aug 8, 2010)

This is awesome! I'm glad to see that this has finally been proven.


----------



## Kirjava (Aug 8, 2010)

You're disappointed? It can still be proven with maths - if that happened first humans would probably have never traversed every permutation that exists. We did well to take this route imo ^_^

Did anyone else think of Google's SECRET BEOWULF CLUSTER SUPERCOMPUTER like the Large Hadron Collider for cubers?


----------



## vgbjason (Aug 8, 2010)

God's number is 4:20, you need to edit that typo


----------



## Rinfiyks (Aug 8, 2010)

20 is such a nice round number, this makes me happy


----------



## rokicki (Aug 8, 2010)

*Computational proof*

Every bound since Thistlethwaite's 52 for this puzzle depended on exhaustive search. Earlier, higher bounds were based on the exhaustive search of smaller groups and factor spaces. Some might consider it a feature of Rubik's cube, that the distance of a position cannot be easily estimated by some structural property.

Personally, I was holding out hope for finding a distance-21 position. Now that would have been very nice.

I've been trying to simplify, analyze, and solve this problem using non-exhaustive methods for years, and have come up all but empty. There are some small observations (for instance, some small number of the H-cosets have distance 18) but, in the end, very little "simple structure" to the group that I could figure out how to exploit. For many of these puzzles, I fear that's the nature of the beast.


----------



## MTGjumper (Aug 8, 2010)

I wonder what time Faz gets on the "hardest scramble"


----------



## Tim Major (Aug 9, 2010)

New FMC goal for everyone... get a sub 20 official solution 
Cool... 20 moves for any case...
"Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions."
Haha, loved this sentence.
And what is the average required amount of moves? I realise 18 moves is the most common, but is 15-16 about average?
Coool


----------



## hic0057 (Aug 9, 2010)

I'm wondering if it's a coincidence how there is exactly 20 pieces (12 edges and 8 corners.) This is excluding the core but that doesn't change position.


----------



## rokicki (Aug 9, 2010)

ZB_FTW!!! said:


> And what is the average required amount of moves? I realise 18 moves is the most common, but is 15-16 about average?
> Coool



The average is 17.7; most positions (about 2 in 3) have an optimal solution 18 twists long.


----------



## amostay2004 (Aug 9, 2010)

I wonder what's God's number in STM


----------



## Zubon (Aug 9, 2010)

This is a very significant achievement in the history of the Rubik's cube.

Glad it has finally been done but it does remove some of the mystique surrounding the 3x3.


----------



## hawkmp4 (Aug 9, 2010)

On to 4x4! 

Edit: This isn't serious. Not at this point in time, at least.


----------



## mrCage (Aug 9, 2010)

Exactly how many positions are of maximum distance from solved? And are all these symmetrical positions??

Per


----------



## Christopher Mowla (Aug 9, 2010)

mrCage said:


> Exactly how many positions are of maximum distance from solved? And are all these symmetrical positions??
> 
> Per


"Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are."


----------



## Kryptonite (Aug 9, 2010)

This is awesome. Though I agree, it would have been sweet if there was exactly one distance-21 position we could marvel at.


----------



## RCTACameron (Aug 9, 2010)

hawkmp4 said:


> On to 4x4!
> 
> Edit: This isn't serious. Not at this point in time, at least.



What about 2x2?



hic0057 said:


> I'm wondering if it's a coincidence how there is exactly 20 pieces (12 edges and 8 corners.) This is excluding the core but that doesn't change position.



I wonder if God's Number for 2x2 would be 8 moves.

Anyway, this is amazing.


----------



## irontwig (Aug 9, 2010)

RCTACameron said:


> hawkmp4 said:
> 
> 
> > On to 4x4!
> ...



http://www.jaapsch.net/puzzles/cube2.htm


----------



## aronpm (Aug 9, 2010)

RCTACameron said:


> hawkmp4 said:
> 
> 
> > On to 4x4!
> ...



I thought that was already done, and it was 11.

EDIT: Ninja'd.


----------



## Rinfiyks (Aug 9, 2010)

RCTACameron said:


> hawkmp4 said:
> 
> 
> > On to 4x4!
> ...



Because the 2x2x2 has so little permutations, it can easily be brute forced. Here's a table. God's number is 11 for a 2x2x2.


----------



## mrCage (Aug 9, 2010)

cmowla said:


> mrCage said:
> 
> 
> > Exactly how many positions are of maximum distance from solved? And are all these symmetrical positions??
> ...


 
If there was an exhaustive search that number should be known. Or could have easily been known if implemented Oh well, my main concern was the second question...


----------



## qqwref (Aug 9, 2010)

But there wasn't really an exhaustive search. They didn't bother to optimize solutions because they just needed to show every position could be done in 20 or fewer moves. (As they said they could analyze 2 million positions optimally per second, but prove 1 billion positions to have a solution of 20 or fewer moves, it would probably have taken some decades at Google's server farm to compute optimal solutions for everything. That is, 17500 computer-years.)


----------



## Zarxrax (Aug 9, 2010)

Now that they know which solutions need 20 moves, they could take a look specifically at those, and try to reduce the numbers... right?


----------



## Kabuthunk (Aug 9, 2010)

This is awesome. Although on the cube20 site, we can't use the numbers at the bottom to find the 'average' number of moves needed to solve, since they stated on the page that they didn't "optimally" solve each position, just found a solution of 20 or less.

But yeah... I'm surprised there's still well over a hundred million (at least 300 mil on the site, but not 'optimally' solved) that need a full 20 rotations.

Although I'm curious how they came to their conclusion that "FU-F2D-BUR-F-LD-R-U-LUB-D2R-FU2D2" was the hardest solve for the computers.


----------



## Bryan (Aug 9, 2010)

Zarxrax said:


> Now that they know which solutions need 20 moves, they could take a look specifically at those, and try to reduce the numbers... right?



All you need is one solution that can't be reduced, and they say they have those.


----------



## hawkmp4 (Aug 9, 2010)

Zarxrax said:


> Now that they know which solutions need 20 moves, they could take a look specifically at those, and try to reduce the numbers... right?



No need to, really- there are some positions that can't be solved in any less than 20 moves. 20 is the lowest upper bound we'll ever have.


----------



## cuBerBruce (Aug 9, 2010)

mrCage said:


> cmowla said:
> 
> 
> > mrCage said:
> ...



The number of symmetric positions that require 20 moves to solve is exactly 1,091,994 (source:  http://kociemba.org/math/c1.htm). All the rest of the known 20f* positions are unsymmetric. (Some undoubtedly have symmetry in edges only or corners only.)

A list of some of the known 20f* positions can be found here. This list only includes 1 position for each set of positions that are equivalent with respect to symmetry & antisymmetry.

I understand the group is thinking about the creation of a BOINC project to get the exact number of positions at each distance from solved. That may not happen for awhile, though.

My raw video of the announcement at US Nationals is embedded here.


----------



## Kryptonite (Aug 9, 2010)

irontwig said:


> RCTACameron said:
> 
> 
> > What about 2x2?
> ...





Rinfiyks said:


> Because the 2x2x2 has so little permutations, it can easily be brute forced. Here's a table. God's number is 11 for a 2x2x2.



Anyone know what available programs can do it?


----------



## Herbert Kociemba (Aug 9, 2010)

Kabuthunk said:


> .
> 
> Although I'm curious how they came to their conclusion that "FU-F2D-BUR-F-LD-R-U-LUB-D2R-FU2D2" was the hardest solve for the computers.



For a coset of the subgroup H=<U,D,R2,L2,F2,B2> which has about 20 billion elements we generated in principle (because we need only one bit per element) the optimal solutions for all elements of this coset which have <=15 moves and eventually a fraction of all elements which have 16 moves. Appending now 5 moves (15) or 4 moves (16) only from subgroup H nonoptimal-solutions for almost all other elements of the coset are generated. This reminds in some way on the two-phase algorithm and there is indeed a close connection to the method.

Those elements which cannot be solved in this way are in a certain sense hard and are solved via the two-phase algorithm one by one. The longer phase 1 has to be, the harder the positions are. The position above needs 18 moves in phase 1 and has only 2 moves in phase 2 (U2D2). Try for example Cube Explorer (though a faster version of the two-phase alg developped by Tom Rokicki was used for the computations) and it will take some time to find the solution.

This explanations is a bit simplified but gives almost the right picture.


----------



## qqwref (Aug 9, 2010)

Herbert Kociemba said:


> For a coset of the subgroup H=<U,D,R2,L2,F2,B2> which has about 20 billion elements we generated in principle (because we need only one bit per element) the optimal solutions for all elements of this coset which have <=15 moves and eventually a fraction of all elements which have 16 moves. Appending now 5 moves (15) or 4 moves (16) only from subgroup H nonoptimal-solutions for almost all other elements of the coset are generated. This reminds in some way on the two-phase algorithm and there is indeed a close connection to the method.



Aha! I had been wondering exactly how you quickly computed solutions over an entire coset. This is a clever way to do it.


----------



## badmephisto (Aug 9, 2010)

This is great news! Huge thanks to Google for sponsoring this, wow.

I always thought it should be 20 only because of symmetry arguments: the superflip is 20... In my mind the entire state space is like a diamond with one vertex the solved position, and the opposite vertex the superflip. Of course, there are MANY other positions with 20 moves, maybe these are some other verteces of this high dimensional diamond  
or something.

awesome news!


----------



## Whyusosrs? (Aug 10, 2010)

*Rubiks cube solvable in 20 moves or less*

http://cube20.org/

Would like alg for super flip in 20 moves. Anyone else have more info on this?


----------



## Ranzha (Aug 10, 2010)

R' U2 B L' F U' B D F U D' L D2 F' R B' D F' U' B' U D'.
It's on the page.


----------



## cuBerBruce (Aug 10, 2010)

Whyusosrs? said:


> http://cube20.org/
> 
> Would like alg for super flip in 20 moves. Anyone else have more info on this?





Ranzha V. Emodrach said:


> R' U2 B L' F U' B D F U D' L D2 F' R B' D F' U' B' U D'.
> It's on the page.



No, that's a suboptimal 22-move alg that they showed. Optimal algs can be found here.

Well, actually that alg is optimal in the QTM metric, but not FTM.


----------



## Rinfiyks (Aug 10, 2010)

Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.


----------



## irontwig (Aug 10, 2010)

Rinfiyks said:


> Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.



That sounds way low, as the 4x4x4 has more than twice the number of pieces than the 3x3x3. If I would guess the 4x4x4 would be closer to 40 moves. Does anybody know upper and lower bounds of the 4x4x4?


----------



## Rinfiyks (Aug 10, 2010)

irontwig said:


> Rinfiyks said:
> 
> 
> > Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.
> ...



If you do 10 inner+outer face scramble moves, that messes up the 2x2 centres and the edges, then you have another 20 outer face only moves for the edges and corners, I don't think it should be much higher than 30.


----------



## Thomas09 (Aug 10, 2010)

Faskinating.


----------



## qqwref (Aug 10, 2010)

Rinfiyks said:


> Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.



Without using slice moves on the 4x4, and allowing only Rw/Uw/Fw (since Lw/Dw/Bw are equivalent), at least 34 moves are required to be able to get to every position (that is, to have at least as many possible scrambles as there are positions ignoring cube rotation).

Similarly, but allowing all six double-layer turns, at least 50 moves on a 5x5 are required to be able to get to every position.

(If you're interested, you need at least 73 moves for 6x6 and 95 for 7x7, by the same technique.)


----------



## cuBerBruce (Aug 10, 2010)

qqwref said:


> Rinfiyks said:
> 
> 
> > Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.
> ...



Well, first you need to define what you mean by a "move."

Dan Hoey proved that some 4x4x4 positions require at least 37 single-layer quarter-turns, or at least 41 quarter-twists (which some people now call face quarter-turn metric). I think simple lower bounds for half-turn metrics are 29 for block turns (moving any contiguous set of parallel layers with respect to the rest of the cube), and 32 for single-layer turns. qqwref indicated 34 twists (face turns) is a lower bound. 

For upper bounds (4x4x4 half-turn metrics), I have proven 67 block turns, 77 single-layer turns, or 82 twists. (The nested subgroups I chose for my analysis wasn't particularly suited for getting a good twist metric upper bound, so that's why the twist turn number is rather high.)

As with the 3x3x3, the actual God's numbers are expected to be much closer to the known lower bounds.


----------



## brunson (Aug 10, 2010)

ZB_FTW!!! said:


> New FMC goal for everyone... get a sub 20 official solution
> Cool... 20 moves for any case...
> "Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions."
> Haha, loved this sentence.
> ...



We should start scoring FMC like par in golf, you don't get a 23, you get a 3 over. 

Edit: How confident are we that Thistlewait/Kociemba generates the optimal solution? If we're certain then we would score plus/minus away from optimal.


----------



## Lars Petrus (Aug 11, 2010)

I *really* don't mean to be a party pooper, but to be precise:

Unless I've missed something this is so far only a *claim* of a proof, right? I certainly haven't seen an actual proof that I can verify or falsify.

I don't for a second believe that the authors are making this up, though that does occasionally happen even among very reputable scientists. 

A more realistic concern is that there could be a subtle bug in the code, or that something flaky happened in one of the 55 million separate runs.

Proofs like these are tricky since it's very hard to prove that a non trivial piece of code does what it's intended to do. I don't know how science in general handles this issue.


----------



## uberCuber (Aug 11, 2010)

Lars Petrus said:


> I *really* don't mean to be a party pooper, but to be precise:
> 
> Unless I've missed something this is so far only a *claim* of a proof, right? I certainly haven't seen an actual proof that I can verify or falsify.
> 
> ...



this is a big reason why i am disappointed that it was proved (possibly?) by brute force rather than mathematically


----------



## qqwref (Aug 11, 2010)

brunson said:


> We should start scoring FMC like par in golf, you don't get a 23, you get a 3 over.
> 
> Edit: How confident are we that Thistlewait/Kociemba generates the optimal solution? If we're certain then we would score plus/minus away from optimal.


But it is impossible to beat the optimal solution.



Lars Petrus said:


> Unless I've missed something this is so far only a *claim* of a proof, right? I certainly haven't seen an actual proof that I can verify or falsify.
> 
> [...]
> 
> A more realistic concern is that there could be a subtle bug in the code, or that something flaky happened in one of the 55 million separate runs.


Good point. This is not a mathematically rigorous proof but rather a series of computations that - *if* the code and assumptions are all correct - solves the problem. In this way it is similar to the 4-color theorem proof. I would be interested in seeing a proof-like analysis that the code is correct.


----------



## Tord (Aug 11, 2010)

*Excellent!*

I, too, would like an uniformly mathematical proof. Nevertheless, I embrace progress. Huzzah for google!

On a side note; A small notice in Aftenposten (norwegian newspaper), dated 11/8-10, reported this discovery. The 75 words of the "article" said little, but the online article said more.


Spoiler



If interested, one might google translate it, only to discover that the article contains a small amount of content regarding the actual solution.


----------



## Krible (Aug 11, 2010)

*Can be solved on less than 20 moves*

I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.

Sources:
Article
History of God's number


----------



## Edward (Aug 11, 2010)

Yeah this is kind of old news =/


----------



## uberCuber (Aug 11, 2010)

Krible said:


> I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
> 
> Sources:
> Article
> History of God's number



lol you post that in a thread where the first post gives the article telling us this...wow


----------



## TheCubeMaster5000 (Aug 11, 2010)

> I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
> 
> Sources:
> Article
> History of God's number



READ OP before you post reply!


----------



## mr. giggums (Aug 11, 2010)

TheCubeMaster5000 said:


> > I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
> >
> > Sources:
> > Article
> ...



I think a mod merged the threads and this was origally a different thread.


----------



## TheCubeMaster5000 (Aug 11, 2010)

mr. giggums said:


> TheCubeMaster5000 said:
> 
> 
> > > I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
> ...



Oh really? I thought the other thread was just deleted.


----------



## rokicki (Aug 11, 2010)

*Computer proof*

Yes, this is a computer proof. We will be releasing code, but not for a while.

We too were concerned about things like hardware reliability and bugs. We did as much as we could to not be tripped up by this. In particular:

1. Almost every single position was actually solved *twice*, not just once. Thus, an error in a single run would almost certainly not affect the overall result. The subset of positions not checked twice is small (but, alas, not small enough to easily check in full). I may yet attempt to check that subset exhaustively, at which point we can say for certain that every position has been checked twice.

2. Along the way we generated numbers that reproduced earlier results by other researchers, including the count of positions at distances 0 through 14, and also generated a *new* result, the count of positions at 15, which we hope to have verified soon by another researcher running code in Germany. Generation of these numbers required every single one of the 55,882,296 runs to be correct (at least up to that point).

3. We used a single program to do the bulk of the calculations; this is a much faster version of the earlier programs used for 22 and 23 and the other bounds. We have compared the output of this program with the output of the earlier versions, and with the output of an independent implementation (sharing no code), and with the output of a much simpler version that is also much slower, and found no disagreements.

4. It turns out, every single position has a distance-20 solution that can be found reasonably easily, except about 100K positions. We solved this set of positions numerous times. (We *wanted* there to be a 21).

5. The code embeds distinct methods for computing the same result (to a certain extent); we compared results with and without the "fast" code for a large set of cosets.

6. We include all sorts of checksumming of the output files, verification of the pruning tables after each run (to make sure no bits flipped), and many other defensive programming techniques to guard against errors.

7. The technique and results from it have been published over the past five years on Cubelovers, and we have had independent confirmation of many of the results by separate implementations. The code originated back in 2005, and every version of the program has been extensively checked against prior versions and against the results generated by the prior versions over this time period.

We would not be publishing this result if we were not certain of it.

I would love for there to be a nice concise mathematical proof. But so far no one has been able to come up with it. The technique we use is straightforward, the optimizations are straightforward, and we have checked the result extensively.


----------



## DT546 (Aug 11, 2010)

it was in the new scientist


----------



## cmhardw (Aug 12, 2010)

DT546 said:


> it was in the new scientist





> It has taken 15 years to get to this point, but it is now clear that every possible scrambled arrangement of the Rubik's cube can be solved in a maximum of 20 moves – *and you don't even have to take the stickers off.*



I literally groaned out loud. Why?! In an article written for a scientific audience? :fp

Chris


----------



## qqwref (Aug 12, 2010)

Because appealing to people's stupidity is still cool?

I'd like to see someone find a way to solve in less than 20 remove-and-replace-a-sticker moves... don't people realize it's actually more difficult to deal with the stickers?


----------



## buelercuber (Aug 12, 2010)

just saw this on Kotaku 

http://kotaku.com/5610473/the-number-20-is-gods-number?skyline=true&s=i


----------



## Lars Petrus (Aug 12, 2010)

rokicki said:


> Yes, this is a computer proof. We will be releasing code, but not for a while.
> 
> We too were concerned about things like hardware reliability and bugs. We did as much as we could to not be tripped up by this. In particular:
> 
> ...



Sounds good. I don't doubt it's correct.

If you're a science proof nerd, check out the Wikipedia article on computer assisted proofs. Perhaps this proof should be added to the example section?


----------



## Alex DiTuro (Aug 14, 2010)

*Was an international study really necessary?*

"An international team of researchers using computer time lent to them by Google has found every way the popular Rubik's Cube puzzle can be solved, and showed it can always be solved in 20 moves or less."

Apparently, they've finally figured it out!!!! :fp

They used some supercomputer to find god's algorithm. Was this really necessary? ugh...

 http://videogames.yahoo.com/events/plugged-in/study-uncovers-every-possible-rubik-s-cube-solution/1407748


----------



## shelley (Aug 14, 2010)

Why the facepalm? Was it such a trivial problem you had figured it out already?

Also, where have you been? This was fairly big news for the cubing community.


----------



## hawkmp4 (Aug 14, 2010)

Alex DiTuro said:


> Apparently, they've finally figured it out!!!! :fp
> 
> They used some supercomputer to find god's algorithm. Was this really necessary? ugh...



You talk about it like it's a bad thing...


----------



## hic0057 (Aug 14, 2010)

_"The research, published online, ends a 30-year search for the most efficient way to correctly align the 26 colored cubes that make up Erno Rubrik's 1974 invention."[/U]_[/U]

Last time i count there was 20 colored cubes and 1 core not 26. They count the core in 6 piece not just 1.


----------



## hawkmp4 (Aug 14, 2010)

hic0057 said:


> _"The research, published online, ends a 30-year search for the most efficient way to correctly align the 26 colored cubes that make up Erno Rubrik's 1974 invention."[/U]_[/U]
> 
> Last time i count there was 20 colored cubes and 1 core not 26. They count the core in 6 piece not just 1.



8 corners + 12 edges + 6 centres. I think it's a forgivable offense. At least they realised that the cube is comprised of pieces, not just stickers.


----------



## aronpm (Aug 14, 2010)

You are a retard.


----------



## qqwref (Aug 14, 2010)

aronpm said:


> You are a retard.


This.


Also, "international team" does not mean several hundred people from different countries and millions in grant money. It means a handful of people who don't happen to be from the same country (because, hey, they met and shared a lot of their research online, so country is irrelevant). What, do you think people from different countries shouldn't be allowed to work together on the same project? You fail.


----------



## Hyprul 9-ty2 (Aug 14, 2010)

When qq flames, you know you suck.

Edit: Gavin ur doin it wrong


----------



## Edward (Aug 14, 2010)

Alex DiTuro said:


> Was this really necessary? ugh...




Was this really necessary? uguu...


----------



## krnballerzzz (Aug 14, 2010)

I don't understand the OP's frame of mind. Wasting resources for the sake of figuring out something useless? That can be applied to like 90% of the things in our lives outside medicine, food, and basic hygiene. Maybe he's trying to troll us. Hmmm~


----------



## Rinfiyks (Aug 14, 2010)

http://videogames.yahoo.com/events/...-every-possible-rubik-s-cube-solution/1407748
"The research, published online, ends a 30-year search for the most efficient way to correctly align the 26 colored cubes that make up Erno *Rubrik*'s 1974 invention."


----------



## MTGjumper (Aug 14, 2010)

Eugh, the Daily Mail did a small article on this: I don't have it to hand, but they put in a flippant comment saying something along the lines of "but there still might be a 21-move scramble, because not every position was checked". I think they interpreted the fact that the number of cases solved was reduced by so many factors due to symmetry and whatnot meant that the the results were simply extrapolated.

For what it's worth, they have an online article that isn't the same, and doesn't make short-sighted conclusions like the one in the paper.


----------



## guusrs (Aug 14, 2010)

Awesome achievement! I didn't expect this till 2024 (50 years after Rubik invented the cube) 
I already thought it was 20 moves during a very long time, about 25 years, but that was based on statistical calculation.
Gus


----------



## tkcube1 (Aug 14, 2010)

*Breaking News on Rubiks Cube!*

Ok I haven't been in this forum alot since I quit cubing, but I saw this and looked at the most recent threads and nothing has been posted so here it is. http://videogames.yahoo.com/events/...-every-possible-rubik-s-cube-solution/1407748 . I found this on the front page of Yahoo. It appears that it can be solved in 20 moves or less every time. Sorry if this has been posted, like i said, I don't keep up with this stuff anymore.


----------



## Olji (Aug 14, 2010)

just some day ago that was a pretty hot topic here x)


----------



## CubesOfTheWorld (Aug 14, 2010)

If you don't keep up, use the search function.


----------



## tkcube1 (Aug 14, 2010)

I honestly didn't feel like it. Sorry guys.


----------



## ariasamie (Aug 14, 2010)

tres.60 said:


> http://www.speedsolving.com/forum/showthread.php?t=23101&highlight=proven+20



lets get more accurate:
http://www.speedsolving.com/forum/showthread.php?p=434467#post434467


----------



## cuBerBruce (Aug 14, 2010)

Why was this moved to Off-Topic Discussion? I think this thread belongs in Puzzle Theory if any thread does.


----------



## ExoCorsair (Aug 14, 2010)

cuBerBruce said:


> Why was this moved to Off-Topic Discussion? I think this thread belongs in Puzzle Theory if any thread does.



One of the mods keeps moving it to Off-Topic for whatever reason.


----------



## masterofthebass (Aug 14, 2010)

ExoCorsair said:


> cuBerBruce said:
> 
> 
> > Why was this moved to Off-Topic Discussion? I think this thread belongs in Puzzle Theory if any thread does.
> ...



I actually think chris is "at fault" here. His merging of various threads moved it around (looking back at the moderator log).


----------



## cmhardw (Aug 14, 2010)

masterofthebass said:


> ExoCorsair said:
> 
> 
> > cuBerBruce said:
> ...



Good to know, I did merge the various repeat threads together. I'll pay more attention to where the merged group ends up next time.

Chris


----------



## mrCage (Aug 14, 2010)

This results is quite intriguing, but "expected" i guess. However it will have no implications on how scrambling (or solving) will be done now or in the future.

Still pretty cool to have done fewest moves in less than 20 moves, altough the actual acramble of course had shorter optimal solution. One of my 19 solutions had a 18-turn optimal solution

Per


----------



## uberCuber (Aug 14, 2010)

mrCage said:


> This results is quite intriguing, but "expected" i guess. However it will have no implications on how scrambling (or solving) will be done now or in the future.
> 
> Still pretty cool to have done fewest moves in less than 20 moves, altough the actual acramble of course had shorter optimal solution. *One of my* 19 solutions had a 18-turn optimal solution
> 
> Per



you've had more than one?


----------



## rokicki (Aug 16, 2010)

*15f* result confirmed*

I'm happy to announce that our 15f* result (which accounted for a fair percentage of our overall computation) was just confirmed today by Thomas Scheunemann. This is a independent code, an independent team, and independent hardware. While it does not confirm our proof of 20 in its entirety, it does confirm a result that requires about 13% of our overall effort and about 80% of our codebase, including our set cover, our entire search phase, the prepass, and much more.

If there were an error in any single one of the coset runs (up to level 15), or if we omitted one or counted one twice, or if there was a problem in the set covering, these two results would not have agreed.


----------



## qqwref (Aug 16, 2010)

Awesome! Of course, by showing that the number of 21f* is zero, and getting all the way up to 15f*, you've made me wonder... how much more calculation would it take to get the last five numbers? I know the average is 17.7 or so, so most cubes will be in that range, and it will probably take many times what you've already done. Would it be closer to a month on a Google farm? A year? A decade?


----------



## Kirjava (Aug 16, 2010)

God's alg rainbow tables.


----------



## rokicki (Aug 16, 2010)

Kirjava said:


> God's alg rainbow tables.



You're not far off!

Long term I plan to make this a BOINC project, and let whoever wants to work on it with their machines (and a nice graphical display of cubes per second or rotating, changing cubes or something like that).

To finish off the distribution, I've got some ideas up my sleeve---but I estimate it would probably take about 500 times the effort. So call it, for better or worse, 17 CPU millennium. The good news is Moore's law is getting us closer all the time.

The good news is we can find a lot of intermediate interesting things, like 16f*, 17f*, and indeed just enumerating the 20f*'s is interesting at some level. And just the slow and steady progress; every CPU night (say ten hours) grinds through some hundred billion positions or so (plus all the rotations of said positions) and will probably find a handful of new 20f*'s.

It may take a few years to get the project up and working fast enough (this is just a hobby after all), but who knows what will happen.

But maybe in five years, desktops cease to exist and everything is done on mobile platforms like phones and (relatively slow) tablets, and then BOINC goes nowhere.

We shall see.


----------



## Cool Frog (Aug 16, 2010)

Why does it have to be called "god's" algorithm... everyone knows its the FSM that is the higher power of the universe...
how long is the solution to the evil edge flip if the flipped all but for say two.. or flipped two corners...?


----------



## hawkmp4 (Aug 16, 2010)

Cool Frog said:


> how long is the solution to the evil edge flip if the flipped all but for say two.. or flipped two corners...?



I don't know. Fire up Cube Explorer and let us know, yeah?


----------



## Cool Frog (Aug 16, 2010)

hawkmp4 said:


> Cool Frog said:
> 
> 
> > how long is the solution to the evil edge flip if the flipped all but for say two.. or flipped two corners...?
> ...



Will not let me load the website... Great connection, can click any other link but not that one...


----------



## Rinfiyks (Aug 21, 2010)

hawkmp4 said:


> Cool Frog said:
> 
> 
> > how long is the solution to the evil edge flip if the flipped all but for say two.. or flipped two corners...?
> ...



Superflip + M2 E2 S2
U R F D R U' D L' U' D F' B2 R L' D' F' L' B' R' (19f*)

Superflip with FU and BD corners orientated correctly
D2 B2 L2 B2 D' L2 D U L2 B' F' L' D U' B' L' R' U' (18f*)


----------



## qqwref (Aug 22, 2010)

rokicki said:


> But maybe in five years, desktops cease to exist and everything is done on mobile platforms like phones and (relatively slow) tablets



Gee, I hope not. I hate those things. Mouse+keyboard is far better than touch, and I will always prefer big screens to tiny.


----------



## mrCage (Oct 14, 2010)

qqwref said:


> Gee, I hope not. I hate those things. Mouse+keyboard is far better than touch, and I will always prefer big screens to tiny.


 
Desktops will exist in the foreseeable future, due to gamers and other power users. Mobility is not the only driving force

Per


----------



## deadalnix (Oct 14, 2010)

Hi,

Is theyre any scientific publication about this result ?


----------



## Tim Major (Oct 14, 2010)

There was an article in _The Australian_ newspaper


----------



## rokicki (Oct 15, 2010)

deadalnix said:


> Hi,
> 
> Is theyre any scientific publication about this result ?


 
The new paper is in preparation. In the meantime, the technique is the same as was used for 22, with some technological improvements and one additional insight that helped. The paper for 22 is linked from the cube20 website, but here's the link again:

http://www.springerlink.com/content/q088143tn805k124/


----------



## Cubenovice (Dec 7, 2010)

Been playing around a little with the "hardest scramble":
F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2

What do I see?
U D edges flipped in place
middel layer edges flipped in "opposite positions"
Corners not quite, but after D2 U2:
All corners flipped in place
All edges "opposite flipped"

From the original scramble:

Simple route to cross: R L F B R L D U
U gives me two crosses!
Middle layer edges in position but flipped!
R and L can be OLL'd in f-SM-SM-f' style:
B L D L' D' L D L' D' B'
F R D R' D' R D R' D' F

Leaves a solved belt plus two solved faces plus 4 L-sides
L-sides have two pairs which can be alternately "solved" by L2 or R2
Bonus: you break an existing pair and build a new one
This looks so nice and I would like to believe there is an elegant finish to this cube pattern.

Anyway, back to OLL for R and L layers.
Who can tell me how to do this in one alg?
Note that these two sides seperately are actually "unsolvable": on both faces two edges need to be exchanged.
So this opposite-side-OLL would have to tackle this too...

What I did in my actual solve: set up - Z or H perm - undo set up to switch two edges on each face
Leaving both R and L face in combinations of N, V or F perm to finish the cube


Another question, how could I extract this -double-OLL-with-parity alg from Cube explorer?
I managed to get a 13 move finish after the D + U cross but how do I enter a "target" state?
I tried leaving grey facelets for all but the belt and the orange / red stickers to be OLL'ed but it would not accept it.

13 move finish after the double cross: L2 B2 L D2 L2 D2 B2 U2 F2 R2 F2 R' U2


----------



## rokicki (Oct 13, 2011)

Source code is released: http://cube20.org/src/


----------



## QPowerPrime (Nov 10, 2014)

penfold1992 said:


> it was suspected to be 20 but mearly solving all cases still isnt satisfying... a nice mathematical explanation would do and the guy/girl who does it will probably get a group theory prize too


Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and if you own a computer, it shouldn't be too hard, so why did it take some google supercomputers to work it out?


----------



## guysensei1 (Nov 10, 2014)

QPowerPrime said:


> Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and iff you own a calculator, it shouldn't be too hard, so why did it take some google supercomputers to work it out?


You think it's possible to check all the 20 move Algs 'with a calculator'?


----------



## Christopher Mowla (Nov 10, 2014)

QPowerPrime said:


> Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and iff you own a calculator, it shouldn't be too hard, so why did it take some google supercomputers to work it out?


That's a good question, but you have to realize two things:
[1] The number of algorithms drastically increases as the move length increases. So there are A LOT more 15 move algorithms than 14 move algorithms, for example.
[2] We do not have enough memory to store/keep track of all unique positions reached with each move sequence.

As far as what you quoted penfold1992 saying, I agree. It would be much more satisfying if this was proved without brute force.


----------



## qqwref (Nov 11, 2014)

QPowerPrime said:


> Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and iff you own a calculator, it shouldn't be too hard, so why did it take some google supercomputers to work it out?


Do you have any idea how much 43 quintillion is? It's 43 million million million.

Have fun doing it by hand on a calculator. I'll see you in a couple of million million years.


----------



## Cube Is Life (Nov 11, 2014)

QPowerPrime said:


> Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and iff you own a calculator, it shouldn't be too hard, so why did it take some google supercomputers to work it out?



You can't count the same cube twice and some 6 move algs give you the same cube as some 0 move algs. So the super computer had to figure out wich ones will give you unique cubes.


----------



## WinPooh (Nov 11, 2014)

QPowerPrime said:


> Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and iff you own a calculator, it shouldn't be too hard, so why did it take some google supercomputers to work it out?



You need to store some information about seen positions somewhere. Even 1 bit per position x 43 quintillion will require very large storage...
43 * 10^18 bit = 5 * 10^18 bytes
Lets use terabyte hard drives (10^12 bytes each). We need 43 000 000 discs. Maybe Google does have 43 million HDDs, but I doubt there exist any manager in Google who will approve using them for such task


----------



## Tony Fisher (Nov 12, 2014)

QPowerPrime said:


> Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and if you own a computer, it shouldn't be too hard, so why did it take some google supercomputers to work it out?


I love the way you say "it shouldn't be too hard". Perhaps for the 4x4x4 they will ask you how to do it. 43 quintillion is a very big number and it's not as if it has to 'just' do that number of straight calculations. It would need to run a program that did various things like check for repeated positions and know how to actually go through all the moves of each set of algs.


----------



## LNZ (Nov 12, 2014)

According to people who actually do such calculations, there are about 490 million depth 20 positions in HTM.


----------



## elrog (Nov 16, 2014)

QPowerPrime said:


> Can't you just do all the different 1 move algs, then all the 2 move algs, then all the three move algs, etc. until you reach 43 quintillion, and if you own a computer, it shouldn't be too hard, so why did it take some google supercomputers to work it out?


When I was relatively new, I asked a very similar question. I will do my best to explain why this doesn't work.

If you add up every possible 1 move alg, 2 move alg, and so on, you will reach 43 quintillion after 18 moves. The reason for this is that a 15 move alg may solve the same position of a 7 move alg you already counted earlier, so reaching 43 quintillion algs isn't the same as reaching 43 quintillion states. To filter through the states you have already counted, you would need a database of every possible state. This would take a lot of storage space and you would need a million million years (as previously stated) to sort through it.

And just for you information, this is how the lower bound of 18 moves was established.


----------

