43 quintillion possible configurations, but only 27 moves required

Rubiks
PopSci'
s annual "Worst Jobs in Science" issue hits stands this week, and let us tell you, it's a lulu (whale-feces collector, anyone?). But a new study reveals two guys who just might have the best job in science: Northeastern University computer science professor Gene Coopman and grad student Dan Kunkleput put grant money to good use during a study published last week that proves any Rubik’s cube configuration can be solved in 26 moves, beating the previously held record of 27 moves set in 1997. They were working on a $200,000 endowment from the National Science Foundation to develop 20 terabytes of storage using new techniques in mathematical group theory—and 7 terabytes of RAM—to run single cube moves 100,000,000 times per second.

Why spend all that processing power, cash, and know-how on an obsolete children’s toy from the 1970’s, you might reasonably ask? “The Rubik's cube is a testing ground for problems of search and enumeration,” Cooperman said in a press release. “Search and enumeration is a large research area encompassing many researchers working in different disciplines – from artificial intelligence to operations. The Rubik's cube allows researchers from different disciplines to compare their methods on a single, well-known problem.”

The Rubik’s cube contains 43 quintillion possible configurations. In 1997, UCLA professor Richard Korf published a study showing that the optimal solution for the cube is 18 moves, but no one was ever able to do it in under 27. But the real questions: How many moves did it take Will Smith’s character in Pursuit of Happyness? And how do we get a grant to find easiest way to transform Optimus Prime from robot form to truck form? —Pieter VanNoordenen

Want to learn more about breakthroughs in electronics, medicine, nanotech, and more?
Subscribe to Popular Science today, for less than $1 per issue!

4 Comments

What if you start with a solved scenario and move randomly a certain number of times, repeat that process, and compare, in reverse of what moves occured, the steps it took to "solve" the cube? (I honestly don't know much about it, but maybe it could be of some help?)

wat the above person has said is very usefull
i m a 21 years old and i hav just finished my engineering from Bombay.
I m too working on Rubik'ds cube solver
its not just to develop something which can solve the cube but to do it in minimum no of step.
i have done the god's algorithm for 2by 2 cube it takes max 13 step.(not proud of it but still..)
i work on my normal pc with 1gb ram. 3by3 cube can be solve in 26 moves. and to a 3by3 cube the no. of turns that can be given are 18, which can be reduced to 12 (skipping the middle layer rotations by two adjecent layers). so the no of combinations that have to be checked becomes 12^(26) which is a huge. and that can b reduced by symmetry.(u Must be knwing all that bt still for my side)
Other method on which i m working, find the normal 50 to 60 step solution like we actually solve the cube by hand, and then divide the step in groups and try to reduced the step in each group. onec done solution is reduced by 1 to 10 steps then again repeat the same untill u get within 30 step solution. this is a TIME consuming but does not required very high config PC. I too wanted to do the same for research and career but here there not much support

The worst job in science:
FLATUS ODOR JUDGE

Odor judges are com-mon in the research labs of mouthwash companies, where the halitosis-inflicted blow great gusts of breath in their faces to test product efficacy. But Minneapolis gastroenterologist Michael Levitt recently took the job to another level—or, rather, to the other end. Levitt paid two brave souls to indulge repeatedly in the odors of other people's farts. (Levitt refuses to divulge the remuneration, but it would seem safe to characterize it thusly: Not enough.) Sixteen healthy subjects volunteered to eat pinto beans and insert small plastic collection tubes into their anuses (worst-job runners-up, to be sure). After each "episode of flatulence," Levitt syringed the gas into a discrete container, rigorously maintaining fart integrity. The odor judges then sat down with at least 100 samples, opened the caps one at a time, and inhaled robustly. As their faces writhed in agony, they rated just how noxious the smell was. The samples were also chemically analyzed, and—eureka!—Levitt determined definitively the most malodorous component of the human flatus: hydrogen sulfide.

Levitt defends his work against the reflexively dismissive by noting that doctors have never studied flatulence and that smell is a potentially critical medical symptom: "The odors of feces and intestinal gas and breath could all be important markers of gastrointestinal health," he says. Hydrogen sulfide, for instance, is an extremely toxic gas to mammals, potentially playing a role in ulcerative colitis, among other diseases. And so Levitt has dedicated his career to the study of the myriad fragrances produced by the human gut and imprudently ignored by the medical establishment.

Kimbl, www.jobinterviewquestionsandanswers.net/7/

This year, gold imprint, bracelets, necklaces and jewelry sets the hands of those who became the favorite of everyone in a very good health ...


138 years of Popular Science at your fingertips.

Innovation Challenges



Popular Science+ For iPad

Each issue has been completely reimagined for your iPad. See our amazing new vision for magazines that goes far beyond the printed page



Download Our App

Stay up to date on the latest news of the future of science and technology from your iPhone or Android phone with full articles, images and offline viewing



Follow Us On Twitter

Featuring every article from the magazine and website, plus links from around the Web. Also see our PopSci DIY feed


February 2012: The Future of Fun

Science is reinventing play, from extreme sports to gamification to ridiculous roller coasters to the playgrounds of tomorrow, and this issue is chock full of fun. Also, on a less fun note: Did global warming destroy my hometown?


circ-top-header.gif
circ-cover.gif