Talk:Optimal solutions for the Rubik's Cube

I don't think the cube on the picture is correct. It is not an original Rubik's due to the center pieces and even then it's not solvable since the green/white corner must have orange as third colour and faces in the wrong direction after rotating. Luigi173 —Preceding undated comment added 23:21, 23 September 2016 (UTC)

http://cubezzz.homelinux.org/drupal/?q=node/view/117 Credibility? Update needed or not?Ithy (talk) 03:43, 10 May 2008 (UTC)

I changed the link from mathematical constructivism to constructive proof because, although IANAM, I feel the notion of constructive vs. non-constructive proofs does not depend on the philosophy of constructivism, and the latter is not really relevant to the topic at hand. Unfortunately I don't think I'm up to actually writing the article on constructive proofs... :(

There needs to be a 2x2 part — Preceding unsigned comment added by 73.170.251.28 (talk) 14:11, 19 June 2022 (UTC)

Oh goody, Gandalf61 just did :)

24 quarter turns changed to 26 quarter turns by anonymous editor, can anyone cofirm? Κσυπ Cyp   22:51, 20 Jan 2004 (UTC)

I can confirm it. On the following page http://www.math.ucf.edu/~reid/Rubik/x_symmetric.html there is a positions that needs 26 quarter turns. Here is the solution

U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B'

User:Sander123 3 febuary 2004.

I am not convinced this is correct. Reid's x_symmetric.html page is stating that his best algorithm (the optimal cube solver) needs 26 quarter turns to reach that position. This is not a proof that no algorithm can reach that position in fewer turns. For the superflip position the situation is different: as stated, Jerry Bryan has proved by brute-force search through depth 11 (exploiting the symmetry of superflip) that 24 is a real lower bound (http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Jerry_Bryan__Qturn_Lengths_of_M-Symmetric_Positions.html). Without a similar proof for the 26 quarter turn position (and if so, please give a reference), it is not a lower bound. Jim Mahoney 18:05, 8 June 2007 (UTC)

After looking around further and re-reading the primary sources, I'm even more unconvinced. http://www.fact-index.com/o/op/optimal_solutions_for_rubik_s_cube.html states that the bounds are 20 for the face metric, and 24 for the quarter turn metric, both based on the superflip position. I'm therefore going to change the front page lower bound back to 24 for the quarter turn metric. Jim Mahoney 18:45, 8 June 2007 (UTC)

On this page [1] he claims that the solver he used is optimal, ie it may never give a solution, but if it will it is an optimal one. Sander123 10:48, 14 June 2007 (UTC)

Update, I have a reference for the lower bound of 26q. See [2] (dated august 2 1998, subject: superflip composed with four spot)

Hmm. In this article http://www.americanscientist.org/template/BookReviewTypeDetail/assetid/25829;jsessionid=baa4XNTR6LdtGz it is claimed that there are also positions that need 21 face turns. I haven't found one yet though. User:Sander123 3 febuary 2004.

A position with 21 face turns has not been discovered up to now. User:Herbert Kociemba 9 febuary 2004.

The mathematics concerning Thistlethwaites and my algorithm was not correct. The subgroups there definitely are not normal and so the coset spaces are no groups! I changed it. User:Herbert Kociemba

The article Rubik's Cube says that "all cubes can be solved in 23 moves or fewer." Is this correct? Does it need to updated changed? Is this perhaps the correct number? (The Swami 05:54, 11 November 2005 (UTC))

According to the 6 Step Solution Guide that is included in all recent Rubik's Cubes sold today, all cubes can be solved in 20 twists or less. "RUBIK Fact: Most cubes can be solved in only 17 moves with the aid of a computer, and theoretically there is no cube that requires more than 20 twists to solve. Some people can solve the cube in under 45 moves from any scrambled positon; and a few can even solve the cube blindfolded!" This may prove to be a valuable addition to the article.User:Ring-Ding July 29, 2006.

Though 20 twist is suspected to be the actual lower bound, this has not been proven, afaik. Sander123 11:52, 31 July 2006 (UTC)

"How to solve the Rubik's Cube" Link

How to solve the Rubik's Cube is no longer a valid link. Was that article deleted, or moved, or merged? This article seems to build off of that old one, so if it was deleted, at least a little information of it should be merged into this one. If it was moved, the link should be changed too. Fieari 06:51, July 23, 2005 (UTC)

It got moved to wikibooks:How to solve the Rubik's Cube -- Spoon! 05:19, 8 August 2005 (UTC)

Dedmore?

Why does no one speak of the excellent solution by Denny Dedmore? I have learned it this way, and it is much easier as a beginner's soulution, but can be executed quite quickly. Plus, it is highly visual and easy to understand, utilizing move sequences for the posistion of cubies on the cube face.Fishdert 22:46, 25 February 2007 (UTC)Fishdert —The preceding unsigned comment was added by Fishdert (talk • contribs) 22:45, 25 February 2007 (UTC).

Because this page is about solution that are optimal. I don't know dedmore's method but very likely it can't solve a cube in worst case 27 turns. The solutions on this page are not intended to be used by humans for solving cubes in practice. Bye. Sander123 15:32, 26 February 2007 (UTC)

Scientist Solves Rubik's Cube In 26 Moves

http://www.sciencedaily.com/releases/2007/05/070531131326.htm

