May 30, 2012 : Interview with Speedsolving.com member Herbert Kociemba : Best known for creating Cube Explorer, and also helped reduce God's Number to 20 (2010).
Teacher of Mathematics and Physics (Gymnasium)
What made you become interested in solving puzzles?
The Rubik's cube and nothing else. When I first came into contact with Rubik's cube in 1980, the first challenge was of course to find a way to solve an arbitrary cube. But I soon got interested in the question if there is a way to solve it with as few moves as possible.
What motivated you to develop Cube Explorer, and how long did it take?
When I bought my first computer in 1982 - an Apple II - I already thought about some cube solving program. But with 64 kB of RAM and a 1 MHz CPU, it was absolutely impossible to get any interesting results. So I did not think about it anymore until I bought an Atari ST with 1 MByte of RAM in 1991. I hoped that with this hardware there was a way to write some useful cube program.
It took several months until I found an approach which seemed promising. I could not have foreseen that the result in the end was so much better than anything else that was out there before. The program had no graphical interface yet, but when, for example, a 15 move solution for the cube in the cube pattern appeared I was really excited.
The first version of Cube Explorer I released to public was version 1.5 in 1997. It had a graphical interface and was written in Borland C++. I completely rewrote the program in 2001 using Borland Delphi and the current version still is based on this version.
Can you tell us a bit about the background of Kociemba's Algorithm and how/why you developed it?
After more than twenty years I do not know the details any more but I think Thistlethwaite's 52-move algorithm was the starting point. Was it possible to write a program which uses only the subgroup generated by [U,D,R2,F2,L2,B2] as an intermediate step and uses only moves from this subgroup to finally solve the cube?
I tried different things but the program did not work until I developed the following methods:
1. Representing a cube state with a few numbers which allowed to implement face turns with a few table lookups. From today's point of view I reinvented the numbering of permutations and combinations.
2. Using these numbers to build a pruning table to prune the search tree. From today's point of view I constructed a minimal perfect hash function to generate a pattern database for an IDA* search.
But it was the time before the Internet was available for everyone so I knew nothing about these concepts. So the most important background of Kociemba's Algorithm is presumably that I developed it without any background.
I developed Cube Explorer mainly not to find short solutions for arbitrary cubes but to find nice cube patterns and short generators for them. Nice cube patterns usually have some symmetry and I always was fascinated by the concept of symmetry, for example in Escher’s tessellations of the plane.
What are your other hobbies?
I must admit that, objectively speaking, I spend too much of my free time doing computer related stuff. I am quite interested in playing classical guitar and piano but I neglect these hobbies unfortunately. Other hobbies are riding my bicycle and reading.
What is/are your pet peeve(s)?
I myself do not use a mobile phone and sometimes I feel disturbed by people using it in the train or a restaurant for example, telling boring stories.
What will the future of cubing be like and how would you like cubing to progress?
The speedcubing community will be a reliable variable in the future too. But it will become more and more difficult to break records which will make this issue less exciting, so the public interest (newspaper, TV etc.) will surely decrease.
Concerning the puzzle theory I do not expect breaking news in the next decades, for example, with God's number for the 4x4x4 or higher cubes. The complexity of these puzzles is much higher and the diameter problem for permutation groups is NP-hard in general.
So far, what has been your most enjoyable cubing experience?
Surely the first time I was able to solve my cube in 1981, without the aid of any other methods. It took me several weeks until all faces had the same color again. And about ten years later when I realized that my ideas to solve the cube really worked.