Update: optimal solver by generating multiple solutions until one is proven optimal. Also, reversed back to IDA*, for the first phase, a depth 6 pruning table is beeing used, and for the secound phase, a depth 7 pruning table is beeing used. This means that, for example in the first phase, if said position x in within 6 moves of domino reduction, it must be in the table, and the heuristic for the IDA* brute forcer will just be whatever the table says the distance is. However, if the position is not in the table, then it is not within 6 moves of domino reduction, thus beeing at least 7 moves away, and a static heuristic of 7 is used. Similar concept applies for the secound phase. A new kind of pruning is now also used in the secound phase. Let's say we are using the optimal solver, the best solution we have found so far is 19 moves long and it took 10 moves to reach the domino reduction we are trying to solve. In this condition, there's no point on trying to find a secound phase solution any longer than 8 moves, and if we end up proving that 8 moves to not suffice we can simply give up on the domino reduction entirely as it is simply not good enough to provide a new best solution. Using this pruning, we also have the garantee that all solution that we find are the new best solution. A similar, altho less powerfull, logic can also be used in the first phase in order to know when to stop searching. Let's say we have a best solution of 18 moves. In this case, if we finish checking all phase 1 solutions and find that none of them beat this 18 move solution, we can stop the search as a whole, as we can't beat an 18 move solution when the first phase alone is already 18 moves or more. This condition terminates the search and serves as proof that the best solution found is optimal. Despite that, the code is still written on python running on a phone, and I'm yet to see one single non-trivial search finish within reasonable time. Dispite that, actually finding the optimal solution takes way less time than proving it is optimal. It may take multiple hours to finish the search proving the solution is optimal, but just several minutes to find said solution. It, seperately, also finds multiple technically not optimal but still good solutions along the way, about the same size as you may find the scrambles in cstimer to be, in just a few secounds (not counting the time to load the pruning tables to ram, since you just have to do that once if you want to solve multiple cubes). If you do not care about the intermediate solutions and only care about the final optimal solution, one other small pruning you may use is to initialize the best solution length variable to 21 rather than infinity, since it is proven by exaution that no state of the rubik's cube takes more than 20 moves to solve. Since the ammount of states of the cube that actually requires 20 moves to solve is way bellow 1%, you may want go initialize the variable at 20 rather than 21, but I don't recommend that, since doing so would finish the search before finding any solution at all in 20 move scrambles.
Here's an example of the optimal solver doing the Jb perm scramble.
Reading table #1
Reading table #2
0
999 11 U R2 B2 U B2 U' B2 D B2 D' R2
1
2
3
4
5
6
7
8
11 10 B2 L U L' B2 R D' R D R2
First it reads both tables. Nothing to comment here; takes about 1 minute. Then it explores phase 1 solutions of increasing length. Each time a number is printed out, the next phase 1 solution length starts beeing explored. First, it starts exploring 0-long phase 1 solutions and emmidiately finds an 11 move solution within <U, L2, F2, R2, B2, D> to the Jb perm. However, after several minutes it found an 8 move phase 1 solution that resulted in an overall 10 move long solution, 8 for first phase and 2 for secound phase. Notice that, altho the initial scramble already had the first phase done, it couldn't find the optimal solution the first time because the optimal solution violated the restrictions of phase 2. You may also notice that I didn't let it finish running both because I know the optimal solution is 10 moves because I am into fmc and because it would take hours to finish exploring depth 9 at this pace. Still, I'm quite excited to see how fast this will run once I get it running on a faster programming language (probabilly c, c++ or java) and on my computer.
Edit: I forgot to explain what the numbers in the lines that have the solutions mean. The first number is the length of the previous best solution, and the secound number is the length of the new solution. Notice that I am not using the 21 move pruning.
