I'm late to notice this, but recently a team proved that a Rubik's Cube can always be solved in 20 moves or less, regardless of its initial configuration. It had already been proven, back in 1995, that at least one initial configuration requires 20 moves to solve. Thus, all positions can be solved in 20 moves, and some positions require the full 20.
What is particularly interesting is that the these researchers found the 20-move bound by having a computer solve all of the 4E19 initial positions exhaustively. The best proof that didn't do an exhaustive search only proved an upper bound of 22 moves.
I wonder if a human-digestible proof will be found for the 20-move upper bound, or if we'll be left with computers generating the stronger proof? At any rate, this is yet one more problem where a mathematical result depends crucially on some very heavy computation.
Subscribe to:
Post Comments (Atom)
2 comments:
You might want to take a look at Richard Korf's Ph.D. thesis (1984?) under Alan Newell. He got his Doctorate by building a Rubik's Cube solver. The difficulty in this task is that the solver requires *non-serializable* subgoals. I am not sure how a clever proof would do this, but they would probably have to prove the minimal subgoals.
I've also recently stumbled across a Google Tech Talk from 2008 you may have not seen (I didn't see it until tonight): http://www.youtube.com/watch?v=WQw7c-PliB4&feature=related
They used 7 terabytes of disk space to prove that Rubik's Cube can be solved in a minimum of 26 steps. Obviously this newer minimum supersedes this result.
Post a Comment