There is no need to do iterative deepening as you suggest.

The move set L, or more precisely

     L := C^5 U C^4 U C^3 U C^2 U C^1 U C^0,

contains all non-redundant moves sequences of length between 0 and 5. L has 621,649 elements. See e.g. the function that produces this [1].

Solutions thus are found between 0 moves and 20 moves inclusive.

If you ask the algorithm to solve a cube with the front face turned, it will immediately output the four words:

    "", "", "", "F".

It will also return every other quadruplet of non-redundant moves that achieve the same state if you keep the solver running, for example:

    "", "F'", "F", "F" 

(Here, "non-redundant" means there are no obvious simplifications within each word.)

The algorithm is guaranteed to enumerate all non-redundant solutions of bounded length, which includes all optimal solutions, in the same worst-case running time of O(N^0.5) and memory complexity of O(N^0.25). The Common Lisp implementation does return on the first match, but that's an implementation detail, not a limitation of the algorithm.

Lastly, solutions whose length is short typically show up first, since the words "" * "" correspond to the identity permutation, the lexicographically least permutation, and hence the first permutation found in the search.

[1] https://github.com/stylewarning/cl-permutation/blob/master/s...