32q upper bound

[cuBerBruce]

Tom Rokicki has now claimed that all Rubik's Cube position can be solved using no more than 32 quarter turns.

http://cubezzz.duckdns.org/drupal/?q=node/view/131

 

[AvGalen]

No coset I have run yet has required more than 26 moves to solve, and
the possible distance-26 positions that I have run through an optimal
solver have all yielded distances less than 26

So why 32 and not 25? Is it because he has only looked at a special group of cosets? Or is there a known position that requires 26 or even 32 moves?

 

[Lucas Garron]

No coset I have run yet has required more than 26 moves to solve, and
the possible distance-26 positions that I have run through an optimal
solver have all yielded distances less than 26

So why 32 and not 25? Is it because he has only looked at a special group of cosets? Or is there a known position that requires 26 or even 32 moves?

I think 35 was the current bound. If I'm interpreting correctly, he ran all the "problem cosets" (396 of them) that took 33-35, and they all turned out to be solvable in 26. Which means that there are some leftover cosets at 32 (not in the 396), but perhaps too many to compute and reduce (below 32, perhaps to 26) the same way right now.
(He declared a bound of 33 first, so I presume he solved the 32s right after.)

I don't know quite how correct this is (or if it's anymore the right idea), but it somewhat corresponds to the HTM analysis.

 

[Johannes91]

Or is there a known position that requires 26 moves?

Yes.

 

[Stefan]

So why 32 and not 25? Is it because he has only looked at a special group of cosets?

Remember for his 25 HTM bound he proved his cosets to be solvable in 20 HTM or less. I think the proof it's a two-phase technique.
http://arxiv.org/pdf/0803.3435v1

Like when you want to want to determine the maximum time anyone needs to travel to Chicago. Chicago has an airport, but not everybody lives at an airport. So what you can do is you determine, for each airport in the world, the time it takes from that airport to Chicago, plus you look at how long it takes people to get to their closest airport. The airport-to-Chicago time corresponds to his 26 QTM, the people-to-their-airport corresponds to the remaining 6 QTM. Although for example some people/cubes might take 7 hours/moves if their corresponding airport/coset only takes 25.

Somewhat like that. Bruce or so please correct me if I'm wrong.

Or is there a known position that requires 26 or even 32 moves?

Yes, Mike Reid found a 26q* in 1998:
http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube#Lower_bounds

 

[AvGalen]

It is a 2-phase proces

I am running phase one to a depth of 19 and letting phase two complete
the coset

I think Lucas is entirely right
And I like Stefans analogy

Does anyone believe that a 21 (HTM) or a 27 (QTM) will ever be found (or even exists)?

 

[Lucas Garron]

Does anyone believe that a 21 (HTM) or a 27 (QTM) will ever be found (or even exists)?

Tom does, sorta. http://cubezzz.homelinux.org/drupal/?q=node/view/129 suggests it's not quite o impossible.

 

[cuBerBruce]

It is a 2-phase proces

I am running phase one to a depth of 19 and letting phase two complete
the coset

I think Lucas is entirely right
And I like Stefans analogy

I think the coset solver itself uses a two-phase process. But solving the positions in the cosets is only one "phase" of the proof. The basic idea of the proof involves first proving that from any scrambled position, you can reach at least one of a small selected set of cosets within N moves. Secondly, the proof shows that any position in each of the selected cosets can be solved in at most M moves, where M + N <= 32.

So basically Tom has divided the 43+ quintillion cube positions into 2.2+ billion cosets. From the 2.2+ billion cosets he has carefully selected 396 so that from any of the 2.2+ billion cosets you can always reach one of the "25-max" cosets in 7 quarter turns (or less) or one of the "26-max" cosets in 6 quarter-turns (or less). (It might very well be that he found 396 cosets such that 6 quarter turns is always sufficient to reach at least one of these 396 cosets.)

Does anyone believe that a 21 (HTM) or a 27 (QTM) will ever be found (or even exists)?

There are over a million 20f* positions and Tom has made a crude estimate of 700 million, so there seems like a very real possibility of a 21f* position, but it seems to becoming more and more doubtful. On the other hand, there are only 3 known 26q* positions (all symmetrically related to each other), and I believe even 24q* positions are rather rare, so it seems to me highly unlikely there is any positions deeper than 26q*.

Edit (appending to this post):
The previous QTM upper bound I knew of was 34 quarter-turns:
http://cubezzz.duckdns.org/drupal/?q=node/view/92
-----
It is interesting that this thread was moved to the "speedcubing" section. In the past, we were told to use "Off Topic Discussion" for general cubing threads not related to speedcubing or any of the other categories provided. I guess the scope of the "speedcubing" section is now wider than it used to be.

 

[Herbert Kociemba]

Some additions to Stefans explanation: We do not determine the distances from all airports in the world to the airport in Chicago but only from a small selection. For all these distances we show that they are <= 26 QTM. The people-to-the-closest-airport-in-this-selection is the remaining 6 QTM. If you want to prove 31 QTM, you must increase the number of airports in this selection so that the people-to-the-closest-airport-in-this-selection is only 5 QTM.

 

[brunson]

Mr. Kociemba, it is certainly a privilege to have you contribute to our forum. Welcome!


Back to the thread, though...

This was an interesting note on the Wiki page Stefan linked to,

In 1998 Michael Reid found a new position requiring more than 24 quarter turns to solve. The position, named by him as 'superflip composed with four spot' needs 26 quarter turns.

