|
Daniel Kunkle spent most of his time in graduate school playing with a colorful puzzle called a Rubik's Cube(魔方)．He wasn't just goofing off．With clever computer programming, Kunkle figured out that any Rubik's Cube can be solved in 26 moves or fewer．
◆Cracking the cube
Each side of a Rubik's Cube is divided into nine squares．When the puzzle is solved, all nine squares on each side are the same color as one another．Hinges(铰链)allow rows of squares to rotate．The squares of a Rubik's Cube can be arranged in about 43 quintillion(that's 43 with 18 zeros after it)possible ways．By hand, it can take a long time to find a solution．Even the world's fastest computer would need a long time to solve the problem．
To save time, Kunkle and computer scientist Gene Cooperman of Northeastern University in Boston, Mass．, looked for strategies to break the problem into smaller pieces．First, they calculated how many steps would be required to solve the puzzle using only half-turns, which send a square to the opposite side of the cube．Their study showed that only 600,000 possible configurations(结构)can be solved this way．Using a desktop computer, Kunkle discovered that all these arrangements could be solved in 13 moves or less．
◆Puzzle pieces
Next, the researchers wanted to calculate how many steps would be necessary to turn any other configuration into one of the special 600,000 pre-solved arrangements．Results showed that it could be done in 16 moves or fewer．Remember that it took a maximum of 13 steps to solve one of these special configurations．In sum, the researchers concluded, any configuration could be solved in a maximum of 29 steps．
Kunkle and Cooperman noticed, however, that only about 80 million configurations(far less than 1 percent of all possibilities)actually needed more than 26 steps to reach a solution．So, the pair focused on the few, hardest arrangements．This time, they searched through every possible way of solving each one in 26 steps and at the end they did it．The strategies that Kunkle and Cooperman used to solve the cube can be applied to other complicated problems, especially ones that require searching through lots of possibilities．Scheduling airplane flights to carry millions of people to a variety of destinations as quickly as possible is one example．
| 