search

cs0x7f / TPR-4x4x4-Solver

4x4x4 Solver = Three-Phase-Reduction Solver + 3x3x3 Solver
24 stars 5 forks source link

optimal solver "chokes" on very short scrambles #9

Open gregorbg opened 4 years ago

gregorbg commented 4 years ago

When presented with scrambles of length 4, the Search#solution method sometimes comes up with unnecessarily long results:

Lw2 F2 R' 3Fw solved as F2 B' Uw2 U2 F2 D F2 U2 Fw B L2 3Fw' solved as D2 Fw' B R2 B R2 B2 D2 Dw2 3Bw2 U solved as F2 Uw2 U2 F2 U' F2

I would expect the code to be able to find the "reverse solutions" of length 4. This is currently keeping us from using your optimal solver in TNoodle because we use scrambles of length 4 in our CI sanity checks.

Is there a common pattern to these scrambles that would allow you to fix such corner cases? I can provide you with more samples if you'd like. The code I'm using is the most recent as of writing this issue.

cs0x7f commented 4 years ago

The algorithm is not designed for finding the optimal solution. More specifically, it uses many tricks to improve solving efficiency for random state. And due to these tricks, the optimal solution might not be found by the solver. Such behaviours also occur in some other algorithms/software. For example, when you solve the state R L U2 R' L' F with two-phase algorithm in Cube Explorer, the optimal solutions will be lost as introduced in the document.