God's algorithm for megaminx <U,R>

[Ben Whitmore]

Today I finished running a disk-based breadth first search through megaminx <U,R>. God's number is 26 (as expected).

Depth              New            Total
    0                1                1
    1                8                9
    2               32               41
    3              128              169
    4              512              681
    5             2048             2729
    6             8176            10905
    7            32400            43305
    8           128608           171913
    9           509927           681840
   10          2021092          2702932
   11          8003554         10706486
   12         31678834         42385320
   13        125307530        167692850
   14        495157495        662850345
   15       1953478687       2616329032
   16       7682157029      10298486061
   17      29984818955      40283305016
   18     114831820323     155115125339
   19     417957132495     573072257834
   20    1325871801018    1898944058852
   21    2934550836931    4833494895783
   22    2736869164561    7570364060344
   23     427540149248    7997904209592
   24       1770867597    7999675077189
   25             7595    7999675084784
   26               16    7999675084800

The 16 positions that take 26 moves are the ones with 7 corners twisted one way, and 1 corner twisted the other way.

https://benwh1.github.io/web/twisty_puzzles/megaminx/megaminx_RU/index.html

 

[Ben Whitmore]

QTM:

Depth              New            Total
    0                1                1
    1                4                5
    2               12               17
    3               32               49
    4               88              137
    5              240              377
    6              656             1033
    7             1792             2825
    8             4896             7721
    9            13376            21097
   10            36504            57601
   11            99528           157129
   12           271359           428488
   13           739584          1168072
   14          2015884          3183956
   15          5493494          8677450
   16         14965234         23642684
   17         40757056         64399740
   18        110960833        175360573
   19        301946732        477307305
   20        821049717       1298357022
   21       2230003682       3528360704
   22       6044495440       9572856144
   23      16321629020      25894485164
   24      43746575372      69641060536
   25     115506765437     185147825973
   26     295645071578     480792897551
   27     709214579066    1190007476617
   28    1487087816072    2677095292689
   29    2368788759019    5045884051708
   30    2189306113522    7235190165230
   31     726260727313    7961450892543
   32      38159404443    7999610296986
   33         64787090    7999675084076
   34              724    7999675084800

34 move positions: https://benwh1.github.io/web/twisty_puzzles/megaminx/megaminx_RU/depth-34-generators.txt
A nice symmetric one: R2' U' R U2' R2' U R U' R' U R' U R2 U2' R2 U' R U R' U' R U' R U2' R' U2'

 

[abunickabhi]

Interesting computation, is this a substep to get an upper limit for god's number for the whole megaminx puzzle?

 

[UMichSpeedCubist]

Depth              New            Total
    0                1                1
    1                8                9
    2               32               41
    3              128              169
    4              512              681
    5             2048             2729
    6             8176            10905
    7            32400            43305
    8           128608           171913
    9           509927           681840
   10          2021092          2702932
   11          8003554         10706486
   12         31678834         42385320
   13        125307530        167692850
   14        495157495        662850345
   15       1953478687       2616329032
   16       7682157029      10298486061
   17      29984818955      40283305016
   18     114831820323     155115125339
   19     417957132495     573072257834
   20    1325871801018    1898944058852
   21    2934550836931    4833494895783
   22    2736869164561    7570364060344
   23     427540149248    7997904209592
   24       1770867597    7999675077189
   25             7595    7999675084784
   26               16    7999675084800

I was just able to independently verify the values up to depth 14. It might spit out one more before it runs out of memory.

 

[ichcubegerne]

Interesting computation, is this a substep to get an upper limit for god's number for the whole megaminx puzzle?

Yes it was, it is now at 116 (from 119 when Ben generated it).

 

[Deleted member 36445]

the graph looks like a leaf if you mirror it, or a spades suit