First of all that page needs some serious editing because they switch from QTM to HTM and back at will without noting the change in metric, but that aside. This statement was interesting to me because the super flip is the example of a proven 20 HTM case, so I'm going to guess this 26 QTM case is also solvable in 20 HTM?

 

[cuBerBruce]

Mr. Kociemba, it is certainly a privilege to have you contribute to our forum. Welcome!

He's contributed before actually. His post count reads 1 (at the moment) because his other 2 posts were in a thread in the "Off-Topic Discussion" section, and posts there aren't currently counted in a user's post count.

This statement was interesting to me because the super flip is the example of a proven 20 HTM case, so I'm going to guess this 26 QTM case is also solvable in 20 HTM?

Superflip is only one of at least 1,445,274 proven 20f* positions.

Edit: OK, I think that superflip may have a direct mathematical proof of being 20f* while other 20f* positions have probably only been "proven" so by use of computer analysis.

You happen to be correct that the 26q* position is also one of the known 20f* positions. From Reid's web site, it can be created by:

U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B' (26q*, 21f)
F U2 R L D F2 U R2 D F2 D F' B' U2 L F2 R2 B2 U' D (20f*, 28q)

See: http://www.math.ucf.edu/~reid/Rubik/x_symmetric.html

 

[brunson]

Mr. Kociemba, it is certainly a privilege to have you contribute to our forum. Welcome!

He's contributed before actually. His post count reads 1 (at the moment) because his other 2 posts were in a thread in the "Off-Topic Discussion" section, and posts there aren't currently counted in a user's post count.

I want to make a joke in the "Chuck/Frank Morris" genre. Something along the lines of "Hebert K. cannot post off topic, anything he posts is, by definition, a topic". ;-)

This statement was interesting to me because the super flip is the example of a proven 20 HTM case, so I'm going to guess this 26 QTM case is also solvable in 20 HTM?

Superflip is only one of at least 1,445,274 proven 20f* positions.

Edit: OK, I think that superflip may have a direct mathematical proof of being 20f* while other 20f* positions have probably only been "proven" so by use of computer analysis.

You happen to be correct that the 26q* position is also one of the known 20f* positions. From Reid's web site, it can be created by:

U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B' (26q*, 21f)
F U2 R L D F2 U R2 D F2 D F' B' U2 L F2 R2 B2 U' D (20f*, 28q)

See: http://www.math.ucf.edu/~reid/Rubik/x_symmetric.html

Very cool, I'vn never come across his site before. Thank you.

 

[Stefan]

OK, I think that superflip may have a direct mathematical proof of being 20f* while other 20f* positions have probably only been "proven" so by use of computer analysis.

Never heard of that. Would like to know about it if it's true. Most in that direction that I know is Reid's original proof exploiting symmetries to reduce the computer analysis:
http://www.math.rwth-aachen.de/~Mar...l_reid__superflip_requires_20_face_turns.html

 

[AvGalen]

... Superflip is only one of at least 1,445,274 proven 20f* positions. ...

Please tell me that someone tried all 18 moves on all those proven 20f* positions.
And has any of that 18*1,445,275 positions given another 20f* position?

 

[brunson]

I'll look for it later when I have more time, but I read on the cube lovers archive that the proof involved the high symmetry of the position. I'll be honest, I never read the proof, only about it.

 

[cuBerBruce]

OK, I think that superflip may have a direct mathematical proof of being 20f* while other 20f* positions have probably only been "proven" so by use of computer analysis.

Never heard of that. Would like to know about it if it's true. Most in that direction that I know is Reid's original proof exploiting symmetries to reduce the computer analysis:
http://www.math.rwth-aachen.de/~Mar...l_reid__superflip_requires_20_face_turns.html

OK, I see that while the optimality of superflip maneuvers was proven before the Korf and Reid optimal solvers were available, they still relied upon computer searches for both FTM and QTM. So I'm not aware of any more direct mathematical proof. The QTM proof involved generating all positions to depth 11q to show no 22q maneuver exists.

... Superflip is only one of at least 1,445,274 proven 20f* positions. ...

Please tell me that someone tried all 18 moves on all those proven 20f* positions.
And has any of that 18*1,445,275 positions given another 20f* position?

The figure 1,445,275 comes from a post by Rokicki in a thread started by brunson: http://cubezzz.homelinux.org/drupal/?q=node/view/125

Note that this number is not symmetry-reduced, so the number of positions that you would really have to check is much less 1,445,275*18. Many of the known positions are symmetric (all symmetric 20f* positions are known), and you generally don't need to check all 18 neighbors for symmetric positions.

I have wondered about this too. I suspect this has not been done for many of the positions.

I suspect that some of the known 20f* positions are neigbhbors of each other, but I don't recall offhand of any such known cases.

 

[cuBerBruce]

Tom has now reduced the best upper bound by one more move to a value of 31q. See:

http://cubezzz.homelinux.org/drupal/?q=node/view/134

 

[cuBerBruce]

Tom has now reduced the best upper bound by one more move to a value of 30q. See:

http://cubezzz.homelinux.org/drupal/?q=node/view/138

 

[AvGalen]

believe, based on this, that it is likely
that on other distance-26 positions exist

I am assuming that he meant to say NO other distance-26 positions exist.
But it might also have been ONE other....

 

[whauk]

my opinion:
a cube has 4.33*10^19 permutations.
you can make different 12 moves (quarter turn metric)
every further move can have only 11 possibilities because you dont want to undo sth. after 19 moves you get 6.67*10^19 possibilities which is already more than all permutations. of course some cases are not covered(e.g. R L R' L'...) but it should be approximately gods algorithm