7 ms·

If I'm not mistaken, this algorithm doesn't result in an optimal solution. You can see that in the example in the end, a random cube resulted in a 20 move solu

If I'm not mistaken, this algorithm doesn't result in an optimal solution. You can see that in the example in the end, a random cube resulted in a 20 move solution, which is the upper bound for any solution [0]. There are not many cube configurations that require such a long solution and the chance that we hit one randomly (and solved it that quickly) is incredibly small. In order to make this algorithm optimal, you'd need to do iterative deepening, trying to find solutions of length 1, 2, etc. up until 20. [0] https://www.cube20.org/ https://www.cube20.org/

seeknotfind 3y ago
Good point. I think also it would find the optimal (in the worst case time) if it continued to search for shorter solutions over the entire space once it found one. If it happened to find a solution of length 14, for instance, it could stop considering those of 15 or more, so you would still avoid the 2 month waiting time (same can be done with DFS). Though come to think of it you probably mean to do this with iterative deepening by not throwing away the intermediate structure (like BFS). What I really appreciate about this article though is the solid presentation of math connected with computer science and the author throwing around multiple programming languages. They don't even see the code anymore...
- ashdnazg 3y ago
  At the moment the algorithm seems to only check for exactly 20 move solutions, so it won't find them easily. You would however find the optimal solution followed by some silly back and forth that can be identified, as long as the optimal one isn't 19 moves.
  - deleted 3y ago
    [deleted]
reikonomusha 3y ago
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/src/4-list-algorithm.lisp#L445 https://github.com/stylewarning/cl-permutation/blob/master/s...
- ashdnazg 3y ago
  I was indeed talking about the implementation and the algorithm as described in the article (prior to the recent edit updating the definition of L). That Shamir's algorithm is correct was never in question.

seeknotfind 3y ago

Good point. I think also it would find the optimal (in the worst case time) if it continued to search for shorter solutions over the entire space once it found one. If it happened to find a solution of length 14, for instance, it could stop considering those of 15 or more, so you would still avoid the 2 month waiting time (same can be done with DFS). Though come to think of it you probably mean to do this with iterative deepening by not throwing away the intermediate structure (like BFS). What I really appreciate about this article though is the solid presentation of math connected with computer science and the author throwing around multiple programming languages. They don't even see the code anymore...

ashdnazg 3y ago
At the moment the algorithm seems to only check for exactly 20 move solutions, so it won't find them easily. You would however find the optimal solution followed by some silly back and forth that can be identified, as long as the optimal one isn't 19 moves.
- deleted 3y ago
  [deleted]

reikonomusha 3y ago

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/src/4-list-algorithm.lisp#L445 https://github.com/stylewarning/cl-permutation/blob/master/s...

ashdnazg 3y ago
I was indeed talking about the implementation and the algorithm as described in the article (prior to the recent edit updating the definition of L). That Shamir's algorithm is correct was never in question.