Optimal Rubik's cube solver

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.

System requirements

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.

References and links

[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.