"It’s a toy that most kids have played with at one time or another, but the findings of Northeastern University Computer Science professor Gene Cooperman and graduate student Dan Kunkle are not child’s play. The two have proven that 26 moves suffice to solve any configuration of a Rubik's cube – a new record. Historically the best that had been proved was 27 moves."

Thank you 129.71.94.254 for deleting that awful overview paragraph. --72.192.8.238 (talk) 20:50, 23 March 2008 (UTC)

Lower Bounds section

Isn't this

"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. [2]"

in the Lower Bounds section now incorrect, because of http://arxivblog.com/?p=332, which shows that 25 moves is the (currently known) lower bound? Mattack (talk) 00:37, 28 March 2008 (UTC)

There are two ways to count the number of moves: counting each quarter turn as a move, and one counting each face turn as a move. Using the face turn metric one gets lower numbers than using the quarter turn metric. Reid's position is the currently worsed known position in terms of the number of quarter turns needed. Most of the work on lower bounds focusses on the face turn metric. This difference is not always explicit in the article. Sander123 (talk) 05:20, 6 June 2008 (UTC)

What is "optimal"?

It's perhaps obvious to some, but the article should make clear what an optimal algorithm is. I'd guess: an algorithm that is guaranteed to take the minimal number of steps to solve a cube from any starting position. pgr94 (talk) 12:33, 5 August 2010 (UTC)

Possible New Solution

I don't feel qualified to edit this page, so instead am simply including this link: http://www.cube20.org/ I think some mention of this "claim" should be included in this article, but unfortunately, there don't seem to be any citations on that page. They claim to have shown, using multiple computers at Google labs, that every unique position on a cube can be solved in 20 moves or less, using the face metric. ETomeny (talk) 14:38, 9 August 2010 (UTC) ETomeny, are you saying that they haven't been published so they shouldn't be mentioned? 24.163.17.26 (talk) 21:36, 10 August 2010 (UTC) Well, I guess the big question is, is it true? Does the information at cube20 provide sufficient detail to at least convince that it might be true? The names they mention are at least people known from the field, but really anybody can put up a web site. Sander123 (talk) 06:52, 11 August 2010 (UTC) The issue that Sander123 raised is what I was discussing. Anyone could have put up that website. There are no citations whatsoever. However, I don't see why this article can't mention "A website appeared in July, 2010 claiming that several notable people had managed, using computer time at Google, to prove that any configuration of a Rubik's Cube can be solved in 20 moves or less. The website, however, provided no citations." Is this type of thing allowed in a Wikipedia article? ETomeny (talk) 18:44, 11 August 2010 (UTC)

Sure, its relevant, and people can make up their own minds whether they want to believe the claim or not. Sander123 (talk) 13:07, 12 August 2010 (UTC)

Quarter Turn vs. Face Metric

I think the article needs a more detailed discussion, or perhaps needs to be split into two sections, to highlight the differences between the quarter turn metric and face metric. The upper and lower bounds will be different depending upon which metric you use, no? Apparently (see my previous discussion topic) it has been shown that the upper and lower bounds are 20 using the face metric (i.e. this discussion has been "solved" for the face metric, see http://www.cube20.org/) but I'm not familiar enough with the cube to know whether this means it has been solved for the quarter turn metric as well. It seems to me that there would be a different "God's Number" for that metric. ETomeny (talk) 14:41, 9 August 2010 (UTC)

I agree. I would like to see the move count for each solution (upper bound vs. lower bound) in the same metric so that they can be compared. Perhaps everything could be listed in face turn metric with quarter turn metric in parentheses. --68.97.85.136 (talk) 17:44, 2 October 2010 (UTC)

New low number of moves for solving Rubik's cube?

The following web page:

http://www.digitaltrends.com/computing/how-many-moves-to-solve-rubiks-cube/

says that a new low has been found, but I don't trust the page - it looks like a blog pretending to be news.

I am listing it here in case someone can find a reliable source to cite. Guy Macon (talk) 11:30, 18 June 2011 (UTC)

It looks like you're right about that being nothing but SEOslop.

However, the result they were (poorly) reporting on, Kunkle & Cooperman 2007, was legitimate, published by the ACM (https://doi.org/10.1145%2F1277548.1277581) and has since been properly integrated into the page. So this subthread can probably be archived. 50.4.94.103 (talk) 01:19, 12 May 2023 (UTC)

Title is not quite right

Is the title "Optimal solutions for Rubik's Cube" correct? The article is about finding God's number, not optimal solutions to random states (although there is section "Korf's algorithm" about it). Kociemba's algorithm is not optimal, and Thistlethwaite's algorithm was used only to prove certain upper bound.

Maybe something like "Mathematics of the Rubik's Cube" would be better? Stuff like [3] could be also included here in that case. Stannic (talk) 02:19, 28 July 2013 (UTC)

Unclear phrasing in Korf's algorithm

“Although this algorithm will always find optimal solutions, there is no worst case analysis. It is not known how many moves this algorithm might need.”

This is not at all clear. God's number is 20, so a trivial “worst case analysis” reveals that of course this algorithm has to find sequences that are no longer than 20, no?

If not “moves”, what does that sentence actually refer to? Algorithmic iterations?

50.4.94.103 (talk) 01:10, 12 May 2023 (UTC)