Add CITATION.cff

[tniessen]

Hi @dwalton76, is there any chance you could add a CITATION.cff file to the repository? I have not found any other open-source tools that provide even remotely similar capabilities for almost arbitrarily large Rubik's cubes. This file would be useful for referencing your tool in writing.

[dwalton76]

@tniessen yep I can do that. If you end up citing the solver can you let me know? I am just curious as to where it will end up being cited from :)

[dwalton76]

I wasn't sure about the doi section so left that out https://github.com/dwalton76/rubiks-cube-NxNxN-solver/blob/master/CITATION.cff

[tniessen]

Thank you @dwalton76! I hope it won't disappoint you, I am using it for a part of a Master's thesis on the difficulty of some problems related to Rubik's cube groups.

The table in the README seems like you made some "recent" improvements to the reduction that decreased the number of turns required, which is a difficult task! Did you ever calculate the upper bounds for the number of moves to reduce NxNxN to 3x3x3? Algorithms for solving the Rubik's cube have often been a useful source for upper bounds on "God's number" (diameter of the Rubik's cube group), and the currently known bounds for NxNxN are anything but tight to the best of my knowledge. For example, a reduction from 5x5x5 to 3x3x3 in no more than 110 OBTM turns would mean an upper bound of 110 (reduction) + 20 (solving), which would be better than any upper bound I am aware of.

[dwalton76]

I haven't computed an upper bound for each of the phases used to reduce a NxNxN cube to a 3x3x3. Most of the phases are solved via IDA* and have a huuuuuge number of states...so it wouldn't be feasible to build out all of the states for each phase to get the worst case number of moves for each phase :(

I have done a little god's number research though. For 4x4x4 and 5x5x5 I wrote a gods-number-bound.py) tool that computes a lower bound on what the god number could be. This is without reducing to 3x3x3 though. Basically at depth one you can reach 36 states and then after that 33 states for each depth.

The number of 4x4x4 states is 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000 so the following shows us that god's number for it has to be at least 31.

                                                        This Depth
===  =============================================================
01:                                                             36
02:                                                          1,188
03:                                                         39,204
04:                                                      1,293,732
05:                                                     42,693,156
06:                                                  1,408,874,148
07:                                                 46,492,846,884
08:                                              1,534,263,947,172
09:                                             50,630,710,256,676
10:                                          1,670,813,438,470,308
11:                                         55,136,843,469,520,164
12:                                      1,819,515,834,494,165,412
13:                                     60,044,022,538,307,458,596
14:                                  1,981,452,743,764,146,133,668
15:                                 65,387,940,544,216,822,411,044
16:                              2,157,802,037,959,155,139,564,452
17:                             71,207,467,252,652,119,605,626,916
18:                          2,349,846,419,337,519,946,985,688,228
19:                         77,544,931,838,138,158,250,527,711,524
20:                      2,558,982,750,658,559,222,267,414,480,292
21:                     84,446,430,771,732,454,334,824,677,849,636
22:                  2,786,732,215,467,170,993,049,214,369,037,988
23:                 91,962,163,110,416,642,770,624,074,178,253,604
24:              3,034,751,382,643,749,211,430,594,447,882,368,932
25:            100,146,795,627,243,723,977,209,616,780,118,174,756
26:          3,304,844,255,699,042,891,247,917,353,743,899,766,948
27:        109,059,860,438,068,415,411,181,272,673,548,692,309,284
28:      3,598,975,394,456,257,708,568,981,998,227,106,846,206,372
29:    118,766,188,017,056,504,382,776,405,941,494,525,924,810,276
30:  3,919,284,204,562,864,644,631,621,396,069,319,355,518,739,108
31:  3,359,435,005,609,447,705,097,734,409,802,088,750,621,300,296

The number of 5x5x5 states is 282,870,942,277,741,856,536,180,333,107,150,328,293,127,731,985,672,134,721,536,000,000 so the following shows us that god's number for it has to be at least 44.

                                                                                   This Depth
===  ========================================================================================
01:                                                                                        36
02:                                                                                     1,188
03:                                                                                    39,204
04:                                                                                 1,293,732
05:                                                                                42,693,156
06:                                                                             1,408,874,148
07:                                                                            46,492,846,884
08:                                                                         1,534,263,947,172
09:                                                                        50,630,710,256,676
10:                                                                     1,670,813,438,470,308
11:                                                                    55,136,843,469,520,164
12:                                                                 1,819,515,834,494,165,412
13:                                                                60,044,022,538,307,458,596
14:                                                             1,981,452,743,764,146,133,668
15:                                                            65,387,940,544,216,822,411,044
16:                                                         2,157,802,037,959,155,139,564,452
17:                                                        71,207,467,252,652,119,605,626,916
18:                                                     2,349,846,419,337,519,946,985,688,228
19:                                                    77,544,931,838,138,158,250,527,711,524
20:                                                 2,558,982,750,658,559,222,267,414,480,292
21:                                                84,446,430,771,732,454,334,824,677,849,636
22:                                             2,786,732,215,467,170,993,049,214,369,037,988
23:                                            91,962,163,110,416,642,770,624,074,178,253,604
24:                                         3,034,751,382,643,749,211,430,594,447,882,368,932
25:                                       100,146,795,627,243,723,977,209,616,780,118,174,756
26:                                     3,304,844,255,699,042,891,247,917,353,743,899,766,948
27:                                   109,059,860,438,068,415,411,181,272,673,548,692,309,284
28:                                 3,598,975,394,456,257,708,568,981,998,227,106,846,206,372
29:                               118,766,188,017,056,504,382,776,405,941,494,525,924,810,276
30:                             3,919,284,204,562,864,644,631,621,396,069,319,355,518,739,108
31:                           129,336,378,750,574,533,272,843,506,070,287,538,732,118,390,564
32:                         4,268,100,498,768,959,598,003,835,700,319,488,778,159,906,888,612
33:                       140,847,316,459,375,666,734,126,578,110,543,129,679,276,927,324,196
34:                     4,647,961,443,159,397,002,226,177,077,647,923,279,416,138,601,698,468
35:                   153,382,727,624,260,101,073,463,843,562,381,468,220,732,573,856,049,444
36:                 5,061,630,011,600,583,335,424,306,837,558,588,451,284,174,937,249,631,652
37:               167,033,790,382,819,250,069,002,125,639,433,418,892,377,772,929,237,844,516
38:             5,512,115,082,633,035,252,277,070,146,101,302,823,448,466,506,664,848,869,028
39:           181,899,797,726,890,163,325,143,314,821,342,993,173,799,394,719,940,012,677,924
40:         6,002,693,324,987,375,389,729,729,389,104,318,774,735,380,025,758,020,418,371,492
41:       198,088,879,724,583,387,861,081,069,840,442,519,566,267,540,850,014,673,806,259,236
42:     6,536,933,030,911,251,799,415,675,304,734,603,145,686,828,848,050,484,235,606,554,788
43:   215,718,790,020,071,309,380,717,285,056,241,903,807,665,351,985,665,979,775,016,308,004
44:    60,410,940,069,543,318,737,315,632,892,900,864,991,472,837,750,454,093,078,550,432,372

[dwalton76]

Add a CITATION.cff via https://github.com/dwalton76/rubiks-cube-NxNxN-solver/pull/76

[tniessen]

Hey @dwalton76, so sorry for never getting back to you despite your great analysis! I really appreciate the time you put into it even though it did not lead to new results in my case! Also, the solver itself works amazingly well.