• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Loopover god's number upper bounds: 4×4, asymptotics, etc.

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 101.
I reduced the GN of 4x5->5x5 + 5x5->6x6 to 38, by applying at most 5 prefix moves to every scramble that would naively take >38 moves. There were 249347110 total scrambles, which took 4294.610 seconds to process (including making the two BFS trees). Referring to this earlier post, this means that the GN of 6x6 is at most 27 (0x0->2x2->3x3) + 21 (3x3->4x4) + 15 (4x4->4x5) + 38 (4x5->5x5->6x6)=101.
I've also rewritten my BFS tree and tree optimization programs and put them on https://github.com/coolcomputery/Loopover-Brute-Force-and-Improvement
UPDATE (2021-06-27): 6x6 GN is at most 100.
This time I reduced the GN of 4x4->4x5->5x5 to 28, by applying at most 7 prefix moves 6 prefix moves. There were 709300008 total scrambles, which in total took 3167.242 seconds 42296.808 seconds. by applying at most 6 prefix moves. Thus, 6x6 GN is at most 27 (0x0->2x2->3x3) + 21 (3x3->4x4) + 28 (4x4->4x5->5x5) + 24 (5x5->6x6)=100.
Doing 4x4->5x5 brute-force requires tracking 20!/11!=~60 billion states, which is too big for Java arrays to be use to track whether a state has been visited before or not during the BFS. It might be possible to replace Java arrays with several thousand or so I/O files, but that will take a lot of work to program and will probably result in a very slow BFS.
UPDATE (2021-06-28): 6x6 GN is at most 99.
I further reduced the GN of 4x4->4x5->5x5 to 27, by applying at most 7 prefix moves. There were 2821027911 total scrambles, which took 16478.048 seconds to process. 27 (0x0->2x2->3x3) + 21 (3x3->4x4) + 27 (4x4->4x5->5x5) + 24 (5x5->6x6)=99.
UPDATE (2021-06-29): 6x6 GN is at most 98.
This time I reduced the GN of 0x0->2x2->3x3 to at most 26. 5629775526 total scrambles took 28655.157 seconds to process. 26 (0x0->2x2->3x3) + 21 (3x3->4x4) + 27 (4x4->4x5->5x5) + 24 (5x5->6x6)=98.
Currently, trying to reduce 4x4->4x5->5x5 to 26 moves results in java.lang.OutOfMemoryError because my program is forced to try generating all prefix move sequences consisting of 9 moves.
 
Last edited:
  • Like
Reactions: Q--

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
5x5 GN is at most 49.
I reduced the GN for 0x0->2x2->3x3 (i.e. solving AB FG, then C H KLM) to at most 21 moves., by considering every scramble of the pieces ABC FGH KLM that would take >21 moves by naively applying solving the two phases, applying at most 2 prefix moves, and solving the two phases of the resulting scramble. In total, 2922776484 scrambles took 3625.230 to process.
Since the GN for 3x3->4x4->5x5 is already known to be at most 28, this reduces the 5x5 GN to at most 21+28=49.
UPDATE (2021-07-01): 5x5 GN is at most 48.
I further reduced the GN for 0x0->2x2->3x3 to at most 20 moves, this time by applying at most 3 prefix moves. 22,088,910,396 scrambles took 37362.881 seconds to process. 20+28=48.
UPDATE (2021-07-06): 5x5 GN is at most 47.
I further reduced the 0x0->2x2->3x3 GN to 19 moves, using at most 5 prefix moves. 88,669,385,160 scrambles took 438839.540 seconds to process. 19+28=47.
Below is the stdout of the program I used.
5x5
[11111, 00111, 00011],[11111, 00111, 00011]
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
[0, 1, 5, 6]
ncombos=303600
0:1
1:8
2:64
3:492
4:2974
5:14584
6:49562
7:97448
8:95449
9:39425
10:3592
11:1
#reached=303600
D=12
total time=703
-1 -1 0 1 2
-1 -1 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
[0, 3, 6, 7, 8]
ncombos=2441880
0:1
1:4
2:20
3:105
4:508
5:2386
6:10441
7:41483
8:143791
9:398056
10:738804
11:744707
12:321693
13:39351
14:530
#reached=2441880
D=15
total time=3905
threshold=19, P=1
#mvseqs=20
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
NOT REDUCED:
..FB.
..C.G
.....
K....
LM.AH
t=0; [0, 0, 1] [1, 3, 1] [0, 1, 1] [0, 1, 1] [0, 0, 1] [0, 0, 1]
t=1; [0, 4, -1] [1, 4, -1] [0, 4, -1] [1, 4, -1] [0, 2, -1] [1, 4, -1] [0, 3, -1] [0, 3, -1] [0, 2, 1] [1, 3, -1] [1, 2, 1] [1, 2, 1] [0, 2, 1] [0, 2, 1]
--------------------------------

threshold=19, P=2
#mvseqs=320
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 4194697
13591 14330036
20566 22731789
23454 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
NOT REDUCED:
LM.B.
H...G
.....
C....
K.FA.
t=0; [1, 2, 1] [0, 0, 1] [1, 3, 1] [0, 1, 1] [0, 1, 1] [0, 0, 1] [0, 0, 1]
t=1; [1, 4, 1] [0, 3, -1] [1, 4, 1] [1, 2, -1] [0, 4, -1] [0, 4, -1] [1, 3, 1] [1, 3, 1] [0, 2, 1] [1, 3, 1] [1, 2, 1] [0, 2, 1] [0, 2, 1]
--------------------------------

threshold=19, P=3
#mvseqs=4640
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 5639768
13591 15895846
20566 24364229
22136 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1843207
13591 7205813
20566 12453106
28261 17683133
36945 23931376
46782 30156822
57912 38056072
70470 49324924
84594 60226892
100427 74363891
118121 89821904
137835 107773693
159738 126368443
184009 147449049
210839 170503217
240428 196172792
272990 223179404
308753 252034290
347956 282139166
390855 315699165
437717 357259160
488829 407675011
544492 457802155
605024 510049433
670764 564532796
742065 621033191
819305 690464104
902880 761328186
993208 830751427
1090730 916032486
NOT REDUCED:
.LA.C
.....
....G
...BH
KM.F.
t=0; [1, 4, -1] [1, 3, 1] [1, 3, 1] [0, 1, 1] [0, 1, 1] [0, 0, -1] [0, 0, -1]
t=1; [0, 4, -1] [1, 3, -1] [0, 4, -1] [1, 3, -1] [0, 2, -1] [1, 4, -1] [1, 4, -1] [0, 3, -1] [1, 2, -1] [0, 3, -1] [0, 2, -1] [1, 2, -1] [0, 2, -1]
--------------------------------

threshold=19, P=4
#mvseqs=65560
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 5424021
13591 15568919
20566 23654225
22655 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1941354
13591 7494878
20566 12647504
28261 17865289
36945 24142040
46782 30224398
57912 38090731
70470 49318891
84594 59705711
100427 73761790
118121 89136460
137835 106980474
159738 125431249
184009 146489407
210839 169203960
240428 195066989
272990 222107639
308753 250888586
347956 280713560
390855 315150416
437717 355339142
488829 405879973
544492 456493697
605024 508305824
670764 561866412
742065 619044882
819305 688432964
902880 759910399
993208 830639305
1090730 914962991
1195910 999428960
1309240 1082106762
1431233 1184350896
1562434 1284532704
1703414 1395080047
1854773 1519564037
2017143 1650417732
2191190 1777322834
2377612 1928998394
2577140 2093367660
2790547 2265512253
3018641 2444796664
3262270 2630874009
3522324 2838463422
3799738 3041414772
4095490 3268200261
4410608 3482307172
4746166 3738874871
4887273 3834676248
[7, 14]: ncombos=51647440
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 3104966
13591 9367853
20566 13684325
28261 17810915
36945 23171213
46782 29232132
57912 35828302
70470 42862466
84594 49678518
88527 51647440
[8, 12]: ncombos=30705275157
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1912357
13591 5170250
20566 7225947
28261 10671055
36945 13920836
46782 17702050
57912 22259717
70470 27545084
84594 32923969
100427 37493569
118121 44962412
137835 52052458
159738 60713878
184009 69427571
210839 78450098
240428 90711901
272990 105416641
308753 122759128
347956 149210379
390855 176463040
437717 207507680
488829 234382785
544492 262959996
605024 294889554
670764 322803674
742065 356264827
819305 396531897
902880 447443902
993208 496528860
1090730 546042186
1195910 598881447
1309240 652257249
1431233 713383257
1562434 800508138
1703414 889802345
1854773 983398635
2017143 1070792909
2191190 1180782076
2377612 1312266558
2577140 1461365716
2790547 1621512833
3018641 1779084770
3262270 1935576309
3522324 2110451822
3799738 2294714116
4095490 2502033157
4410608 2699003932
4746166 2913274117
5103292 3120795334
5483165 3337783860
5887023 3563116575
6316157 3802569509
6771923 4063340640
7255737 4338409959
7769080 4653828462
8313503 5054462475
8890625 5480151826
9502140 5887074487
10149817 6302641673
10835506 6718543089
11561138 7169784935
12328729 7643289607
13140387 8136066005
13998309 8651179664
14904789 9176189774
15862223 9794520721
16873106 10315828746
17940045 10759407911
19065756 11303363927
20253072 11945179165
21504944 12637723966
22824451 13232821252
24214799 13797095541
25679329 14613481818
27221521 15497874096
28845000 16370921031
30553538 17141237279
32351067 17898582126
34241676 18835012882
36229621 19849629060
38319332 20822958627
40515419 21886249026
42822676 22929179746
45246087 24085828014
47790841 25325447366
50462328 26474145110
53266154 27852903509
56208145 28994296117
59294357 30451562168
59985716 30705275157
[8, 13]: ncombos=3756013599
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 856169
13591 2341330
20566 3613636
28261 4690163
36945 6136822
46782 7629478
57912 9310749
70470 11636631
84594 14862136
100427 21917896
118121 28250172
137835 34419737
159738 39605963
184009 46035723
210839 55476798
240428 64041823
272990 73206345
308753 81447875
347956 95284956
390855 113182072
437717 129584893
488829 151164385
544492 181827394
605024 214304958
670764 245875933
742065 278732732
819305 316183761
902880 354313389
993208 388896646
1090730 422400781
1195910 461832994
1309240 506963662
1431233 553241016
1562434 627421068
1703414 700152268
1854773 770560833
2017143 843528224
2191190 919129211
2377612 1001362130
2577140 1087621447
2790547 1179078074
3018641 1278336452
3262270 1321890632
3522324 1394185083
3799738 1484872504
4095490 1594725425
4410608 1669811318
4746166 1775333651
5103292 1915925097
5483165 2052293672
5887023 2153890077
6316157 2314791345
6771923 2488828572
7255737 2658938769
7769080 2822268513
8313503 3009174064
8890625 3189939235
9502140 3376953470
10149817 3509899095
10835506 3704282558
11063922 3756013599
[8, 14]: ncombos=50587970
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 550865
13591 2746955
20566 5144179
28261 7198491
36945 10708997
46782 14218108
57912 17427278
70470 19182903
84594 21938170
100427 25337678
118121 28959854
137835 34392727
159738 39524401
184009 45039135
210839 49287655
218219 50587970
[9, 11]: ncombos=29360073475
memoizing scramble actions: 0 ms
elapsed ms #combos
5001 2920907
13591 4529497
20566 5883486
28261 7410213
36945 10166316
46782 14052565
57912 17779900
70470 21262466
84594 23684752
100427 28193399
118121 31711406
137836 34910065
159738 39477797
184009 46647958
210839 55542795
240428 66039995
272990 76165898
308753 88163077
347956 102496350
390855 116975087
437717 131360711
488829 140878149
544492 155172494
605024 174621831
670764 185405984
742065 208488571
819305 231094822
902880 260562889
993208 288225296
1090730 312548611
1195910 339915382
1309240 373735776
1431233 415249904
1562434 454536057
1703414 496421810
1854773 557231011
2017143 617588336
2191190 684434520
2377612 760644189
2577140 826415792
2790547 886848038
3018641 959654976
3262272 1040180239
3522324 1110946990
3799738 1205672700
4095490 1305853516
4410608 1421635805
4746166 1537660804
5103292 1645648363
5483165 1765232816
5887023 1896154093
6316157 2032967878
6771923 2198486677
7255737 2392432268
7769080 2577352246
8313503 2765802429
8890625 2969252677
9502140 3222415317
10149817 3489879820
10835506 3754695584
11561138 4015837486
12328729 4288830057
13140387 4586127706
13998309 4870652538
14904789 5188110478
15862223 5497974072
16873106 5800945247
17940045 6128796701
19065756 6457148115
20253072 6839410212
21504944 7100224473
22824451 7448206657
24214799 7820206464
25679329 8274811703
27221521 8860416348
28845000 9403841408
30553538 9961912437
32351067 10557978284
34241676 11133071281
36229621 11668663030
38319332 12203420956
40515419 12850042951
42822675 13646203621
45246087 14389910828
NOT REDUCED:
LK..H
.....
C.AB.
...G.
...FM
t=0; [1, 3, -1] [1, 3, -1] [1, 2, -1] [0, 2, -1] [1, 2, -1] [0, 1, -1] [0, 1, -1] [0, 0, -1] [0, 0, -1]
t=1; [1, 4, -1] [1, 4, -1] [1, 3, 1] [1, 3, 1] [0, 2, 1] [0, 2, 1] [1, 4, -1] [0, 4, -1] [0, 4, -1] [1, 2, 1] [0, 2, 1]
--------------------------------

