Rubik's Cube - solved in 26, or 17.7 moves?

Alex Zaharov-Reutt
Monday, 04 June 2007 23:13

Opinion and Analysis

Although Northeaster University Computer Science Professor Gene Cooperman and grad student Dan Kunkle say they’ve made a breakthrough and can solve the Cube in 26 moves, free online software claims to do it in usually 17.7 moves.

We’re no mathematicians and were never able to solve the Rubik’s Cube (but did have fun solving other Rubik’s puzzles), we’re not sure what to make of the claims and counterclaims that Northeastern University’s 26 move solution to the Rubik’s Cube is a world beater.

According to online reports, it used to take 65 moves to solve the Rubik’s Cube, but over the years the number has gotten lower and lower, with 27 the supposed previous record and now Northeastern University’s claim of 26 moves. That’s pretty impressive, as the Rubik’s Cube as 43 quintillion states – that’s 43 with a heck of a lot of zeros behind it!

Cooperman and Kunkle say their 26 move solution is a new record, with Cooperman saying that: “The Rubik's cube is a testing ground for problems of search and enumeration. 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 dynamic duo say that they used “7 terabytes of distributed disk as an extension to RAM, in order to hold some large tables and developed a new, “faster faster” way of computing moves, and even whole groups of moves, by using mathematical group theory”.

They then explain that they “put all of the configurations of a Rubik's cube in a family of sets of configurations (called a family of cosets in mathematical group theory).  They then looked at the result of applying a single move to all of the configurations of a coset at once.  They simulated this on a computer at a rate of 100,000,000 times per second, using a new technique in mathematical group theory”.

Some claim that Cooperman and Kunkle have used a brute force method, implying that somehow it doesn't count, but it is still quite impressive. But their statement says that U.C.L.A. computer science Professor Richard Korf said in May 1997 that he believed the Cube could be solved in around 18 moves, and no more than 20, but was never able to prove it.

Kunkle said that: “Korf had written a program that spends a long time to find optimal solutions for single states of the Rubik's cube. Our program first does a large pre-computation and then it very quickly - in about a second - finds a solution in 26 moves or less for any state of Rubik's cube”.

But a web page called “The Performance of the Two-Phase-Algorithm" claims to be able to solve the cube in around 17.7 moves with freely downloadable software, which would seem to back up Korf’s claims. We don’t have a Cube handy or we’d test it, but if it’s true, your desktop computer can do what Cooperman and Kunkle have claimed as a world record.

Either way, it’s great to see Rubik’s Cube back in the news again, as ever since its release it’s been one of the most original puzzles of all time, invented in the late 1970s by the Hungarian Erno Rubik who certainly is the puzzler of the 20th century.