# Interview with Herbert Kociemba

#### pjk

Staff member
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).

Location:

<img src="http://www.speedsolving.com/interviews/interview-herbertk.jpg" border="0" align="left" alt="Herbert Kociemba">Occupation:
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.

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.