Researchers prove Rubics Cube solvable in 20 moves or less

August 13th, 2010

Using a combination of mathematical tricks, good programming and 35 CPU-years on Google’s servers, a group of researchers have proved that every position of Rubik’s Cube can be solved in 20 moves or less. The group consists of Kent State mathematician Morley Davidson, Google engineer John Dethridge, math teacher Herbert Kociemba, and programmer Tomas Rokicki.

This is an amazing result and a testament to more than 30 years of work on the problem. The Cube was invented in 1974 and almost immediately the subject for programs to solve it. In 1981, Morwen Thistlethwaite proved that any configuration could be solved in no more than 52 moves. Periodically, tighter upper bounds for the maximum solution length were found. This result ends the quest — there are some configurations (about 300M) that require 20 moves to solve and there are none that require more than 20 moves.

In their own words, here’s how the group solved all 43,252,003,274,489,856,000 Cube positions:

  • We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
  • We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
  • We did not find optimal solutions to each position, but instead only solutions of length 20 or less.
  • We wrote a program that solved a single set in about 20 seconds.
  • We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.

This reminds me of the first program I wrote for my own enjoyment, which used brute force to find all solutions to Piet Hein’s Soma Cube. In 1969 I had a summer job as the night operator for an IBM 360 and I would turn off the clock to run my program so that the management wouldn’t know how much computer time I was consuming.

See this BBC story more more information on this amazing result.

Swoogle has five faces

August 13th, 2010

Seen on the Web: “Swoogle is an alien from outer space send out to spy on the modnation circuit. He got five faces so he can watch them from all angles without turning his head. However only his front shows many emotions. His right face is always angry, his left face is always in awe for some reason.”

Semantic Web seen as a distruptive technology

August 1st, 2010

Washington Technology, which describes itself as “the online authority for government contractors and partners”), has an article by Carlos A. Soto on 5 technologies that will change the market. They are:

  1. Mobile
  2. Search and the Semantic Web
  3. Search and the Semantic Web
  4. Virtualization and cloud computing
  5. Virtualization and cloud computing

These are reasonable choices, thought I’ve have not done the double counting and added “machine learning applied to the massive amounts of Web data now available” and “social computing”.

But it’s gratifying to see the Semantic Web in the list. Here’s some of what he he has to say about search and the Semantic Web.

The relationship between search technology and the Semantic Web is a perfect illustration of how a small sustaining technology, such as a basic search feature on an operating system, will eventually be eaten up by a larger disruptive technology, such as the Semantic Web. The Semantic Web has the potential of acting like a red giant star by expanding at exponential rates, swallowing whole planets of existing technology in the process.

The technology started as a simple group of secure, trusted, linked data stores. Now Semantic Web technologies enable people to create data stores on the Web and then build vocabularies or write rules for handling the data. Because all the data by definition is trusted, security is often less of a problem.

The task of turning the World Wide Web into a giant dynamic database is causing a shift among traditional search engines because products such as Apture, by Apture Inc. of San Francisco, Calif., let content publishers include pop-up definitions, images or data whenever a user scrolls over a word on a Web site. The ability to categorize content in this manner could have significant implications not only for Web searches but also for corporate intranets and your desktop PC.

These types of products will continue to expand, initially in the publishing industry and then to most industries on the Web in the next two to three years.

For example, human resources sites could use them to pop up a picture and a résumé blip when a recruiter drags a mouse over an applicant’s name. Medical and financial sites such as the National Institutes of Health could use it to break down jargon and help with site exploration.

Government sites around the world, such as Zaragoza, Spain, and medical facilities, such as the Cleveland Medical Clinic, are using the vocabulary features of the Semantic Web to create search engines that reach across complex jargon and tech silos to offer a high degree of automation, full integration with external systems and various terminologies, in addition to the ability to accurately answer users’ queries.

(h/t @FrankVanHarmele)