The first step was to compute the list of all sequences of length at most 15. I added to this the list of all sequences of length 16 and height at most 5. This part of the work required much processing power, above all memory (up to 500 Mb). I didn't do it in one time, but I think the total computing time was about 10 hours. The biggest part of the memory used was for a hash table that contained all positions of the pieces of the 2 first layers, that were at a distance at most 6 to the origin. There were approximately 6 million elements in this hash table. Then the algorithm used was based on IDA*.
We now have millions of sequences. The second part is to select interesting sequences. I associate to each sequence a few integers (the lower, the better) : the length of the sequence, its length in slice metric, an integer that depends on the set of faces used, and the height of the sequence. A sequence is discarded if another sequence exists whose associated integers are all smaller. To reduce the number of sequences obtained, I also discarded a sequence if its length exceeds by 3 or more that of the shortest.
The integer associated to the set of faces used is defined as follows :
UR,RB,DR->0 URL,URD,DRL,RBL->1 URB,DRB->2 UDRL,UDRB,URBL,DRBL,RBLF->3 URBLF,DRBLF,UDRBL,UDRBLF->4The "slice sequences", generally denoted by Slices RL, receive the integer 1. If a sequence can be decomposed, the integer associated to the sequence is the maximum of the integers associated to the set of faces of the shorter sequences.
All the programs for this work were written in Caml.