threshold=19, P=5
#mvseqs=910744
total combos to reduce=88669385160
[6, 14]: ncombos=26267860
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 2536153
13591 10320515
20566 17897045
28218 26267860
[7, 13]: ncombos=3834676248
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1779871
13591 6246350
20566 10832328
28261 15801970
36945 20456191
46782 26539946
57912 32985199
70470 43335750
84594 54465175
100427 65827778
118121 80453877
137835 96016900
159738 115502863
184009 134960171
210839 156024893
240428 180760029
272990 206208779
308753 233515312
347956 258527545
390855 285819993
437717 316034466
488829 350666361
544492 398827277
605024 449340377
670764 498920101
742065 555093742
819305 617250872
902880 687253497
993208 755181395
1090730 823411626
1195910 895524089
1309240 965552210
1431233 1012880823
1562434 1070499529
1703414 1177259472
1854773 1282498655
2017143 1393276656
2191190 1521277206
2377612 1649361465
2577140 1772598541
2790547 1893265221
3018641 2036482759
3262270 2197118229
3522324 2372020989
3799738 2547772372
4095490 2743835553
4410608 2942241855
4746166 3156410703
5103292 3366777950
5483165 3577277509
5887023 3799573830
5968126 3834676248
[7, 14]: ncombos=51647440
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1755417
13591 5993345
20566 9887075
28261 13632057
36945 17373775
46782 22033217
57912 27354414
70470 33733338
84594 37715663
100427 43790052
118121 50289402
123168 51647440
[8, 12]: ncombos=30705275157
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1584101
13591 4561573
20567 5307887
28261 6964896
36945 8543052
46782 12153903
57912 14871474
70470 18638570
84594 22806167
100427 26979084
118121 30793145
137835 36410262
159738 42344836
184009 50026156
210839 57884728
240428 65311281
272990 73710886
308753 84604711
347956 97956381
390855 112623861
437717 137260764
488829 163853736
544492 191706336
605024 219018562
670764 244423442
742065 271810919
819305 303819875
902880 329576370
993208 362857779
1090730 405574244
1195910 455322630
1309240 505702769
1431233 555016708
1562434 602360125
1703414 666138892
1854773 724005112
2017143 807691698
2191190 908383924
2377612 1007448803
2577143 1087443340
2790547 1197880638
3018641 1311844370
3262270 1460543377
3522324 1610582483
3799738 1747523767
4095490 1882185674
4410608 2025294296
4746166 2179499745
5103292 2395833456
5483165 2613219349
5887023 2819913165
6316157 3023684616
6771923 3231065584
7255737 3437339280
7769080 3713489714
8313503 3941794496
8890625 4190995195
9502140 4497042295
10149817 4934334702
10835506 5453773238
11561138 5940598962
12328729 6421482798
13140387 6933923431
13998309 7449201636
14904789 8030490077
15862223 8603229512
16873106 9199812670
17940045 9893254033
19065756 10524710077
20253072 11020200453
21504944 11791631726
22824451 12576775003
24214799 13301435320
25679329 13985758890
27221521 14956336742
28845000 15849514049
30553538 16823269568
32351067 17660517901
34241676 18766565148
36229621 19877419619
38319332 21023083723
40515419 22188887243
42822675 23316807041
45246087 24624215705
47790841 25914924101
50462328 27192606501
53266154 28396306830
56208145 29669558371
58592310 30705275157
[8, 13]: ncombos=3756013599
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 858479
13591 2356061
20566 3657816
28261 4711592
36945 6188545
46782 7721711
57912 9400055
70470 11752562
84594 15089747
100427 22268557
118121 28528839
137835 34694736
159738 39656484
184009 46535361
210839 55864191
240428 64459261
272990 73402361
308753 81955867
347956 96549601
390855 114611559
437717 130447042
488829 152873642
544492 184015556
605024 216573815
670764 248181036
742065 280566171
819305 318083046
902880 356060876
993208 390273608
1090730 424934546
1195910 464603093
1309240 508851981
1431233 556266869
1562434 631331355
1703414 704586090
1854773 774293095
2017143 847969887
2191190 923118471
2377612 1004556780
2577140 1090935625
2790547 1183549247
3018641 1279255718
3262270 1324639305
3522324 1397406814
3799738 1489109562
4095490 1597054001
4410608 1672257413
4746166 1782687594
5103292 1920786624
5483165 2058483258
5887023 2160684829
6316157 2321956001
6771923 2496656961
7255737 2668047567
7769080 2830766795
8313503 3016786031
8890625 3195806266
9502140 3383503015
10149817 3514420781
10835506 3714160936
11030022 3756013599
[8, 14]: ncombos=50587970
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 734851
13591 3063805
20566 5429276
28261 7556994
36945 11085850
46782 14555703
57912 17474012
70470 19303249
84594 22043513
100427 25385229
118121 28989568
137835 34430797
159738 38989974
184009 44648845
210839 48916189
220530 50587970
[9, 11]: ncombos=29360073475
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 2945360
13591 4715499
20566 5949282
28261 7615602
36945 10372929
46782 14303702
57912 17887755
70470 21456219
84594 23819789
100427 28716541
118121 32003190
137835 35454920
159738 40166438
184009 46893834
210839 56860964
240428 66627342
272990 77084894
308753 89521748
347956 103282639
390855 117958824
437717 131530252
488831 141070865
544492 155649220
605024 175046846
670764 186453604
742065 209324366
819305 232080569
902880 261484429
993208 289284140
1090730 313423527
1195910 340854110
1309240 375051883
1431233 416740858
1562434 455654845
1703414 498090509
1854773 560056286
2017143 620757472
2191190 688131140
2377612 762330650
2577140 828435239
2790547 890018716
3018641 961571005
3262270 1041008084
3522324 1113509877
3799738 1207595245
4095490 1307376947
4410608 1423497483
4746166 1540504869
5103293 1649481251
5483165 1768112897
5887023 1898938486
6316157 2040238575
6771923 2208330742
7255737 2399521066
7769080 2593382494
8313503 2781308037
8890625 2997031570
9502140 3270362557
10149817 3575752703
10835506 3845881204
11561138 4149412895
12328729 4467645297
13140387 4795705814
13998309 5134514691
14904789 5472053623
15862223 5805494631
16873106 6146305057
17940045 6520880708
19065756 6885890594
20253072 7280255167
21504944 7664873108
22824451 8127139915
24214799 8730599957
25679329 9321158278
27221521 9884576035
28845000 10474523649
30553538 11109402115
32351067 11730161739
34241676 12281459187
36229621 12969384036
38319332 13743697213
40515419 14417834401
42822675 14995922507
45246087 15778023751
47790841 16610218001
50462328 17439264253
53266154 18188614136
56208145 19056399493
59294357 20066111557
62531083 21068273590
65924860 21943001401
69482480 23082988776
73210999 24187281258
77117743 25308119156
81210321 26409923899
85496631 27442860647
89984875 28419561072
94683564 29335163333
94811270 29360073475
[9, 12]: ncombos=12682746525
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1401828
13591 2356078
20566 2837656
28261 4100464
36945 5892547
46782 7668978
57912 9048688
70470 10166493
84594 12295942
100427 13732435
118121 14835679
137835 16612715
159738 20153840
184009 25306741
210839 29473030
240428 33670285
272990 39433633
308753 45339771
347956 53574855
390855 59553389
437717 64358362
488829 72540542
544492 77512410
605024 86230863
670764 96386431
742065 109597747
819305 122422846
902880 133815175
993208 147156643
1090730 162811396
1195910 182366636
1309240 198677537
1431233 222095061
1562434 258099620
1703414 292970404
1854773 330860334
2017143 360808583
2191190 392151227
2377612 429166134
2577140 457454844
2790548 494814497
3018641 541675289
3262270 592735996
3522324 649656089
3799738 695473667
4095490 752801952
4410608 807422513
4746166 868988173
5103292 944750175
5483165 1046144557
5887023 1146995280
6316157 1228101853
6771923 1354447080
7255737 1515887010
7769080 1659329490
8313503 1816496082
8890625 1985035112
9502140 2147314223
10149817 2324908194
10835506 2477474966
11561138 2640560677
12328729 2806263449
13140387 2984422619
13998309 3164744446
14904789 3358782177
15862223 3603356898
16873106 3914305381
17940045 4193346962
19065756 4468927903
20253072 4781356764
21504944 5077453573
22824451 5329708075
24214799 5664918826
25679329 6037288165
27221521 6276367404
28845000 6470694163
30553538 6768312376
32351067 7104091039
34241676 7460832056
36229621 7781954593
38319332 8060697671
40515419 8543737976
42822675 8978997959
45246087 9337733876
47790841 9861592151
50462328 10388096099
53266154 10900878268
56208145 11380017578
59294357 11840774986
62531083 12248420901
65924860 12632490349
66400801 12682746525
[9, 13]: ncombos=1551413175
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 431361
13591 1186889
20566 1653608
28261 1857155
36945 2471100
46782 3512350
57912 4259103
70470 5404146
84594 7033505
100427 8034191
118121 9358762
137835 10825411
159738 12916861
184009 15442106
210839 17596496
240428 20617698
272990 23855368
308753 27624955
347956 35256896
390855 42088472
437717 47005395
488829 53546372
544492 57127025
605024 64977390
670764 74166226
742065 82868263
819305 91885034
902880 100536148
993208 109891247
1090730 128809896
1195910 145639939
1309240 162254538
1431233 193964117
1562434 219571313
1703414 249509667
1854773 280311276
2017143 306985104
2191190 331955516
2377612 363529318
2577140 393977468
2790547 428704594
3018641 480235421
3262270 526546033
3522324 578287805
3799738 626389417
4095490 673359498
4410608 731734458
4746166 765197644
5103292 788483928
5483165 826768222
5887023 876015831
6316157 922383988
6771923 963620509
7255737 1023083698
7769080 1085754441
8313503 1141653180
8890625 1229185673
9502140 1308988717
10149817 1374184733
10835506 1448870713
11561138 1506975394
12136485 1551413175
[9, 14]: ncombos=20895250
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 270013
13592 1015286
20566 1620902
28261 2705457
36945 4114273
46782 5343057
57912 7131231
70470 8970658
84594 10367124
100427 11313158
118121 12765552
137835 14351260
159738 16558362
184009 18878900
210839 20599475
215086 20895250
[10, 10]: ncombos=2653783968
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 1056944
13591 2098636
20566 3255404
28261 4324420
36945 5617827
46782 7324338
57912 8524570
70470 10833600
84594 12897232
100427 14847050
118121 18597966
137835 21408708
159738 24605483
184009 27733765
210839 31620173
240428 38527514
272990 43279062
308753 47949331
347956 52699460
390855 57592882
437717 64345371
488829 72208634
544492 81212579
605024 90531493
670764 100218657
742065 110609211
819305 120789647
902880 135646235
993208 148629821
1090730 163086818
1195910 177692667
1309240 196058417
1431233 215280570
1562434 237728824
1703414 265898341
1854773 286693724
2017143 308901675
2191190 333159967
2377612 358935154
2577140 389322076
2790547 421797005
3018641 454158735
3262270 492579841
3522324 523825688
3799738 568953844
4095490 613536877
4410608 665251232
4746166 717887777
5103292 775493134
5483165 840425390
5887023 906446299
6316157 979768138
6771923 1051523735
7255737 1127011389
7769080 1200182041
8313503 1275428354
8890625 1357153329
9502140 1443156266
10149817 1545252797
10835506 1649998365
11561138 1756381327
12328729 1862493217
13140387 1969982489
13998309 2088497473
14904789 2202749142
15862223 2335965117
16873106 2469232066
17940045 2604642383
18539769 2653783968
[10, 11]: ncombos=2674987544
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 675660
13591 1619497
20566 2066296
28261 2847916
36945 3754540
46782 4415248
57912 5513132
70470 6449457
84594 7785559
100427 9080244
118121 10814282
137835 12531558
159738 14081217
184009 16555234
210839 19908113
240428 22627666
272990 25761314
308753 28618093
347956 32658638
390855 39489315
437717 44096562
488829 48372614
544492 52635036
605024 56769374
670764 62241845
742065 69625775
819305 77493307
902880 86047448
993208 93863987
1090730 103308179
1195910 112780375
1309240 122888133
1431233 136812116
1562434 149535046
1703414 163476522
1854773 177020754
2017143 195095780
2191190 213241705
2377612 234998586
2577140 262056261
2790547 283771754
3018641 301602075
3262270 326029651
3522324 348844854
3799738 372993428
4095490 402606117
4410608 435976700
4746166 468032591
5103292 503097978
5483165 534032121
5887023 575614544
6316157 617836204
6771923 664942826
7255737 718220111
7769080 770384539
8313503 834444243
8890625 900143526
9502140 976619849
10149817 1049112328
10835506 1127344081
11561138 1199934229
12328729 1269223858
13140387 1355025779
13998309 1439114375
14904789 1530579343
15862223 1636585024
16873106 1740933541
17940045 1846796642
19065756 1954882214
20253072 2063105164
21504944 2161110189
22824451 2273336632
24214799 2387654905
25679329 2507909812
27221521 2633172501
28018655 2674987544
[10, 12]: ncombos=1155521256
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 417551
13591 939942
20566 1537512
28261 1890752
36945 2424081
46782 2841675
57912 3429822
70470 4113723
84594 4969143
100427 5658538
118121 6676275
137835 8278475
159738 9585278
184014 11402424
210839 13228222
240428 15693619
272990 18602273
308753 21146538
347956 23168646
390855 25861207
437717 28571202
488829 31906615
544492 35963957
605024 39951151
670764 44337965
742065 49093828
819305 54509515
902880 60993977
993208 67814409
1090730 73826966
1195910 82087832
1309240 90801050
1431233 101550045
1562434 115003567
1703414 123876428
1854773 132575125
2017143 143249059
2191190 154004147
2377612 165684287
2577140 180217388
2790547 196727746
3018641 213501821
3262270 229001574
3522324 248265665
3799738 267379019
4095490 288198320
4410608 313720053
4746166 340048164
5103292 373498594
5483165 407608598
5887023 443171340
6316157 482534491
6771923 518583955
7255737 552295833
7769080 596137608
8313503 635339125
8890625 686081176
9502140 735484541
10149817 785973670
10835506 839153689
11561138 890164312
12328729 929674162
13140387 975417213
13998309 1024885188
14904789 1077370659
15862223 1134112786
16383311 1155521256
[10, 13]: ncombos=141348792
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 273812
13591 554546
20566 820349
28261 1220869
36945 1682118
46782 2346190
57912 2880365
70470 3406741
84594 4208329
100427 4991746
118121 5937505
137835 7019966
159738 8332206
184009 9519612
210839 11389317
240428 13745797
272990 15318491
308753 17043628
347956 18816178
390855 20737945
437717 23718698
488829 26859146
544492 29849136
605024 33008596
670764 37002096
742065 41235078
819305 46970800
902880 53387341
993208 60652617
1090730 66101472
1195910 73942941
1309240 81236247
1431233 89347910
1562434 98527617
1703414 107927677
1854773 113411153
2017143 120154597
2191190 128095784
2377612 135837655
2504993 141348792
[10, 14]: ncombos=1903760
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 230880
13591 662337
20566 1103491
28261 1504401
36945 1813342
39358 1903760
[11, 9]: ncombos=398056
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 148995
13591 372757
14587 398056
[11, 10]: ncombos=738804
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 114523
13591 300441
20566 433481
28261 575015
36945 734803
37126 738804
[11, 11]: ncombos=744707
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 94144
13591 265856
20566 380764
28261 509165
36945 661988
41897 744707
[11, 12]: ncombos=321693
memoizing scramble actions: 0 ms
elapsed ms #combos
5000 92657
13591 246396
17798 321693
[11, 13]: ncombos=39351
memoizing scramble actions: 0 ms
elapsed ms #combos
1999 39351
[11, 14]: ncombos=530
memoizing scramble actions: 0 ms
elapsed ms #combos
20 530
time=438839540

