New Upper Bound for Rubik's Cube Solutions
2008.03.27
Linky!, Mathematics

Posted on the arXiv: Twenty-Five Moves Suffice for the Rubik's Cube. Tomas Rokicki (Stanford trained computer scientist [I didn't know CS can be listed on the Math Genealogy Project...]; logic puzzle enthusiast; and author of dvips) showed using exhaustive computer computation (with a bit of theoretical mangling to reduce the configuration space) that there exists no configurations of the Rubik's cube that requires 26 moves or more, putting in a new upper bound for optimal solution at 25. (The previous record was 26.)

This is exciting, but still not satisfactory. While we know that there exist several configurations that require at least 20 moves to solve, there has not yet been any example constructed that requires at least 21 moves to solve. So the practical lower bound for optimal solution is 20. The gap between the lower bound and the upper bound is rather ugly. Ideally one would like a theoretical proof for a sharp upper bound of the number of moves required to solve a Rubik's cube.

While I am at it, here's a page with many cute Rubik's cube patterns and the minimal length moves required to achieve them.

Posted at 10:22:22 EDT by W comment

blogCentralFront Page
2009.11.20 00:41:20 GMT Feynman's Messenger Lectures online Just found out something rather cool: Microsoft Research, through Project Tuva, is publishing videos of Richard Feynman's Messenger Lectures. Go watch.
2009.11.18 11:05:07 GMT Alcohol consumption Different cultures certainly have different views on alcohol. For example, at Hertford College Oxford, wine is allowed if reasonably drunk and 4) A small amount of beer or lager will be allowed wher
2009.11.16 19:17:31 GMT Luc visits; Willie doesn't check e-mail Holy cow! I just realized that I spent a day at work without checking e-mail! Okay, to be honest, today I was hosting Luc Nguyen, who we invited to speak on his work about the regularity near the sing
2009.11.15 18:19:32 GMT Chicken soup Chicken soup is not just good for the soul. It has been scientifically proven to mitigate inflammation. Maybe mommy's chicken soup was the reason that the same bug that took Pin out of commission for
2009.11.10 17:58:53 GMT Sayonara, e-nibbles; hullo, Gee-Mi-Ni It's final: e-nibbles is no more. e-nibbles was my trusty Dell D600 which I purchased summer after my Junior year in college through the Student Computer Initiative. Immediately after receiving the ob
2009.09.30 10:12:57 BST Ahhh! Cruft discovered in pre-print. Ack, I should've known better. I stayed up a bit later on Monday night than I intended to. I was asked, by Claude, last week, about whether certain cases (in particular the Born-Infeld model) not cove
2009.09.28 18:30:27 BST Spiders spiders everywhere Wow! Third post today, and here I thought I have been neglecting my blog. Anyway, it turns out that I am not the only person to have noticed the large number of spiders in Britain this autumn. Going o
2009.09.28 15:12:09 BST Causality of generalized wave-maps--paper on arXiv Oh, almost forgot. New paper on arXiv. Gary Gibbons showed via explicit computations using eigenvalues that the Skyrmion equation obeys the dominant energy condition. In my paper, I proved the dominan
2009.09.28 14:42:39 BST The evolution debate as an illustration of speciation I was reading some article or another in Wired, which happens to be about dinosaurs. And of course, the religious kooks came out of the woodwork to attack evolution on the comment board. And it occurr
2009.09.02 12:42:44 BST New beginnings: first days at Cambridge Heh. Did you, dear reader, notice the change on the date-stamp for the previous entry? It was posted in British Standard Time. Yes, I am now taking a position in the Department of Pure Mathematics and