A computer scientist managed to prove that any Rubik's Cube can be solved within 25 moves. He basically developed a way to mathematically model the "cube space" and the simplify the otherwise 43,252,003,274,489,856,000 combinations into sets (which still number in the billions). It took over 1500 hours of processing time on a quadcore workstation to solve each of those sets within 25 moves. Next he's going to attempt to prove that every cube is possible to solve in 24 moves.
I was always interested in creating a similar mathematical model to play every possible game of the "Free Cell" version of Solitaire. I know that not every "game" of Free Cell is winnable, but I wonder what the odds are that any given game is winnable. Some envelope-back calculations convinced me that the complexity involved means that actually solving each game would be near impossible by brute force. However, I could still get meaningful data by sampling possible decks.
Okay, now to REALLY geek-out: these kinds of problems would be instantly solvable by means of a "quantum computer." Such a computer basically leverages a weird by-product of quantum physics to essentially solve a problem by imagining every possible value of every variable simultaneously. In fact, any problem that could be expressed mathematically as a result of variables interacting could be solved in this way. It's possibly the ultimate computer. There is a lot of money going towards this kind of computing, particularly as the physical limitations of transistor-based computing begins to crowd Moore's Law. (Moore's Law predicts the infinite and exponential increase in power of computers over time.) A quantum computer would also be able to do things like break a cypher nearly instantly. (Current methods of simply guessing possible codes are limited.)
Anyway, it's not science fiction--small-scale quantum computers have already been built and demonstrated. When they get bigger, they will be very good at solving probability-based problems.
Obviously, computers have been on my mind the last few days...
-t
No comments:
Post a Comment