Process finished with exit code 0
 
Last edited:

xyzzy

Member
Joined
Dec 24, 2015
Messages
2,877
(No new result in this post; just some observations regarding the asymptotic bounds.)

In post #13 I calculated a lower bound for the uniform-distance swaps method, which must have worst case at least \( \Omega(N\log N) \) moves. This is because:
- there are \( \exp(\Theta(N)) \) possible u-d involutions on an \( N \)-element set
- thus counting argument forces the worst case number of u-d involutions needed in a decomposition to be \( \Omega(\log N) \)
- we have a method to do u-d involutions in worst-case \( \Theta(N) \) moves
- therefore this approach must have worst-case at least \( \Theta(N)\Omega(\log N)\equiv\Omega(N\log N) \) moves

The current proven upper bound using the u-d involution approach is only \( O(N\log^2N) \), so it's a priori plausible that we could continue using the same approach and reduce it further to \( O(N\log N) \). Two years of thinking about this problem on and off has not yielded any new result.

Uniform-distance swaps are very restrictive, which is the feature that allows us to do a lot of "long-distance" swaps in only \( O(N) \) moves, but it also makes using them very difficult. Probabilistic constructions of sorting algorithms (see e.g. AKS sorting network) basically repeatedly throw in random comparators/swaps until there's a nonzero chance that a correct sorting algorithm is produced (we don't know which collection of random choices leads to a correct algorithm, just that some collection exists), and the algorithms thus produced have no guaranteed clean structure, the exact opposite of uniform-distance swaps.

---

