Rubik's cube is not mainstream O.R., but news about it has made the news today, with the proof that every scrambled position can be solved in 20 moves or less. The announcement is here. It is good when mathematics is covered in the press.
There is a slight link with O.R., but I won't exaggerate it. In theory, you could create a dynamic programming formulation of the problem of solving a scrambled cube. The state would be the description of the cube; the decision would be which of the possible moves to make next; the single stage cost would be one; and the objective would be the minimum number of moves needed to solve the cube from its present state. Stages would be identified with the objective value. But before anyone tries this, note that the researchers looked at 55,882,296 cases (states).
And for the last two years, I have shared an office with Peter Vamos, one of Erno Rubik's cousins.
No comments:
Post a Comment