# Online optimal Rubik's Cube scrambler

#### Voltara

##### Member
My online scrambler at https://voltara.org/cube/ just got its first major update in nearly ten years. It now produces optimal move sequences, i.e. the minimum number of moves necessary to reach a randomly selected position (17 or 18 moves, ~94% of the time.)

Previously, it used a C++ implementation of Kociemba's algorithm that I wrote back in 2003. The new version uses multiple solvers that work in tandem to find optimal solutions to randomly generated positions. These are written in C++ and CUDA, and use Two-Phase and IDA* to prove upper and lower bounds respectively for a meet-in-the-middle approach.

The solvers are a still work in progress and haven't been tuned yet (I have been favoring correctness over raw speed), but they are currently finding optimal solutions at an average rate of about 2.7/second on my Mini-ITX desktop. This is within the range of what I should expect from this class of hardware, based on results reported previously by Tomas Rokicki.

#### ch_ts

##### Member
Hi, what did you use for pattern databases?

#### Voltara

##### Member
Hi, what did you use for pattern databases?
For the CPU IDA* search, I am using three pattern databases which I arrived at through experimentation. My constraint was the solver had to fit within 32GB of memory. I'm sure these can be improved upon; I stopped experimenting and moved on to other areas of the code when I felt the throughput was "good enough". I would be interested to hear about PDBs that others have had success with.

Edge Permutation (96-way symmetry); Flip: 2GB
Code:
Depth       96-way
------------------
0f              1
1f              2
2f              8
3f             48
4f            512
5f           6088
6f          75166
7f         924453
8f       11026268
9f      121508236
10f     1157264341
11f     5793688256
12f     3197433505
13f        3548931
14f             25
------------------
Total  10285475840
Edge Permutation (96-way symmetry); Corner Permutation: 19GB
Code:
Depth       96-way
------------------
0f              1
1f              2
2f              8
3f             48
4f            517
5f           6349
6f          81319
7f        1061716
8f       13907673
9f      181486649
10f     2311149704
11f    24598779873
12f    71384683232
13f     2756495662
14f             47
------------------
Total 101247652800
UDSliceSorted + 8-Edge Flip (16-way symmetry, tested on 3 axes); Twist + 4-Corner Combination: 5.5GB
Code:
Depth       16-way
------------------
0f              1
1f              2
2f             18
3f            175
4f           1804
5f          21146
6f         265033
7f        3360283
8f       42274687
9f      511135158
10f     5059755130
11f    19065087858
12f     4567238714
13f         235391
------------------
Total  29249375400