What other types of permutations can we provably do in \( O(N) \) moves? Consider the following class of permutations on the set \( \{0,\cdots,N-1\} \):
\(
\begin{aligned}
S:=\{&(a_0,b_0)(a_1,b_1)\cdots(a_{m-1},b_{m-1}):m\text{ is even and}\\
&0\le a_0<b_0<\cdots<a_{m-1}<b_{m-1}\le N-1\}\\
\end{aligned}
\)
Then by pairing these up in order, we have that all of these swaps can be done in \( O(\sum_{k=0}^{m-1}(b_k-a_k)+\sum_{k=1}^{m-1}(a_k-b_{k-1}))=O(N) \) moves. (See Lemma 8 in post #4.) The size of \( S \) is \( |S|=2^{N-2}+O(2^{N/2}) \). (See OEIS A038503. Exercise for the reader: prove this using a discrete-time Fourier transform.) Thus, as with the u-d involutions, the same idea shows that it's plausible that we can prove an \( O(N\log N) \) upper bound.

Unfortunately, this just doesn't work. Each of the permutations in \( S \) can change the number of inversions by at most \( 2N \), and since there exist permutations with \( \Theta(N^2) \) inversions, it follows that there are \( S \)-decompositions of length at least \( \Omega(N) \).

More generally, any approach that uses only 3-cycles or (2,2)-cycles without any inter-alg cancellation or shared setup moves must take \( \Omega(N\cdot\max(R,C)) \) moves in the worst case. This is because a 3-cycle or (2,2)-cycle alg that uses \( n \) moves can move three or four pieces by at most \( n \) spaces each, thereby reducing the summed distance by at most \( 3n \) or \( 4n \) respectively, but the maximum possible summed distance is \( \Theta(N\cdot\max(R,C)) \). (The u-d involutions method gets a better bound despite also being built on (2,2)-cycles because the setup moves are shared across many (2,2)-cycles.)

---

We can apply arbitrary even permutations to a 2×n region of the board in \( O(n\log n) \) moves. (See post #12.) Using this as a building block, we can sort the rows and the columns in at most \( O(N\log R+N\log C)\equiv O(N\log N) \) moves, up to parity (as in, at most two of the pieces may be out of order). From here… I'm not sure if there's any reasonable progress to be made. If \( R-C=O(1) \) (i.e. the board is square or almost square), then this row-sorting and column-sorting process cuts down the state space by a square root (from \( N!/2 \) to \( N!^{1/2+o(1)} \)), which isn't a lot.

(See also: (standard) Young tableaux.)
 

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
5x5 GN is at most 46.
I reduced the GN of 5x5: 0x0 --> 3x3 to 18, using several new techniques:
First, I split this solving stage into the phases null --> AC KM --> 3x3 (ABC FGH KLM) instead of null --> AB FG --> 3x3, which decreases the scrambles I would have to process from ~233e9 to ~188e9.
Second, in addition to applying prefix move sequences to each scramble I test, I also try solving it with different block-building phases; for example, I try solving a given scramble of the pieces ABC FGH KLM by first solving AB FG and then the rest, or first solving GH LM and then the rest. (A similar technique was used by xyzzy to solve 5x5: 3x3 --> 5x5). On each of these alternative block-building phases, I also apply prefix move sequences if necessary.
A total of 188,592,895,657 scrambles was processed in 100368.865 seconds (about 27.8 hours). At most 3 moves were needed for a prefix move sequence. 18+28=46.
UPDATE (2021-07-18): So far, trying to reduce 5x5: 0x0 --> 3x3 to 17 moves has resulted in a java.OutOfMemoryError. Improving the second phase (3x3->entire board) also seems to require processing hundreds of billions of scrambles.
UPDATE (2021-08-01): 5x5 GN is at most 45.
I finally reduced 5x5: 0x0 --> 3x3 to 17 moves. The process was split into two parts. The first part was slightly faster but hit a java.OutOfMemoryError partway through. The second part consumed less memory but ran much more slowly. The combined computation time was about 11-12 days. At most 6 prefix moves were needed. Code and stdout is at https://gist.github.com/coolcomputery/c4af0f79f7a2d8a9c774395845058c04.
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
Disclaimer: No new results.
Slightly tighter counting of 5x5 move sequences at fixed depths, continuing from xyzzy's post #6 (https://www.speedsolving.com/threads/loopover-gods-number-upper-bounds-4×4-asymptotics-etc.75180/#post-1333877).

On a 5x5, the move sequences R1 C0 R0 C0' and C0 R0 C0' R1 yield the same scramble.
To prevent counting both of these syllable sequences, consider syllables A, B of opposite type (i.e. one is horizontal and another is vertical). Define \( S(A,B)=\{r | (>>r)A^{-1}BA == A^{-1}BA(>>r)\} \), where (>>r) is the action that shifts row r right one unit, or \( \{(,,c)A^{-1}BA == A^{-1}BA(,,c)\} \), where (,,c) is the action that shifts column c down one unit, according to the types of A, B. Also, define \( M(A)=\{r|A[r]==0\} \), where A[r] is the amount that syllable a shifts row/column r one unit in the right/down direction.
Then we can restrict our counting of syllable sequences to the following: for any set of 4 consecutive syllables in the sequence that are of the form \( \dots A^{-1} B A C \dots\), we must have \( S(A,B) \cap M(C) = \emptyset \). We can call such syllable sequences "good".
We can count the number of "good" syllable sequences at each depth using DP (source code). Define \( dp_a(k,t,d)_{A,B}= \) # "good" syllable sequences with \( d \) total moves, \( k \) total syllables, and last syllable being of type \( t \) that end as \( \dots C A B \) for any \( C\neq B^{-1} \). Define \( dp_b(k,t,d)_{A,B}= \) same thing but require syllable sequences to end as \( \dots B^{-1} A B \). Then we have the following:

\[ dp_a(k,t,d)_{A,B}=\sum_{C\neq B^{-1}} dp_a(k-1,1-t,d-|B|)_{C,A} + \sum_{C\neq B^{-1}\wedge S(A,C)\cap M(B)=\emptyset} dp_b(k-1,1-t,d-|B|)_{C,A} \]

\[ dp_b(k,t,d)_{A,B}=dp_a(k-1,1-t,d-|B|)_{B^{-1},A} + (S(A,C)\cap M(B)=\emptyset) dp_b(k-1,1-t,d-|B|)_{B^{-1},A} \]

Here, \( |A|= \) total # of moves needed to execute syllable \( A \).

The base cases occur when \( k=3 \). The cases \( k<3 \) can be dealt with separately.

Computing these DP states naively would take about \( O((N^N)^3) \) time for each triplet \( (k,t,d) \), which is too slow, so we add some helper variables:

\[ h_a(k,t,d)_A=\sum_C dp_a(k-1,1-t,d)_{C,A} \]

\[ h_b(k,t,d)_{A,M}=\sum_{M' | M'\cap M=\emptyset} h_c(k,t,d)_{A,M'} \]

\[ h_c(k,t,d)_{A,M}=\sum_{C | S(A,C)=M} dp_b(k-1,1-t,d)_{C,A} \]

Then we can evaluate \( dp_a(k,t,d)_{A,B} \) as \( h_a(k,t,d-|B|)+h_b(k,t,d-|B|,M(B))-dp_b(k,t,d)_{A,B} \). To reduce memory usage, we avoid directly storing any values in \( dp_a(k,t,d) \). Also, we split the DP dependence into two chains based on tuples (k,t): (3,0)<--(4,1)<--(5,0)<--... and (3,1)<--(4,0)<--(5,1)<--... and evaluate each chain separately. In each chain, after computing all \( h_a(k,t,d)_A, h_b(k,t,d)_{A,M}, dp_b(k,t,d)_{A,B} \), we delete \( h_a(k-1,1-t,...), h_b(k-1,1-t,...), dp_b(k-1,1-t,...) \). Additionally, for each fixed (k,t), after computing all \( h_a(k,t,d)_A, h_b(k,t,d)_{A,M} \), we first fix a value \( d_n \), then evaluate \( dp_b(k,t,d)_{A,B} \) only for \( B \) such that \( |B|=d-d_n \), then delete \( dp_b(k-1,1-t,d_n) \). Before deletion, though, we store several totals, \( T(k,t,d)=\sum_{A,B} dp_a(k,t,d)_{A,B}+dp_b(k,t,d)_{A,B} \). We use these in the end to count how many good syllable sequences there are with total move count at or below a certain threshold, \( d_{max} \).

Unfortunately, the 5x5 GN lower bound of 22 is not improved. Here are the cumulative total number of good syllable sequences at or below 0, 1, 2, ... 22 moves, versus the cumulative totals for normal syllable sequences:

good syllables
0:1
1:21
2:321
3:4641
4:65561
5:923145
6:12994265
7:182929945
8:2575201225
9:36251812425
10:510322952217
11:7183898083097
12:101128894777897
13:1423607949716137
14:20040360519744777
15:282111408726963753
16:3971328093414571593
17:55905030207130704553
18:786984184955193366713
19:11078504118051284217113
20:155953900775003742325737
21:2195388376234705442432377
22:30904838535964351025431817

normal syllables:
0:1
1:21
2:321
3:4641
4:66761
5:960345
6:13814665
7:198724745
8:2858665225
9:41122041225
10:591542609417
11:8509369868297
12:122407708919817
13:1760840982947337
14:25329785146646537
15:364370219564769289
16:5241483736914045449
17:75399004334521259529
18:1084618428671161162249
19:15602290059346154478089
20:224439718762861186359817
21:3228576520930493071364617
22:46443233884627791532876297

Note: It is possible to further tighten syllable sequence counts by requiring that in all syllable sequences, for every set of 4 consecutive syllables \( \dots A B C D \dots \), we have \( S(A,B,C) \cap M(D)=\emptyset \), where\( S(A,B,C) \) is an extension of \( S(A,B) \) for the syllable composition \( ABC \) instead of \( A^{-1}BA \). However, the only DP I know to count such syllable sequences requires far too much memory (on the order of \( O((N^N)^3) \) states for each fixed triple \( (k,t,d) \) instead of \( O((N^N)^2) \) states) to calculate in a reasonable amount of time.
 
Last edited:

rokicki

Member
Joined
Oct 31, 2008
Messages
301
On a 5x5, the move sequences R1 C0 R0 C0' and C0 R0 C0' R1 yield the same scramble.
I've pursued this up to length-12 identities (length-6 identical subsequences) and you're right, it doesn't tighten the bound. (This functionality is built into twsearch; use -C in conjunction with --newcanon # where # goes as high as you can until you run out of memory or patience.)

For comparison, if you want, here are the first several values I get for --newcanon 4:

Code:
D 0 this 1 total 1
D 1 this 20 total 21 br 20
D 2 this 300 total 321 br 15
D 3 this 4320 total 4641 br 14.4
D 4 this 60920 total 65561 br 14.10185185185185
D 5 this 845184 total 910745 br 13.8736703873933
D 6 this 11720315 total 12631060 br 13.86717566825685
D 7 this 162618240 total 175249300 br 13.87490353288286
D 8 this 2255712285 total 2430961585 br 13.87121324766521
D 9 this 31289289688 total 33720251273 br 13.87113502731134
D 10 this 434046099165 total 467766350438 br 13.87203428051818
D 11 this 6021036796248 total 6488803146686 br 13.87188321201601
D 12 this 83522805650006 total 90011608796692 br 13.87183112749836
D 13 this 1158617782388288 total 1248629391184980 br 13.87187335688124
 

GodCubing

Member
Joined
May 13, 2020
Messages
247
What is God's Number for 2x2 and how is it optimally solved? Is it like 2 phase or is there another way
 

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
What is God's Number for 2x2 and how is it optimally solved? Is it like 2 phase or is there another way
For 2x2 Loopover, God's number is 4. There are only 24 possible scrambles so it is possible to brute-force the entire configuration space. A 4-move scramble is:

Code:
DC
BA
 

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 96.
I reduced the GN for solving the 1,2,3,7,8,9,13,14,15 block (i.e. the top-left-most 3x3 block).
First, I split it into solving 1,3,13,15 and then solving the rest of the pieces.
Then, I applied a symmetry reduction to avoid testing as many possible scrambles for the first phase as I would have to (this reduced the total # of scrambles by about 8 times).
Finally, on top of the prefix move trick and the alternate block-building trick as described in post #24, I added "transformed solving", where given a scramble, I test if solving a "transformed" version of that scramble leads to a shorter solution. If it does, then applying the inverse transformation to that solution yields a solution for the original scramble. A total of 34,961,702,384 scrambles was processed in about 20-21 hours. 24 (0x0->1,3,13,15->3x3) + 21 (3x3->4x4) + 27 (4x4->4x5->5x5) + 24 (5x5->6x6)=96.

(2021-08-21)
Using this same symmetry reduction technique, 5x5 GN is at most 44. I reduced the two phases 3x3->4x4->5x5 to at most 27 moves. A total of 274,724,883,578 scrambles was processed in about 7 days (the program was split into two sessions after the first session was accidentally stopped partway through). 17 (0x0->ACKM-->3x3) + 27 (3x3->4x4->5x5)=44.

(2021-08-23) 6x6 GN is at most 95.
The two phases 4x4->4x5->5x5 take at most 26 moves to solve. 7,747,057,906 scrambles were processed in 28625.784 seconds (about 8 hours).

Rigorous explanation of symmetry reduction and scramble transformation:
We represent all scrambles, permutations, and transformations as lists of numbers.
For two lists of numbers \( A, B \), define the product \( AB=[ \dots A[B[ i ]] \dots ]_i \). If, for any i, \( B \) is out of index range of \( A \), then \( AB \) is undefined. Note that for three lists \( A, B, C \), if \( ABC \) is defined, then we have \( (AB)C=A(BC) \), i.e. the product of lists is associative.
We represent a permutation (aka a "scramble action") on the board as \( A \), where location i on the board is moved to location \( A \) for each i. All elements must be distinct and in the set \( \{0\dots len(A)-1 \} \). (Technically any indexing of the cells of the Loopover board will work, although I use row-major indexing).
Denote \( \mathcal{M} \) the set of permutations that are individual moves of the RxC Loopover Board.
We represent a space transformation, i.e. a transformation of the entire board, as a permutation \( S \), where location i on the board is moved to location \( S \) for each i. Then a permutation \( A \) that is transformed under \( S \) is defined as the permutation \( SAS^{-1} \).
All space transformations \( S \) that we consider must be "rigid", meaning that for all permutations \( M \in \mathcal{M} \) we have \( SMS^{-1} \in \mathcal{M} \). Consequently, if \( A \) can be represented as the product of \( k \) individual moves \( \prod_{i=0}^{k-1} M_i \), then \( SAS^{-1} \) can be also represented as the product of \( k \) moves \( \prod_{i=0}^{k-1} SM_iS^{-1} \). This is a very important property.

Now suppose we have a scramble \( P \) of only a subset of pieces on the Loopover board, ex. of the pieces ABEF on the 4x4 board. We want to transform \( P \) into a target \( T \). In our example, \( T=[0,1,4,5] \). Let's have \( P=[6,15,2,13] \). The board will look like this:
Code:
..E.
..A.
....
.F.B
Suppose some permutation \( A \) over the entire board solves \( AP=T \). Now, what could the scramble \( SAS^{-1} \) solve, for a carefully chosen S? Suppose S rotates the board clockwise around the 2x2 square occupied by AB EF in the solved board:
Code:
ABCD     EAIM
EFGH --> FBJN
IJKL     GCKO
MNOP     HDLP
S=[1,5,9,13,0,4,8,12,3,7,11,15,2,6,10,14]
If we transform the locations of pieces described by \( P \) under \( S \), we get \( SP \). Applying \( SAS^{-1} \) yields \( SAS^{-1}SP=SAP=ST \), which is not necessarily equal to \( T \). However, for our specific \( S \), the 2x2 region that \( T \) occupies is preserved, i.e. the locations that AB EF are supposed to occupy only get permuted among each other, and not to any other locations outside of \( T \). This means there exists a permutation \( Q \) s.t. \( STQ=T \). Consequently, \( SAS^{-1} \) solves the scramble \( SPQ \).

To generalize, define the function \( \mathcal{Q}_T(S)=Q \texttt{ s.t. } STQ=T \texttt{ if such Q exists else } \emptyset \) and the set \( \mathcal{T}(T)=\{S \texttt{ s.t. } \mathcal{Q}_T(S)\ne\emptyset\} \). (Note that if \( \mathcal{Q}_T(S)\ne\emptyset \), then \(\mathcal{Q}_T(S) \) must have a unique value.)
Then we have \( \forall S\in \mathcal{T}(T), SAS^{-1} \texttt{ solves } SP\mathcal{Q}_T(S) \). This is the essence of the "transformed solving" trick: instead of solving a given scramble \( P \) directly, we first see if there is a space transformation \( S\in \mathcal{T}(T) \) and a sufficiently short solution \( B \) that solves \( SP\mathcal{Q}_T(S) \); if so, then we have a solution \( A=S^{-1}BS \) to the original scramble \( P \). The crucial thing is that the number of individual moves required to obtain \( B \) is the same as the number of individual moves required to obtain \( S^{-1}BS \), which is why it is correct to use this trick in the first place.

Phase 0 symmetry reduction:
For a specific target list \( T \) (and a restriction on which individual moves are allowed on the Loopover board), a BFS tree \( tree_T \) for \( T \) maps every possible scramble \( P \) to an arbitrarily chosen scramble action \( A=tree_T(P) \) over the entire board, such that \( AP=T \) and that the number of individual moves required to obtain \( A \) is minimized.
Now suppose our two phases are described by the targets \( T_0,T_1 \). The overall target of these two phases combined is \( T=[T_0|T_1] \), where | is list concatenation. Let a pair of phase scrambles \( P_0, P_1 \) represent the composite scramble \( f(P_0, P_1):=[P_0|A^{-1}P_1] \), where \( A=tree_{T_0}(P_0), B=tree_{T_1}(P_1) \), and we require that \( BT_0=T_0 \), i.e. that phase 1 does not disrupt any pieces that are solved at the end of phase 0. Thus, \( BAf(P_0,P_1)=T \).
Traditional two-phase optimization involves finding alternative solutions to all scrambles \( \in\cup_{\texttt{all necessary P_0}} \mathcal{S}_{P_0} \), where \( \mathcal{S}_{P_0}:=\{ f(P_0,P_1) \ \forall P_1 \} \). However, we can use the above idea of transformed solving, although we must be more restrictive on \( S \) than we were previously: if we let \( E \) be the set of pieces that are unsolved before either phase 0 or phase 1 start (ex. for the phases 3x3->4x4->5x5 on 5x5 Loopover. \( E=[3, 4, 8, 9, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24] \)), then we require that \( S\in\mathcal{T}(T_0)\cap\mathcal{T}(T_1)\cap\mathcal{T}(E) \).
Using this idea of transformed solving, if there exists a solution \( C \) s.t. \( C[P_0|A^{-1}P_1]=T \), then \( (SCS^{-1})[SP_0\mathcal{Q}_{T_0}(S)|SA^{-1}P_1\mathcal{Q}_{T_1}(S)]=T \). Therefore, if we obtain a solution to \( [P_0|A^{-1}P_1] \) requiring \( \leq t \) moves for some threshold \( t \), we immediately know that \( [SP_0\mathcal{Q}_{T_0}(S)|SA^{-1}P_1\mathcal{Q}_{T_1}(S)]=T \) is also solvable in \( \leq t \) moves. Thus, if we prove that all scrambles \( \in\mathcal{S}_{P_0} \) are solvable in \( \leq t \) moves for a fixed \( P_0 \), then we know that all scrambles \( \in\mathcal{S}_{SP_0\mathcal{Q}_{T_0}(S)} \) are also solvable in \( \leq t \) moves, for all valid \( S \). Therefore, we can partition the set of all \( P_0 \) into equivalence classes, where for two phase-0 scrambles \( X,Y \), we define equivalence \( X\equiv Y \) as \( \exists S\in \mathcal{T}(T_0)\cap\mathcal{T}(T_1)\cap\mathcal{T}(E) \texttt{ s.t. } X=SY\mathcal{Q}_{T_0}(S) \). Then, during two-phase optimization, we only iterate over one \( P_0 \) in each equivalence class.

(Update 2021-08-20: fixed a minor technical error in phase 0 symmetry reduction by adding the list E)
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 94.

The two phases 4x4->4x5->5x5 take at most 25 moves to solve.
24 (0x0->1,3,13,15->3x3) + 21 (3x3->4x4) + 25 (4x4->4x5->5x5) + 24 (5x5->6x6)=94.
Code (specifically the BFS.java and BFS2improve files): https://github.com/coolcomputery/Lo...tree/3aaf37d8e94059b41622e17c2d2cd4779ccac4e3
Stdout: https://gist.github.com/coolcomputery/f1c46f1c24e8a341afa7bc7cda7a4bfe
Total running time was 129523.756 seconds (about 36 hours), although I estimate that about 27000 seconds were of my laptop sleeping (I was traveling and didn't have access to laptop charging for a few hours, and my laptop was almost dead, so I had to pause the program during then by making my laptop sleep; the actual running time was about 28 hours).

I completely rewrote my BFS and BFS-pair-optimization programs to use a much more generalized and powerful method of improving 2-phase God's numbers. In summary, for every scramble that by default would take too many moves, I now iteratively DFS over every possible phase 0 solution move sequence, in increasing order of move count, to find a sufficiently short alternative solution to the scramble.

Rigorous explanation (using the same notation as in my previous forum post):

A scramble of \( R\times C \) Loopover is defined as an permutation array \( S \), where the cell at location index \( i \) goes to location index \( S_i \); the \( (r,c) \) location in the Loopover board is given the index \( rC+c \). Applying a scramble \( B \) on top of a scramble \( A \) forms the "product scramble" \( BA \), where \( (BA)_i=B_{A_i} \). Solving a scramble \( S \) across the entire board consists of finding a list of single-cost moves \( M_0,\dots,M_{m-1} \) such that \( (\prod_{i=m-1}^{i=0} M_i)S=I=[0,1,\dots RC-1] \), i.e. such that we transform \( S \) to the identity permutation \( I \). If we want to only solve a list of location indices \( T \) within a scramble \( S \), then we transform \( S \) to some permutation \( S' \) such that \( S'T_0=T_0 \).

Let our solving blocks be \( T_0 \) and \( T_1 \) and our "pre-block" be \( T_p \). By building our two BFS trees, for every scramble \( S \) such that the region \( T_p \) is already solved, we have a default phase 0 solution \( \mathcal{A}(S)=A=\prod_{i=m-1}^{i=0} M_i \), for some single-cost moves \( M_i \) s.t. \( M_iT_p=T_p \), such that \( AST_0=T_0 \), and a default phase 1 solution \( \mathcal{B}(AS)=B=\prod_{i=n-1}^{i=0} N_i \), for some single-cost moves \( N_i \) s.t. \( N_iT_0=T_0 \), such that \( BAST_1=T_1 \) (note that in the product expressions for \( A, B \) the index \( i \) is in the opposite order it usually is). This way, we never disturb block \( T_p \) during phase 0 or block \( T_0 \) during phase 1. Since \( BAST_1=T_1 \), we say that \( A \) and \( B \) together solve \( S \) "up to \( T_1 \)".
The 4x4->4x5->5x5 phases for 6x6 Loopover would correspond to the blocks \[ T_p=[0,1,2,3,\ 6,7,8,9,\ 12,13,14,15,\ 18,19,20,21],\]\[T_0=[0,1,2,3,4,\ 6,7,8,9,10,\ 12,13,14,15,16,\ 18,19,20,21,22],\]\[T_1=[0,1,2,3,4, 6,7,8,9,10,\ 12,13,14,15,16,\ 18,19,20,21,22,\ 24,25,26,27,28,29].\]

In BFS-pair-optimization, for every scramble \( S \) such that the default phase solutions together take \( >t \) moves, we find an alternative solution for \( S \). In the past, I would first apply an arbitrary product of a sequence of moves \( P \) on scramble \( S \), then check if the default solutions \( A=\mathcal{A}(PS) \) and \( B=\mathcal{B}(APS) \) together take \( \le t \) moves, then repeat with some other \( P \) if needed, with \( P \) increasing in number of moves until a short enough solution for solving \( S \) up to \( T_1 \) was found. Later on I also allowed \( alternative\ block-building \), in which I replace \( T_0 \) with something else when finding an alternative solution for \( S \), ex. extending the 4x4 block to 5x4 instead of 4x5, which corresponds to \( T_0'=[0,1,2,3,\ 6,7,8,9,\ 12,13,14,15,\ 18,19,20,21,\ 24,25,26,27] \), but this method would still have to try too many possible \( P \) and thus become too slow for larger BFS-pair-optimization test case. Additionally, because I used BFS to generate all possible \( P \) within a certain move count, the program would run out of Java heap space; this is exactly what happened in the 4x4->4x5->5x5 phase optimization at threshold \( t=25 \) that the new method solves.

In the new method, I choose some number \( l \), starting at the minimum number of moves needed to solve \( S \) up to \( T_0 \), then DFS over all possible \( A \) obtainable with \( \le l \) moves such that \( AST_0=T_0 \), which can be done reasonably quickly with some pruning, until \( A \) together with the resulting phase 1 scramble \( \mathcal{B}(AS) \) take \( \le t \) moves. If no such sufficiently short solution is found, try alternative block-building. If still no solution is found, increase \( l \) by 1 and try again.

Because this new method is much more direct in searching for alternative phase 0 solutions, and it generates them using DFS instead of BFS, it finds sufficiently short solutions far more quickly and uses far less memory. The code is also simpler, as I can remove the "transformed solving" technique I described in the last forum post, as well as several now-obsolete helper methods. (Edit: transformed solving actually can still have an effect; I just didn't include it because I wanted to start off simple when rewriting my programs; I will probably add back transformed solving at some point).

Important speed optimizations:

I use a lot of lookup tables. Also, when not using alternative block-building, I try improving all scrambles \( S \) with a certain fixed phase 0 scramble portion (i.e. with the same sub-scramble \( ST_0 \)) at once, by only DFSing on the phase 0 solution once and then testing all applicable \( S \) with each generated solution.

I didn't use phase 0 symmetry reduction this time, as in the case of 6x6: 4x4->4x5->5x5 it does nothing. However, it will be important in other BFS-pair-optimization test cases I plan to do later.
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 93.

The phase 4x4->5x5 has a GN of 24, and this time it's tight. After finally realizing that I have a 64-bit JVM and can increase Java heap space beyond 4 GB, I simply ran a BFS over the entire phase instead of using the 2-phase + threshold technique like I have been for the past several months.
24 (0x0->1,3,13,15->3x3) + 21 (3x3->4x4) + 24 (4x4->5x5) + 24 (5x5->6x6)=93.

Code: https://github.com/coolcomputery/Lo...1d92941c7cbb18da1c09900db05/BFSLargeFile.java
There are 20!/11!=60949324800 states in the phase. BFSing all of them took 175950.654 seconds, or about 49 hours. Total memory usage was <=10 GB in Java heap space (using the flag \( \texttt{-Xmx10g} \) in the command line) and 304.83 GB on disk.

Distribution:
Code:
0:1
1:4
2:20
3:101
4:462
5:2093
6:9298
7:40215
8:171078
9:712885
10:2892970
11:11380055
12:42963444
13:154142212
14:518897987
15:1599501934
16:4319908641
17:9553119850
18:15751315904
19:16900073140
20:9726694660
21:2217469365
22:147741036
23:2285403
24:2042

I use 0-indexing, so the solved state for the 4x4->5x5 phase looks like this:
Code:
  X  X  X  X  4  .
  X  X  X  X 10  .
  X  X  X  X 16  .
  X  X  X  X 22  .
 24 25 26 27 28  .
  .  .  .  .  .  .
There are 2042 antipodes for this phase. One of them is:
Code:
  X  X  X  X 16  .
  X  X  X  X  4 10
  X  X  X  X  .  .
  X  X  X  X  . 27
  . 26 25  .  .  .
 24 28  . 22  .  .
I have attached a file to this forum post containing the full list of antipodes.
 

Attachments

  • 6x6:4x4-5x5_antipodes.txt
    229.3 KB · Views: 1

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
No new upper bounds, but I have found that the 0x0->3x3->5x5 block-building approach for solving 5x5 Loopover can at best yield an upper bound of 16+25=41, if during the 3x3->5x5 phase we are only allowed to move the last two rows and last two columns.
Code:
.....
.....
..MLK
..HGF
..CBA

depth 16: R2' R3' C1' C3 R0 R3' C3 R0 C4 R1 C1' R3' C1' R2' R0 C2

...PU
...QV
...RW
DINSX
EJOTY

depth >=25, where only the last two rows and last tow columns can be moved: no explicit solution found

I first run a partial BFS over the entire scramble space, then for a given scramble I iteratively DFS over (canonical) move sequences of increasing length until applying the move sequence to the scramble yields a new scramble that has already been visited in the partial BFS. "Canonical" means that a move cannot be immediately followed by its inverse, and if there are two consecutive row moves Ra(s),Rb(t) or column moves Ca(s),Cb(t), where s,t=1,-1, then a<=b (since such pairs of moves are commutative, so we can force an order on them). Code is at https://github.com/coolcomputery/Lo...cbc445a60866be2faa986dd1dcae9744/BFS_DFS.java, along with (partial) program output (click on the three dots next to the commit message to show).

Note that from an earlier result, God's number of 0x0->3x3 is at most 17, which is only one more than the current lower bound of 16 (as shown above). I've been trying to prove an upper bound of 16 (in fact I already tried it once back in November 2021), but my code requires trying a few hundred to a few thousand solutions per scramble, and I estimate that with my current code it will take about 13 days to complete, so for now I will focus on optimizing my code.
 

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 23+19+23+24=89.

Code:
......     #.#...     #.#.#.
......     ......     ......
...... --> #.#... --> #.#.#.
......     ......     ......
......     ......     #.#.#.
......     ......     ......
GN <= 23 (2-phase improvement)
https://gist.github.com/coolcomputery/8df7c6376572177e96ef77a518c92a49
59874.516 seconds
Code:
#.#.#.     ###.#.
......     ###.#.
#.#.#. --> ###.#.
......     ......
#.#.#.     ###.#.
......     ......
GN = 19 (BFS)
https://gist.github.com/coolcomputery/58244113ebe484b2ec69d1f762126057#file-6x6-010101x010101-000101x000101_stdout-txt
4180.937 seconds
0:1
1:4
2:28
3:170
4:932
5:4892
6:24946
7:123168
8:586358
9:2659448
10:11316244
11:44222892
12:153644726
13:450373068
14:1013585741
15:1481606620
16:1061671686
17:246558712
18:9284500
19:7064
Code:
###.#.     #####.
###.#.     #####.
###.#. --> #####.
......     #####.
###.#.     #####.
......     ......
GN = 23 (BFS)
https://gist.github.com/coolcomputery/58244113ebe484b2ec69d1f762126057#file-6x6-000101x000101-000001x000001_stdout-txt
116255.370 seconds
0:1
1:4
2:20
3:98
4:444
5:1980
6:8695
7:37618
8:160443
9:674029
10:2779829
11:11186512
12:43572549
13:162549363
14:571952209
15:1849682401
16:5239753101
17:11949256158
18:19002513098
19:16462006262
20:5266439024
21:382800089
22:3949330
23:1543
Code:
#####.     ######
#####.     ######
#####. --> ######
#####.     ######
#####.     ######
......     ######
GN = 24 (BFS)
already known; can also be calculated with the line
    new BFS("000001x000001","000000x000000");
~23 seconds

Source code is at https://github.com/coolcomputery/Lo...tree/f1197382a3d2811debeb240bb6c66465bff8c054 with classes BFS.java, BFS2improve.java, BFS_DFS.java, and BFSLowMemory.java used (BFS_DFS.java is referenced in the code of BFS2improve.java but it was not actually used in the specific 2-phase improvement).

(Note: some parts of the standard out may look strange because my laptop may have been asleep for a few hundred seconds at a time.)

I simplified my 2-phase improvement by making symmetry reduction less restrictive, which allows me to use all 72 symmetries between the start and final state in the 2-phase improvement section. I also made a new and even more memory-efficient BFS program that uses two bitsets stored as binary files, rather than several lists of indices of all nodes at each depth. For the larger test case that took 116255.370 seconds, the old program for large BFS trees would use about 20x as much disk memory.

Explanation (for a third time but I hope this time it is clearer than the last two):

Again, we represent the location on row \( r \) and column \( c \) on the \( R\times C \) Loopover board with the index \( rC+c \). A permutation ("scramble") over a board is represented with a list \( A \), where tile \( i \) is sent to location \( A_i \).

The product of two lists \( A,B \) is defined as \( C=AB \) such that \( C=A_{B_i} \). This product is associative.

The set of all permutations made from a single move (i.e. a single-unit shift of one row or column) is \( \mathcal{M} \).

In 2-phase optimization, we are given three lists of pieces \( R_0,R_1,R_2 \) such that \( R_0\subset R_1\subset R_2 \) (i.e. all pieces in \( R_0 \) are contained in \( R_1 \), all pieces in \( R_1 \) are contained in \( R_2 \), and the three lists are all different from each other). For each scramble \( P \) such that \( PR_0=R_0 \) (i.e. all pieces in \( R_0 \) are already solved), we want to find a permutation \( A=M_{k-1}\dots M_1 M_0 \) made of \( k\le \) some threshold \( t \) number of moves, such that \( APR_2=R_2 \) (i.e. applying \( A \) to \( P \) solves all pieces in \( R_2 \) (which includes all pieces in \( R_0 \))), and none of the moves \( M_i \) affect any pieces in \( R_0 \).

However, directly finding such \( A \) may be too expensive, since the search space may be too big. Instead, we construct the BFS tree of all permutations of pieces in \( R_1 \) with \( R_0 \) already solved, and the BFS tree of all permutations of pieces in \( R_2 \) with \( R_1 \) already solved. When solving a \( P \), we first apply an optimal permutation \( A \) (i.e. a permutation made of the lowest number of moves) to solve up to \( R_1 \) (i.e. \( APR_1=R_1 \)), then apply another optimal permutation \( B \) to solve up to \( R_2 \) (i.e. \( BAPR_2=R_2 \)), using the BFS trees to find such optimal permutations. Then if \( A \) and \) B \) collectively require more than \( t \) moves, we try to find a better solution (explained in more detail at the end of the post).

Symmetry reduction:

Let \( S \) be a "rigid" transformation over the entire board, meaning that for every single-move permutation \( M \) in \( \mathcal{M} \), \( SMS^{-1} \) is also a single-move permutation (ex. \( S \) can be a translation, rotation, reflection, or any composition of these transformations, of the entire board). We further require that there exist permutations \( Q_0,Q_2 \) such that \( S R_0 Q_0 = R_0 \) and \( S R_2 Q_2 = R_2 \) (i.e. the region that the pieces \( R_0 \) form is preserved, and so is for \( R_2 \)).

Suppose we have \( P \) such that \( PR_0=R_0 \), and \( A=M_{k-1}\dots M_1 M_0 \) such that \( APR_2=R_2 \). Let \( P'=SPS^{-1} \) and \( A'=SAS^{-1} \); then \( P'R_0=(SPS^{-1})(SR_0 Q_0)=SP(S^{-1}S)R_0 Q_0=SPR_0 Q_0=SR_0 Q_0=R_0 \) and \( A'P'R_2=(SAS^{-1})(SPS^{-1})(SR_2 Q_2)=SA(S^{-1}S)P(S^{-1}S)R_2 Q_2=SAPR_2 Q_2=SR_2 Q_2=R_2 \), so \( P' \) already has \( R_0 \) solved and \( A' \) solves \( P' \) up to \( R_2 \). Also, since \( SAS^{-1}=(SM_{k-1}S^{-1})\dots (SM_1 S^{-1})(SM_0 S^{-1}) \), \( A \) and \( A' \) can be made of the same number of moves.

This means that if we can solve \( P \) in \( \le t \) moves, we can also solve \( SPS^{-1} \) in \( \le t \) moves. Therefore, from the set of all permutations \( \{SPS^{-1}\} \) for valid \( S \) under fixed \( P \), we only have to solve one of them. Currently, we choose the lexicographically lowest permutation.

In the algorithm, we actually only care about the part of \( P \) that are in \( T= R_2 \setminus R_0 \) (i.e. the set of pieces we are trying to solve); the existance of \( Q_0 \) and \( Q_1 \) imply the existence of some \( Q \) such that \( STQ=T \); then \( (SPS^{-1})T=SPS^{-1}(STQ)=S(PT)Q \), so the "subscramble" \( U=PT \) is transformed into \( SUQ \).

In the past, I would further restrict \( S \) to also preserve the region that the pieces \( R_1 \) form, since that would allow us to do symmetry reduction over all \( P \) without having to iterate over every possible \( P \). However, I currently don't know any tricks to analyzing the lexicographic order of \( U \) changes when it becomes \( SUQ \), so for now I iterate over all possible \( U \). When the threshold \( t \) is high enough and it is not too difficult to find alternative solutions for permutations that initially require \( >t \) moves, this program is much slower than my previous 2-phase improver. However, for low enough \( t \) (ex. 5x5: 0x0->ACKM->3x3, \( t=16 \)), both programs' running times are similar.

More detail on how to find solutions of \( \le t \) moves:

We first iteratively DFS over every permutation \( A \) made of \( l_a \) moves that solves \( P \) up to \( R_1 \) (i.e. \( APR_1=R_1 \)), then check if \( AP \) can be solved up to \( R_2 \) in \( \le t-l_a \) moves (which can be done efficiently with the second BFS tree). After each DFS, we increment \( l_a \) and repeat; if \( l_a \) goes past \( t \), then we know \( P \) cannot be solved up to \( R_2 \) in \( \le t \) moves.

(Not used in the 6x6 2-phase improvement but it could be useful for other test cases) At some point in the middle of this process, we may terminate and switch to a meet-in-the-middle approach: we run a partial BFS of all pieces in \( R_2\) with \( R_0 \) already solved up to a cetain depth, then iteratively DFS over all permutations \) A \) made of an increasing number of moves until \( APR_2 \) appears in our BFS tree, and check if the generated solution is at most \( t \) moves. This solution is guaranteed to be optimal, so if is more than \( t \) moves, then \( P \) cannot be solved in \( \le t \) moves, and the God's number of \( R_0 \rightarrow R_2 \) is more than \( t \).
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 22+19+23+24=88.
Code:
......     #.#...     #.#.#.
......     ......     ......
...... --> #.#... --> #.#.#.
......     ......     ......
......     ......     #.#.#.
......     ......     ......
GN <= 22 (2-phase improvement)
stdout: https://gist.github.com/coolcomputery/ba0713fad041ae32b0bd777c30b7230a
94537.805 seconds

New code (of BFS2improve.java) is at https://github.com/coolcomputery/Lo...6a724c373a9770aeba99787d1528/BFS2improve.java.

In my last post, I said
...I currently don't know any tricks to analyzing the lexicographic order of U changes when it becomes SUQ, so for now I iterate over all possible U.
Well, a few days later, I found a trick:

Let \( T_a=R_1\setminus R_0 \) and \( T_b=R_2\setminus R_1 \) be the sets of pieces that are solved by applying the first and second phases, respectively. We call these sets of pieces "target" regions.

For a scramble \( P \) over the entire board, we calculate the subscramble of \( P \) with pieces \( T=T_a||T_b \) as \( U=PT \). We use this value of \( T \) specifically and not just any arbitrary permutation of \( R_2\setminus R_0 \), for reasons that will become clear shortly:

Earlier, we defined \( Q \) as the permutation such that \( STQ=T \), and derived \( (SPS^{-1})T=SPS^{-1}STQ=S(PT)Q=SUQ \). In some cases, \( S \) will also keep the target regions \( T_a \) and \( T_b \) separated from each other, i.e. there exist \( Q_a,Q_b \) such that \( ST_aQ_a=T_a, ST_bQ_b=T_b \); we call such transformations \( S \) "friendly".

Then, since we defined \( T \) as \( T_a||T_b \), we have that \( STQ=T \rightarrow S(T_a||T_b)Q=T_a||T_b=(ST_aQ_a)||(ST_bQ_b) \), so \( TQ=(T_a||T_b)Q=(T_aQ_a)||(T_bQ_b) \). This also allows us to split the subscramble \( U \) into ( U_a,U_b \); \( U_a=PT_a, U_b=PT_b \).

Finally, we have \( U=U_a||U_b \), and for friendly \( S \) we have \( SUQ=SPTQ=SP((T_aQ_a)||(T_bQ_b))=(SPT_aQ_a)||(SPT_bQ_b)=(SU_aQ_a)||(SU_bQ_b) \).

The reason this fact is useful is because we currently perform symmetry reduction by only considering a subscramble \( U \) if it is a lexicographically minimum element in the set \( \{SUQ\}_{S\textrm{ rigid, } STQ=T} \). If \( S \) is friendly, then for \( U \) to be lexicographically not greater than \( SUQ=(SU_aQ_a)||(SU_bQ_b) \), \( U_a \) must be lexicographically not greater than \( SU_aQ_a \). Thus, when iterating over possible \( U \), we can restrict all \( U_a \) to be a lexicographically minimum element in the set \( \{SU_aQ_a\}_{S\textrm{ friendly, } ST_aQ_a=T_a} \).

For this 2-phase improvement, we reduce the number of possible \( U_a \) to consider by about 8 times, compared to my previous algorithm; we end up reducing the total time spent on symmetry reduction by maybe 5 times, according to some smaller test cases I ran (I'm still not sure why it is not 8 times). Even then, for this test case (proving a God's number of <= 22 for these two phases), we still spend about 40,000 seconds on symmetry reduction alone, which is over 40% of the total running time, so more improvements should be made.

NOTE (2022-04-17): By using a partial BFS + DFS program I mentioned in an earlier post, the following scramble takes at least 17 moves to solve, showing that with the current solving scheme of 6x6 Loopover we are using (i.e. 0x0->2x2->3x3->4x4->5x5->6x6, with some lattices being spaced out), the best upper bound on 6x6 GN we can obtain is 17+19+23+24=83:
Code:
0  .  12 .  24 .            0  .  2  .  4  .
.  .  .  .  .  .  solve to  .  .  .  .  .  .
2  .  14 .  26 .    --->    12 .  14 .  16 .
.  .  .  .  .  .            .  .  .  .  .  .
4  .  16 .  28 .            24 .  26 .  28 .
.  .  .  .  .  .            .  .  .  .  .  .
depth >= 17
https://gist.github.com/coolcomputery/059144327f7b8cc07b9361688e34d063

Currently, I am thinking of using a different solving scheme, such as 0x0->2x2->3x3->3x5->4x5->5x5->6x6 (with some lattices being spaced out), as this allows us to do practical 2-phase improvements in more places:
Code:
......       #.#...       #.#.#.
......       ......       ......
......  -->  #.#...  -->  #.#.#.
......       ......       ......
......       ......       #.#.#.
......       ......       ......
2-phase improvement
GN <= 22

#.#.#.       #####.       #####.
......       ......       #####.
#.#.#.  -->  #####.  -->  #####.
......       ......       ......
#.#.#.       #####.       #####.
......       ......       ......
2-phase improvement
GN <= 35
8289.403 seconds
https://gist.github.com/coolcomputery/16bed7efbf4951801345b7e9bb6ab91c#file-6x6_010101x010101-010101x000001-000101x000001_stdout-txt

#####.       #####.       ######
#####.       #####.       ######
#####.  -->  #####.  -->  ######
......       #####.       ######
#####.       #####.       ######
......       ......       ######
2-phase improvement
GN <= 37
4644.727 seconds
https://gist.github.com/coolcomputery/16bed7efbf4951801345b7e9bb6ab91c#file-6x6_000101x000001-000001x000001-000000x000000_stdout-txt
--------------------------------------------------------------------------------------------------------------------------------
(2022-04-23): 5x5 GN <= 17 (0x0 --> ACKM --> 3x3) + 26 (3x3 --> 4x4 --> 5x5) = 43.
Code:
###..       ####.       #####
###..       ####.       #####
###..  -->  ####.  -->  #####
.....       ####.       #####
.....       .....       #####
GN <= 26
113217.506 seconds
stdout: https://gist.github.com/coolcomputery/9033eee59e40446004c93de19516b945
--------------------------------------------------------------------------------------------------------------------------------
(2022-05-10): 5x5 GN <= 17 (0x0 --> ACKM --> 3x3) + 25 (3x3 --> 4x4 --> 5x5) = 42.
Code:
###..       ####.       #####
###..       ####.       #####
###..  -->  ####.  -->  #####
.....       ####.       #####
.....       .....       #####
GN <= 25
304814.840 seconds
stdout: https://gist.github.com/coolcomputery/6b4d6be5d26bb10f5ce74500083b5289
I found an even more powerful (and simpler) optimization to symmetry reduction: given scrambles \( U=U_a || U_b \) of the set of pieces we want to solve, and \( S U Q \) a transformed version of \( U \): if we only know what \( U_a \) is and not \( U_b \), we can fill in as many elements of \( S U Q \) that we can determine, then lexicographically compare \( U \) and \( S U Q \) by comparing corresponding elements until we reach an element of unknown value in either scramble. If we find \( U \) is lexicographically greater than \( S U Q \) even with incomplete knowledge of either scramble, then even if we know \( U_b \), \( U \) is still lex. greater than \( S U Q \), so this tactic allows us to better eliminate \( U_a \). This also removes the need to designate certain transformations \( (S,Q) \) as "friendly", since all transformations are treated the same.
 
Last edited:

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 86 = 24 (0x0->{1,3,13,15}->3x3) + 21 (3x3->4x4) + 20 (4x4->4x6) + 21 (4x6->6x6) (single-tile metric, as I have always used)

NEW TECHNIQUE: Allow transforming each state by a sequence of moves that temporarily disrupts an already solved region, but returns that region to its solved state at the end. Previous methods all required an already-solved region to never be broken up even temporarily, and only allowed transforming states by single-unit moves that individually do not touch the solved region, severely restricting tile movement as the solved region got bigger. This new technique is essentially Dijkstra('s) instead of BFS, since it allows applying multiple moves at once.
(It only took a 10-month break for me to think of this idea; the funny thing is that I had already known it and used it for Loopover NRG GN upper bounds about 20 months ago.)

Instead of breaking 4x4->6x6 into 4x4->5x5->6x6, I break it into 4x4->4x6->6x6, where the permutation counts of the phases are split more evenly (20!/12!+12! instead of 20!/11!+11!).

For 4x4->4x6, I allow transforming by "L-conjugations", or sequences of the form \( ABA^{-1} \), where \( A \) slides a single row or a single column an arbitrary amount of units (a "glide"), \( B \) is also a "glide", and \( A \) and \( B \) slide orthogonal parts of the board (one of them slides a row and the other slides a column; they cannot both slide rows or both slide columns). Furthermore, \( A \) must disrupt the top-left 4x4 solved region (otherwise the L-conjugation could be obtained by composing single-unit moves that never break the 4x4 block, not even temporarily).

For 4x6->6x6, I allow conjugations \( ABA^{-1} \) where this time \( A \) slides an arbitrary subset of columns 1 unit all in the same direction (all up or all down), and \( B \) slides a single row.

The code for Dijkstra's takes in the start region that is already solved, the target end region that should be solved next, and an arbitrary list of sequences of moves. All sequences of moves that disrupt the start region are automatically ignored, and sequences that create duplicate permutation actions on the entire board are discarded.

Source code (two versions, one for each phase) and stdout: https://gist.github.com/coolcomputery/e0204bc48abda3ff3ee9877aa808e7ca

4x4->4x6: 49295.192 seconds
0: 1
1: 4
2: 16
3: 90
4: 492
5: 2474
6: 12259
7: 59574
8: 283163
9: 1300242
10: 5666906
11: 22913610
12: 82863149
13: 254076682
14: 621818069
15: 1141541684
16: 1437263840
17: 1090325622
18: 390839599
19: 30045083
20: 97841

4x6->6x6: 19111.965 seconds
0: 1
1: 4
2: 8
3: 34
4: 224
5: 892
6: 2965
7: 11110
8: 44124
9: 159060
10: 541924
11: 1801924
12: 5901323
13: 17132692
14: 44359213
15: 96249480
16: 141263572
17: 119398514
18: 47277902
19: 4745530
20: 109544
21: 1560

The solving phase 0x0->{1,3,7,9}->3x3 (GN<=24) was a 2-opt obtained a while ago. The phase 3x3->4x4 with GN<=21 was obtained with a plain BFS (old technique); I'll work on using Dijkstra's for this phase in the meantime.

Sidenote: there is an even more powerful solving technique, which is to allow the start region of a phase to only be partially solved throughout the entire phase, until the very end. Compared to Dijkstra's, this means we are not forced to always restore the solved region at the end of every move sequence we apply to a state. xyzzy used this technique on the 5x5 board to bound the GN of 0x0->2x3->3x3 to 22, by allowing the 2x3 region to be any permutation within 5 units (in single-tile metric) of being solved while extending it to a 3x3. A month ago I also tried this same technique to improve 5x5 and 6x6 GN bounds. The issue is that this technique requires far more memory than the old BFS or Dijkstra's (which both use the same amount of memory), because now every state needs to encode the configuration of the start region in addition to the tiles that are to be added to the start region, so for now I have abandoned it.

2023-03-27: Currently I haven't been able to solve this specific scramble (expanding a 3x3 to a 4x4) in under 21 moves:
Code:
(using the same numbering scheme as https://loopover.xyz/: tiles are numbered 1-36 in row-major order)
  X  X  X  . 19  4
  X  X  X  .  .  .
  X  X  X  . 22 16
  .  .  .  .  .  .
  . 20  .  .  .  .
 21  . 10  .  .  .
 
Last edited:

Arcanist

Member
Joined
Jun 18, 2022
Messages
1,160
Location
Looking for my lost Weight 5.
Summary of current knowledge (2022-04-17):

STM:
4×4: 18 (by rokicki)
5×5: ≤44 (by coolcomputery)
6×6: ≤88 (by coolcomputery)
(plus some small rectangular sizes by rokicki)
m×n: \( O(N\log^2N) \) where \( N=mn \); ≥\( \lfloor m/2\rfloor n+m\lfloor n/2\rfloor \) (from considering Manhattan distance)
2×n: \( \le n(\log_2n+20) \)

MTM:
4×4: 14 (by rokicki)
(plus some small rectangular sizes by rokicki)
m×n: Θ(mn) (from counting arguments)

---

Loopover = this game; STM = single-tile metric (the one Loopover implementations use to count moves); MTM = multi-tile metric (a seemingly more sensible choice of metric).

STM bound of 26 moves is one move less than the best I could find (27 according to this spreadsheet); MTM bound has not been previously calculated before, as far as I can tell, although chances are that I'm just not aware of it. This puzzle has "only" 21 trillion states and we can get 128-fold symmetry+antisymmetry reduction, so in theory it shouldn't be too hard to BFS the whole thing. (I did also recently get a new 4 TB hard drive…) The solving procedure is essentially: solve a bunch of pieces optimally, then solve the remaining pieces also optimally. The second part is something that earlier work did not do, which is why we can get an immediate one-move improvement.

(I might bother to do a more sophisticated analysis later on; there's still a lot of low-hanging fruit left to pick.)

Solving the top two rows optimally takes at most 10 MTM, 13 STM.
(0, 1)
(1, 18)
(2, 255)
(3, 3648)
(4, 48787)
(5, 605886)
(6, 6632955)
(7, 56497090)
(8, 253413670)
(9, 199503998)
(10, 2212092)

(nice formatting wew)
total states: 518918400
distance 0: 1 nodes
distance 1: 12 nodes
distance 2: 114 nodes
distance 3: 1084 nodes
distance 4: 9931 nodes
distance 5: 86036 nodes
distance 6: 703024 nodes
distance 7: 5240586 nodes
distance 8: 32884017 nodes
distance 9: 142199734 nodes
distance 10: 258379100 nodes
distance 11: 78645932 nodes
distance 12: 768545 nodes
distance 13: 284 nodes
average distance: 9.717073

Solving the bottom two rows optimally once the top two rows are solved takes at most 11 MTM, 13 STM. Note that almost all of the optimal solutions here temporarily destroy the initially solved rows before finally restoring them (because there are no free columns at all), with the only exceptions being the solutions for the sixteen states that can be solved by moving just the two free rows.
Code:
move count stats:
 0:         1
 1:         6
 2:         9
 3:        24
 4:       288
 5:      1132
 6:      1340
 7:      8936
 8:     16721
 9:      8992
10:      2703
11:       168
Code:
 0:         1
 1:         4
 2:         6
 3:        20
 4:       137
 5:       428
 6:       934
 7:      3172
 8:      8410
 9:     11024
10:      9792
11:      5276
12:       880
13:       236

From these, we conclude an upper bound of 21 MTM and 26 STM.

Alternatively (for STM), following earlier work, it is known that solving a 3×3 block takes at most 13 STM; running the optimal solver on the 7! = 5040 possible permutations of the last side last layer leads to a maximum of 13 STM as well, so we have a total of 26 STM.
Code:
move count stats:
 0:         1
 1:         4
 2:        10
 3:        24
 4:        58
 5:       140
 6:       334
 7:       726
 8:      1258
 9:      1442
10:       829
11:       176
12:        30
13:         8

Similarly, solving a 3×2 block takes at most 11 STM; running the optimal solver on the 10! = 3628800 permutations of the last ten pieces leads to a maximum of 15 STM, again a total of 26 STM.
Code:
move count stats:
 0:         1
 1:         6
 2:        23
 3:        96
 4:       451
 5:      1996
 6:      8370
 7:     33748
 8:    125081
 9:    397755
10:    927554
11:   1230082
12:    748542
13:    150702
14:      4378
15:        15

The solver I coded for this doesn't "truly" exploit much of the inherent symmetry of the puzzle. The puzzle state is stored as a 64-bit integer with four bits for each cell, rather than as a permutation coordinate; this allows for switching the top and bottom halves of the puzzle just by doing a bit rotation and xor-ing by a constant. Only one pruning table is used (solving the top eight pieces); this pruning table is stored very inefficiently by using a 32-bit index, but that's fine, because I have 2 GB RAM to spare and it's only one pruning table. This pruning table is applied to the puzzle state itself, a shifted version of the puzzle state (solving the bottom two rows instead of the top two rows, effectively), as well as doing those two things to the inverse state as well to increase average pruning depth.

When solving the last two rows in MTM, this managed to do about 3500 solves per second, with all 8! = 40320 cases being solved in 11.65 seconds.

The solver has not been thoroughly tested for correctness (I literally just wrote it yesterday and haven't reviewed it), but there is a failsafe check to ensure that the generated solutions really do solve the input puzzle state. In other words, if there's a bug, at worst it just means that the solutions are not optimal, as opposed to being completely wrong. Thus this will not affect the correctness of the upper bounds in the rest of this post. (Unless there's a bug in the checking code…)

I tried doing the thing where the solver switches to the inverse scramble opportunistically (like this) but it ended up being 40% slower than just doing regular IDA* (because of branch mispredicts?). Maybe I just didn't implement it right, idk.

========

Update (2019-09-10): STM bound has been reduced to 25 STM.

Each of the 284 eight-piece cosets that are 13 moves away from solved have the eight pieces ABCDEFGH in the opposite half of the board, e.g.

Code:
P O M N
K L J I
G H E F
C D B A

(For this specific board, it takes 13 moves to solve either ABCDEFGH or IJKLMNOP, and 17 moves to solve the whole thing.) Note that there are four different partitions into 2×4 blocks we can consider:

Code:
X X X X
X X X X
O O O O
O O O O

X X X X
O O O O
O O O O
X X X X

X X O O
X X O O
X X O O
X X O O

X O O X
X O O X
X O O X
X O O X

The only way a piece can be in the opposite block of its home position under all four of these partitions simultaneously is if it's at the antipodal position, i.e.

Code:
K L I J
O P M N
C D A B
G H E F

But it takes only 12 moves to solve ABCDEFGH on this board (shift the bottom two rows by two cells (4 moves), then shift every column by two cells (8 moves)). Thus there is no state that is in a 13-move eight-piece coset under all four partitions simultaneously, and it always takes at most 12 moves to solve some 2×4 block (although solving a specific block may sometimes take 13 moves). This leads to a total upper bound of 12 + 13 = 25 STM.

========

TL note: "future" probably means like in the rest of the week, depending.

Consider the asymptotic behaviour of GN in the single-tile and multi-tile metrics. In the latter, a counting argument shows that it is bounded below by Ω(n^2) and a 3-cycle method shows that it is bounded above by O(n^2), so god's number in MTM is necessarily Θ(n^2). The former seems to be a lot more complicated. Again, a counting argument gives a lower bound of Ω(n^2), but the 3-cycle method gives an upper bound of O(n^3). I think I have a way of bringing the upper bound down to something like O(n^2 (log n)^4) but I haven't worked out the details (so the exponent of the log factor is probably wrong); I'm pretty sure the actual asymptotic behaviour is Θ(n^2), but I can't figure out how to prove that.

As for a lower bound, there are two basic approaches to consider. As mentioned above, we have a counting argument leading to a lower bound of cn^2 + o(n^2) for some constant c ≥ 2, but for small sizes we can also consider a bound given by Manhattan distance. As the sides wrap around (or should I say, they loop over), the maximum possible distance in either axis is ⌊n/2⌋, so the maximum possible Manhattan distance for each piece is 2⌊n/2⌋. Each move affects n pieces, the Manhattan distances of which change by at most ±1; hence the maximum possible change in the sum of Manhattan distances is ±n. The sum of Manhattan distances for a whole board is bounded by 2⌊n/2⌋ × n^2, so this gives a GN lower bound of 2⌊n/2⌋ × n. One example of a board hitting this bound is by shifting all of the rows by half of the board size, then shifting all of the columns by half of the board size. (If n is odd, it doesn't matter whether we round down or round up.)

In particular, this gives a lower bound of 36 for 6×6, which is better than the counting bound of 31, at least according to the formula in the Loopover Research spreadsheet. (I haven't verified it, but it seems roughly correct.)
I didn't understand it at all but liked the post bc it looked high effort.
 

coolcomputery

Member
Joined
Nov 21, 2019
Messages
26
YouTube
Visit Channel
6x6 GN is at most 85 = 24 (0x0->{1,3,13,15}->3x3) + 20 (3x3->4x4) + 20 (4x4->4x6) + 21 (4x6->6x6).

For 3x3->4x4, I allow single-moves that do not disrupt the 3x3 region, as well as all "syllable conjugations" \( ABA^{-1} \) where \( A \) and \( B \) are each syllables of move-count at most 2. A syllable is a sequence of either all row moves or all column moves (with no mixing of rows and columns allowed).

By adding the condition that the \( A \) part of every conjugation must disrupt the 3x3 region, we have 1260 move sequences, so thus 1260 transitions that can be done on each of the \( 27!/20! = 4475671200 \) states. Running Dijkstra's would take quite a long time, so instead I use a different SSSP (single-course shortest paths) algorithm that does DP (dynamic programming) on each (state, distance) pair (rather than something like each (state, edge count) pair like what Bellman-Ford does, which Dijkstra's is sort of a super optimized version of (Dijkstra's can be viewed as DP)).

Source code + stdout: https://gist.github.com/coolcomputery/49f9d579e80044824bbc30593bbe8635

3x3->4x4: 40864.908 seconds
0:1
1:4
2:20
3:129
4:754
5:4038
6:21094
7:106159
8:510034
9:2319261
10:9859651
11:38429865
12:132335913
13:378171435
14:821654445
15:1232821035
16:1152840978
17:574622292
18:124010567
19:7911451
20:52074

In the meantime I'll work on improving the 4x4->4x6 bound.

Explanation of SSSP:
We will be working over an undirected graph. Let \( s_0 \) denote the source vertex (the solved state), \( N(v) \) denote the set of vertices that are adjacent to \( v \), and \( c(u,v) \) denote the weight of edge \( (u,v) \). All weights are small positive integers.

Our DP is \( p(v,d):=(\textrm{there is a path from } s_0 \textrm{ to } v \textrm{ of total weight exactly } d) \) (returns a boolean). We have the base cases \( p(v,d)=\texttt{false}\ \forall d<0 \) and \( p(v,0)=(v=s_0) \), and the recursion \( p(v,d)=\textrm{OR}_{u\in N(v)} p(u,d-c(u,v)) \). (We can derive this by fixing the last edge of an arbitrary path from \( s_0 \) to \( v \).)

A naive SSSP algorithm using this DP would calculate \( p(v,d) \) for all \( v \), for each \( d=1,2,3,\dots \), requiring \( O(V+E) \) work for each value \( d \), where \( V \) and \( E \) are the number of vertices and edges in the graph respectively. We would also have to specify when to stop incrementing \( d \).

However, for each vertex \( v \), we are only interested in the smallest \( d \) s.t. \( p(v,d)=\texttt{true} \), i.e. if \( p(v,d)=\texttt{true} \) we don't care about evaluating \( p(v,d') \) for any \( d'>d \).

Let us fix \( d \) and define \( r(v)=(\textrm{min } {l<d} \textrm{ s.t. } p(v,l)=\texttt{true} \textrm{, or } \infty \textrm{ if such } l \textrm{ does not exist}) \). We only want to evaluate \( p(v,d) \) if \( p(v,l)=\texttt{false}\ \forall l<d \); under this condition, we can show that \( p(v,d)=(\exists u\in N(v) \textrm{ s.t. } r(u)+c(u,v)=d) \).

Proof: let \( A:=\vee_{u\in N(v)} p(u,d-c(u,v)) \) and \( B:=(\exists {u\in N(v)} \textrm{ s.t. } r(u)+c(u,v)=d) \).
If \( B \) is true, then \( \exists u\in N(v) \textrm{ s.t. } r(u)=d-c(u,v) \Rightarrow p(u,r(u))=\textrm{true}=p(u,d-c(u,v)) \), so \( A \) is true.
If \( A \) is true, then \( \exists u\in N(v) \textrm{ s.t. } p(u,d-c(u,v))=\texttt{true} \); letting \( d'=d-c(u,v) \), all \( p(u,l) \) must equal \( \texttt{false} \) for all \( l<d' \) (otherwise \( p(u,l)=\texttt{true} \Rightarrow p(v,l+c(u,v))=\texttt{true}, \textrm{ but } l+c(u,v)<d \textrm{; contradiction} \)), so we must have \( r(u)=d' \), implying \( r(u)+c(u,v)=d \Rightarrow A \).

This result gives us an alternative method of calculating all \( p(v,d) \) for a fixed \( d \): initialize all \( p(v,d) \) to \( \texttt{false} \); for each \( u,v \) s.t. \( r(u)+c(u,v)=d \), set \( p(v,d) \) to \( \texttt{true} \). This also shows that if there is no such pair \( (u,v) \) s.t. \( r(u)+c(u,v)\ge d \), then there is no point in incrementing \( d \) further and we can stop, so our algorithm will terminate. Finally, we can update \( r(v) \) in-place and avoid having to actually store \( p(v,d) \) explicitly.
 
Last edited:
Top