Rubik's Cube

"We have known for fifteen years that there are positions that require 20 moves; we have just proved that there are none that require more. Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions."

James Nourse (who worked on the Dendral project at Stanford) wrote the best-selling The Simple Solution to Rubik's Cube. Compare his solutions to others.

 

Challenges for AI Research

  • The Rubik's Cube is an important test domain for heuristic search. For more on heuristic search, see the 15 Puzzle.
  • The Rubik's Cube has 1019 possible states, making it impossible to store in memory. 
  • There are two common ways of defining a move on a Rubik's Cube. The first defines a move as a quarter turn (90') of any face. The second defines a move as a rotation of a face, whether it is 90', 180' or 270'. We will use this second definition of a move.
  • Until recently, it was unknown what the maximum number of moves required to solve a random Rubik's Cube state could be. Solving the cube, that is, determining the minimum number of moves required to get from any starting state to the goal state, required vast amounts of computational resources and was only finally solved in 2010, after almost 30 years of AI research on the topic.

 Research History

  • The Rubik's Cube was invented in the late 1970s, and became a popular toy in the 1980s. By 1982, it was already a domain of interest for artificial intelligence researchers.
  • In 1997, Richard Korf showed that the worst case number of moves for solving a randomly chosen Rubik's Cube configuration was at least 20. 
  • In 2010, it was shown that any configuration of the Rubik's Cube can be solved in no more than 20 moves. This work required the use of 35 CPU years of computation. 

Contents

Vertical Tabs

Vertical Tabs