Based on ideas developed by Herbert Kociemba, and independently used by Richard Korf, I wrote an optimal cube solver. This is supposed to be a practical implementation of "God's Algorithm" for Rubik's Cube. Although a very small fraction of positions may require months of searching, most can be solved in a day or so, and many require much less time than that.
I originally used (in 1997) a 200MHz Pentium Pro processor, configured with 128Mb of RAM, (but I've upgraded since then).
For random positions, it seems to average about 2.5 hours for a complete search through 17 face turns, 31 hours for a complete search through 18 face turns on my hardware. However, this seems to vary a lot depending upon the position. Also, I haven't tried many random positions. I haven't tried any random positions for the quarter turn metric yet. Let's face it, I'm not so interested in random positions; I'm more interested in symmetric positions and pretty patterns.
For another approach to God's Algorithm for Rubik's cube, see reference [1].
| Download optimal solver (21K gzip'd tar file) |
Enjoy the program. Please let me know about any interesting discoveries you make.
[1] A. Fiat, S. Moses, A. Shamir, I. Shimshoni and G. Tardos,
Planning and Learning in Permutation Groups,
Proceedings of the 30th A.C.M. Foundations of Computer Science
(FOCS) 1989, pp. 274-279.
[2] Herbert Kociemba's
Cube Explorer.
The ideas he developed for his searching algorithm are those
upon which I based my program.
[3] Press
release about Richard Korf's optimal cube solver.
His program also uses similar ideas as Kociemba's.
[4] Cube-lovers message where I describe my
searching algorithm.
Cube page | Home page | E-mail
Updated October 28, 2006.