Self-taught AI solves Rubik's cube

[petero2]

Can it beat this guy though who solves 17x17x17 cube in about 2 hours ? https://www.youtube.com/watch?v=7ChuKKL2PpU

I would like to understand what makes it a unique challenge. From what I understood from the abstract

- single goal state
- solved in reverse with root node being that single goal state (i.e. solved state)
- finds shortest path 60% of the time

Please add more if you read the full paper.

They want $32 for the full pdf, but you can read the first page here:

https://www.nature.com/articles/s42256- ... rer=nature

I did not buy the paper, but from reading the first page:

- They use weighted A* search.
- They use something called "deep approximate value iteration" to train the heuristic function used by the A* algorithm.

In regular value iteration you use a big lookup table and compute the table values by iterating the Bellman equation. (In deterministic cases, like when computing tablebases, you don't even have to iterate more than once if you compute the values in the table in a suitable order.)

If the state space it too big (like for the 3x3x3 cube) you cannot store the whole table. Therefore they instead use "deep approximate value iteration", which means they use a deep neural network as an approximation to the lookup table. The training attempts to minimize the mean squared residual from the Bellman equation. Presumably the mean is taken over the states encountered by starting from the goal position and performing random walks of progressively increasing length.

If you have a complete table you don't need to perform any search to find the solution (like for a tablebase), but since they only have an approximation they use weighted A* to find an actual solution.

Can it beat this guy though who solves 17x17x17 cube in about 2 hours ? https://www.youtube.com/watch?v=7ChuKKL2PpU

Fake , reversed video

Maybe the fake claim was a joke, but it is clear to me that the video is not reversed. It is not really algorithmically harder to solve a large cube than say a 5x5x5 or a 4x4x4 cube, even though it is practically much harder since it requires many more moves and each move is physically more challenging to perform.

If you take a solved cube and randomly shuffle it, then reverse the video, when you look at the video it would appear that you are making random moves that magically in the end causes the cube to be solved. In contrast, in this video the guy is gradually putting pieces into the right positions and also explains what he is doing while he is doing it.

It would be very interesting to know if their algorithm could actually be trained to learn how to solve a 17x17x17 cube. The state space is very large. Just the inner pieces can be arranged in (24!/4!^6)^56 ~= 10^868 ways. My guess is that their algorithm cannot solve 17x17x17 cubes, or else they probably would have mentioned larger cubes in the abstract.

[Michel]

Maybe this link works?

https://www.nature.com/articles/s42256- ... izmodo.com

[Ovyron]

Can it beat this guy though who solves 17x17x17 cube in about 2 hours ? https://www.youtube.com/watch?v=7ChuKKL2PpU

Fake , reversed video

Maybe the fake claim was a joke, but it is clear to me that the video is not reversed.

Yeah, it was a joke people kept posting on the video, as a "plot twist" (for people that just finished watching the whole thing and go to read the comments, making them doubt if what they saw was real), but the video is real.

[Daniel Shawul]

Thanks Peter.

I did not buy the paper, but from reading the first page:

- They use weighted A* search.
- They use something called "deep approximate value iteration" to train the heuristic function used by the A* algorithm.

In regular value iteration you use a big lookup table and compute the table values by iterating the Bellman equation. (In deterministic cases, like when computing tablebases, you don't even have to iterate more than once if you compute the values in the table in a suitable order.)

If the state space it too big (like for the 3x3x3 cube) you cannot store the whole table. Therefore they instead use "deep approximate value iteration",

Ok so they use value iteration instead of policy iteration. According to David Silver's RL lecture, it is kind of surprizing that they chose that. Wouldn't policy iteration or even actor-critic have been better? but maybe the fact that they are interested in the shortest path has a role in that. Anyway now that we have access to the full paper I will try to go through it and understand better.

Maybe the fake claim was a joke, but it is clear to me that the video is not reversed. It is not really algorithmically harder to solve a large cube than say a 5x5x5 or a 4x4x4 cube, even though it is practically much harder since it requires many more moves and each move is physically more challenging to perform.

The guy is also a 3 time rubik's cube world champ...
My thought when i pointed that video was that the 17x17x17 cube could be intractable problem for them.

Daniel

[chrisw]

Can it beat this guy though who solves 17x17x17 cube in about 2 hours ? https://www.youtube.com/watch?v=7ChuKKL2PpU

I would like to understand what makes it a unique challenge. From what I understood from the abstract

- single goal state
- solved in reverse with root node being that single goal state (i.e. solved state)
- finds shortest path 60% of the time

Please add more if you read the full paper.

They want $32 for the full pdf, but you can read the first page here:

https://www.nature.com/articles/s42256- ... rer=nature

I did not buy the paper, but from reading the first page:

- They use weighted A* search.
- They use something called "deep approximate value iteration" to train the heuristic function used by the A* algorithm.

In regular value iteration you use a big lookup table and compute the table values by iterating the Bellman equation. (In deterministic cases, like when computing tablebases, you don't even have to iterate more than once if you compute the values in the table in a suitable order.)

If the state space it too big (like for the 3x3x3 cube) you cannot store the whole table. Therefore they instead use "deep approximate value iteration", which means they use a deep neural network as an approximation to the lookup table. The training attempts to minimize the mean squared residual from the Bellman equation. Presumably the mean is taken over the states encountered by starting from the goal position and performing random walks of progressively increasing length.

If you have a complete table you don't need to perform any search to find the solution (like for a tablebase), but since they only have an approximation they use weighted A* to find an actual solution.

Can it beat this guy though who solves 17x17x17 cube in about 2 hours ? https://www.youtube.com/watch?v=7ChuKKL2PpU

Fake , reversed video

Maybe the fake claim was a joke, but it is clear to me that the video is not reversed. It is not really algorithmically harder to solve a large cube than say a 5x5x5 or a 4x4x4 cube, even though it is practically much harder since it requires many more moves and each move is physically more challenging to perform.

If you take a solved cube and randomly shuffle it, then reverse the video, when you look at the video it would appear that you are making random moves that magically in the end causes the cube to be solved. In contrast, in this video the guy is gradually putting pieces into the right positions and also explains what he is doing while he is doing it.

It would be very interesting to know if their algorithm could actually be trained to learn how to solve a 17x17x17 cube. The state space is very large. Just the inner pieces can be arranged in (24!/4!^6)^56 ~= 10^868 ways. My guess is that their algorithm cannot solve 17x17x17 cubes, or else they probably would have mentioned larger cubes in the abstract.

What a neat idea. Wish I’ld thought of that. Simple and obvious (once somebody told you, of course). Although, does random stepping back from the start actually only work because Rubik cube has the property that any position is never more than N moves from solution, forget what N is, might be 17, or anyway some manageable number, so the backtracked random positions are going to form a subset of all possible positions, just as long as the backtracker goes to -N depth? If so, highly tractable for a net.
Like everybody, I only read page one. I guess no policy because move ordering for the solving algorithm can be found by a depth one sort on value.

[Ajedrecista]

Hello Peter:

[...]

It would be very interesting to know if their algorithm could actually be trained to learn how to solve a 17x17x17 cube. The state space is very large. Just the inner pieces can be arranged in (24!/4!^6)^56 ~= 10^868 ways. My guess is that their algorithm cannot solve 17x17x17 cubes, or else they probably would have mentioned larger cubes in the abstract.

I googled the state space of a n x n x n Rubik's cube and I found the following formula that works for n = {2, 3, 4, 5, 6, 7, 8} when compared with the values given in Wikipedia:

Number of Permutations to the Rubik's Cube and variations

Formula

Code: Select all

Permutations(n) = a(n) * b * c(n) / d(n)

a(n) = [ 24 * ( 2^10 ) * 12! ]^( n mod 2 )
b    = 7! * 3^6
c(n) = (24!)^int[ ( n^2 - 2*n ) / 4 ]
d(n) = (4!)^{ 6 * int[ (n - 2)^2) / 4 ] }

c(2) = d(2) = c(3) = d(3) = 1

n even: a(n) = a(2) = 1
Permutations(2) = b = 3674160 = 3.67416e+6
Permutations(n) = b * c(n) / d(n) = Permutations(2) * c(n) / d(n)

n odd: a(n) = a(3)
Permutations(3) = a(3) * b = 43252003274489856000 ~ 4.3252e+19
Permutations(n) = a(3) * b * c(3) / d(3) = Permutations(3) * c(n) / d(n)

We can split odd and even sizes of the cubes to get the number of permutations of a generic n x n x n Rubik's cube.

Taking the powers of c(n) and d(n) just for simplifying my task:

Code: Select all

n even:
Permutations(n) = Permutations(2) * { (24!)^[ Power of c(n) ] } / { (4!)^[ Power of d(n) ] }

n odd: 
Permutations(n) = Permutations(3) * { (24!)^[ Power of c(n) ] } / { (4!)^[ Power of d(n) ] }

************************

 n    Power of c(n)    Power of d(n)
------------------------------------
 9          15               72
10          20               96
11          24              120
12          30              150
13          35              180
14          42              216
15          48              252
16          56              294
17          63              336
18          72              384
19          80              432
20          90              486
21          99              540
22         110              600
23         120              660
24         132              726
25         143              792
26         156              864
27         168              936
28         182             1014
29         195             1092
30         210             1176
31         224             1260
32         240             1350
33         255             1440

Here is my try of getting approximate values of permutations for n > 8 up to n = 33:

Code: Select all

 n     Permutations(n)
-----------------------
 9    1.417039239e+ 277
10    8.298359851e+ 349
11    1.085408718e+ 425
12    2.063677898e+ 513
13    8.763572317e+ 603
14    5.409635480e+ 707
15    7.458396779e+ 813
16    1.494756775e+ 933
17    6.690926087e+1054
18    4.353609772e+1189
19    6.327081385e+1326
20    1.336610620e+1477
21    6.306625595e+1629
22    4.325504376e+1795
23    6.626239317e+1963
24    1.475519806e+2145
25    7.338606900e+2328
26    5.305542177e+2525
27    8.567153977e+2724
28    2.010902151e+2937
29    1.054231430e+3152
30    8.033939300e+3379
31    1.367451043e+3610
32    3.383316238e+3853
33    1.869666101e+4099

Here are the full numbers outputted by Derive 6, just for curiosity. I do not know if they are affected by roundings or truncations:

Code: Select all

Permutations( 9) = 14170392390542612915246393916889970752732946384514830589276833655387444667609821068034079045039617216635075219765012566330942990302517903971787699783519265329288048603083134861573075573092224082416866010882486829056000000000000000000000000000000000000000000000000000000000000000

Permutations(10) = 82983598512782362708769381780036344745129162094677382883567691311764021348095163778336143207042993152056079271030423741110902768732457008486832096777758106509177169197894747758859723340177608764906985646389382047319811227549112086753524742719830990076805422479380054016000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(11) = 108540871852024137837529457366425345163408989164877909166491842616641991981135011689476695849803941790591401795168969498249897355324768178088518513156026831828793854471326717801604260274446021846541136205357444802749291495386649979610567642710417177711042509688835903368099465519253326878312637499376794203125671816898434564096000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(12) = 2063677898073844357646603197920258890170251516001026118673112483084767850393828353326267972195239544010571248411395616172020455363649849669977863241275268603219332908478121536195085624157051871749415170088220755319274751767818004538485698048613912743246651729135224151386255264736960175481003145164862918479835984636082724967833771274686319930813336734786441266125304166923015534386086055772160000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(13) = 8763572317083138899666771506115448810197988548417152607403264125553225032193212273441405302436314766538801856031356263342723209131492152513934956377943679818337540924470803427841954840974498164317911513147720460230834431517038890897934643613854843859025199191195215176116490497193888533584558263178669850587892778108968904539149570097514125281329326317330500078663925608728704612920139592231421618737966492537338284916915238170408357616663717846089475949173145600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(14) = 540963548099812666682933820527371848034397299421159424155049590163050476068411636535753418151164087747335175625856384218966484021303366183282419501905855736853129473336748334480865044041590895574268088789869745129254462038071324999531694426075100409916615749865129695263458102688963609061584210944262593991636265113756737626636978724934112730782655392014271667104603281109817916292819714983182178040688577343546599157272742343832041118953722678322816449671581689289561473448113662507616149879108855419077298200781492692561885118925750927360000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(15) = 7458396779708914399425703424116428588832669775752912370331684693369552940936002999126419866022131401045934887294375013092109622335952478838389027104290711132448969727122441678941052163978862594762790181083035319196609052418751078592189097318460186014599900718903209613204379177819729462504582471874698725199732220796504701056631175244762504854686369655885308344125859107085280675481055993855307589841962823074878304639609343164431854493410692438084432769446250326070453862500623641227363674043716151846135279426442745301496784381488845178240503146120522611965387229363546314220394932267259946495225551643409129182068736000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(16) = 1494756775484575297753089729413794634791916035636475493712183081618142243652069545607472411595576163073143103050802893067905282157930889905680707881792811601459409766808061818780264883466071023592279154123338318364222758431439965470576759247898341697338281615273378546496796277688929975190185145871528657892009361487826883579195951445593496863998291956073907197989950354147862931797214678168487704714695347611201877632467925715016858205344890707038502927677885168351947460535736682305317463268808791071993752714376704640824592884220205647933275026287167802970559950700260331647366263481659929804845720067720979424197975670125801503116765942873528835639144099277862126068895763613128938170718964084701214539776000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(17) = 66909260871052009626140831457599196711140812269154070729060136529449625780211961895693820570513604163602868942801633627363413148772664738570971988412147490850469267091069898537146037768890069934919884249763818629080668367898685033459370133844075322446474048403397592421266564641031053781182835951043902666703934718275733629773072428119603386280810232743294106725017906015726602505404809355600713515400760343408510054774806467063695824637124911945446317465833055520836975861238244940397333234336971270687092383804133631886114309853819332336282986834777948178464656888802372250927074981140246608824577036094710201099095240641256513217598802423874027822421584587650039125516202912205481540427864199947576722221866866102507350876922115628881880203115212216766503665426445956786264399133302962649600884736000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(18) = 43536097720265280144278194878456326811181709316079829737335494040106652650057074276349562045700106412909473588642781800894420766696582002175516044109410186954218602761162211673894258378158944262518050356603847979272240857550969602112475608283781623642180365635807711948010025177466502769206311590447701992732464035932435955310246896534884706694089252556081961247017112250389141234521702999369939410904285579824042324261821130129688093066120035179492529832194910828474754124225013671020519517679792366327518907370483606574474640783766834539970262233301582292508827230014520357578885729700877397024090818937324055225400131994192599580996032991285461014891893404287273182434837815994588361305433651298765831523368642688747682634788173209457083503842498349707921949310812089538937182715816057326082958464332397599584885692887515328575778180916009118287156040300736392759945785253636452088638348601967247360000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(19) = 6327081385275264164346043097055158810366522474042555067954241969587402026356640692129364487188677463140592409956085164988176507531633437950253734005501196590402730311101738037402244175851123225999573689664805390329695222079477971838579573912158845425000533243033236690293692516650858313402043169149695643217466328340790498330386233806752154095775868002698922427592542082004230484075984315089576703999813923162484127871460124998102498642536234713099430644692747761669770777746139564172666648904485543155275387261619080608652622587863881653425834012192426501519681141866633211977179821028758779189668106437989556639096612988754760784757858242252724817303093020354072377423467443909819899050893378159432792700565029204415810054014885255618394331715072145636162644649818352376618788287271835188744213292099881701621221309293358225206034828472418796642728190265764638500464992937288882291831148730234766784072541608276911800771830275984734282129162395944802358781538885247194692094049416091266858762030913945600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(20) = 13366106203729717328004388722210709492786665116787079998681211538396679042570022585425404370821206040182545545327522208772410297140477757425772619410961344454117617230260366328664585446326493728844508629569445908755642341454003586455099667570898763628333813977467425743448041919790101558108208093996227738435574933039360725661756288491984803766778529753538486321787414062938450610866237972063079664018696360961878447208507659723847392806454333733426081417056070362965275011314780315281828339691106215863742591182739466913446535031731005413713456679104585248947030076457550189748025140180002025928042672399244074882778447836205867933905631221514711756063996080463141198210745160265531358580632240484040861201809726714468061099553945202311832719936014590289920108112191490634408727217523478784079999088684526361226049455825956216543757985870617646047936641338217984520100962194014027498487731444475919912503314546146199530972857141097807100303128683197139495113964913082086217692223191522669898844274394808515580151379363739632240534074543045038280245234230722927672902959146096339383367731184440630224573353521483612160000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(21) = 6306625595619345001195529259773013014981052845425957681044136514037384794592945465582945283745197149479272451634360732389454113202000208157688424605836314889418248366312488439729712537025832428429111527758541526901105895921729644223487275204662800908518533240589736250464384254643173036688030308143943446646893527733449234545005991058726068983733564368918887819028412175131832883768531372513925725955530038190272501266626297214443871148860893177246446462234715167183117389186283227848911536276609674108806444657028663590541599742959175454021390347318006702185596856629794506358939450042587545667207572738463444260194058183626732278351173596464271861122061128745003633255724801689157724325982499010924990741211058249741836807128634231585417889568794177388264974813712037928053200924727744671583400941457163800595561535335310175421475330448822692976198849988826716817481473618500538933625644774819913885202428357116262833824762956506219858998928269588869153415708394563325929649449664855327606969796263477988669988639573561409879992504915382011741709724748831669406559229169395097827547558831302731437845433745169301399325163390381504027603045861196726408006885794977612669316615277930170880925439439842113913917853529555254269444096000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(22) = 43255043761603797113630091774844134775453550640366980778547673133233526156056111086352762541106680563100444501556754078061200040161902545444981363159418942317624324342475893310046720902418909842572254925048152255763863441303957601376714844611959683697690635818016496854273739359313279064666370046140892353517823980846922675751474787577446355037664594347801588102349880881928045254762441010636430061482254233491880624942631395654007616048601555395209216128415329219747176133779395956146746911514214771775855690239351072162630720328485482144507681466660622736814225845041389468585359274634625239725398675655356047474149388129506975426678293985190094954373200648529109213009085243025295695714725062048495626790315739291458632493329982002276666437129462665130296574060413847380108081447548388904581805682624806259243368405271472607466620943953521539611552808899034647451671884821871473150002371967161469667395692183541805647906126837698919382420530164759161006195029042343889342090679974741074212214617599362461432095130944516954244601505865754479368324547884288638788858960324700273827359843495876728690396404545429654674917908712080130069636174970892229914900256301061633858082796212971135604567450455305742728394508401221110518309419409022610708624448968624438667397328140010446578078230783252681413859281663088893481022928914102101729840481251353235030016000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(23) = 66262393177381824732723525900139283590234965360823910580073779977865273717243514383604042990025103148871566189976942886930913783065583785533946642735881849910324451480884632180217851581883838483862727225179630287531434436158822489426014134399910062423717175574413478600256518896606893842233745345032857032262250159090620948581064655185529613417171104117029080510575185675176052793063668712314924450189275834562512929903465958484798579409424908775700520237201104817313643912663434277951000275666783464963920316202775959279571239819670095052640198241583838239163455793436431008787411448445722902807721263275498607381964525979131207347826069454406713054607996405160128348504643120375466375590743671164016060152286925213908645953174856877859607340359800331062620914380181340775083027285788760925763687742676733558790770055169794222694442162554073246433843467081533472035093073337940701526201699634527508694640678600238117144965192085492566083342186278117518199483130449223621506268183772367647393363214584052118038280979751327971380301188158987167780371511387515559307195282399723738374150567453311617570445111688148067634054892083030084024387109922685636233356152502559292336251234821065790918225078178922385789967563389223284930251760637720849162660792616270166689249910073092212723321966409635484807082743858627573648160096560789804959286681221649907531466381077400875719698826444869785989572882827213363703121873726170910608711481817962945203933518981345447414357546187647463981056000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(24) = 1475519806747454373901030622255510346331378029752771931240174199952289340073656084372530742371403121817954756916011809380426948327345728914945758632068801497214258642526145305262522066845023756724189849310020749355634710911268112644444765216990205487500797778318187105628790035913369801481356252461441573768496534732187624958213642937454591385535772215334611316290586282381282551984497101380577972744062598679502967941278029491579942572014374529555255136603918947272604871513773915252279872343346312363615717462117231536315213019368460589453689056130749848392120998647999933301781256148392881124994780124298716785532193754723082314580774816633413351254485826830202451604114899371541600759293210472262289400103936285421479364138827245838795442793956664559167930105844459636349545549137287134043273360346676762426323590717517682739606035175810469788222465654387498900958866524713377066886868522523262231687103910912522189110786128750096204311096256900279955292666842877053225464637913835418478638899350290642863792821318599615491107960898213335890459662264625050902474532715910202874635681437989551985750641754764549005942750967107561460782208580239591014681605964058770848448472730967112894939376045336435397403248683637573249670154956814282747273791946146020662885018898902949460759303114445469556323631506436759626735905163128686020289258710047853473190514253027437911908624532657962230063495112012439330679572232606653104432244178449913045835511449026257248635683333719178014429921904677088974012087402386140372185569700923946211526529795732276725049645872577846374619860278338803820490690732094329156093533864591360000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(25) = 7338606900448337036789808927714722374232054265556867083216987563605831302280124954511318020360031738952123850689949301067016810098821782952622119827191343811714153308174763344519829765740744966395281285250907162807467469411206193386044382177920656626556592406989586319048297532171232195980524608549470654382377337629683696121250485203852784671253465552723661921197323812277759207873014075438873998083588200340665392813884974033548770683966539756225190776056150183488334560717199712278700837482528510188957224739072757519973451653988332028901106023947653492013122471978273081760332246552295633523901575290421730800211251366731783357835649641682382571868916849108307173498957116523350145921674054778826517754760789955404188878815975983885256352902632633873020662232301766339543018349634680668362283438183702813228324979071338435402301910372014568598527037916456835524456894773921188526831393779186341836593724125208353829100559876542082775503510870799705631415086583990681065679299057922416132958730491243560060356773368590520847306709113021275033399321328976746385764292971315981681607381127459115526117981354672920424342659383996123548655976674499673057309342414853636864217778175504956701789630256547841517726192968093645888423683924945743234939386117107128406986222138769394079967354094120661761182197876722276455719218131307283520932301820550597642037727788159125117410163828735097141678436524639308956176346087213881095179847923513780445012559343543898821960560224764734838087057026877946627114988892818954861787433838722015223207055499970664774362372935907468804546985510049528366673121962024926187502872847716756747755025480612185841109985394393975911931963302893074202797834753563717887841509506339744669847853737346773669138655220124613894314393600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(26) = 530554217716300443683705459034835317581758856030327846472040502796027926072608943173855519462145994349193905260196888972851063779521222266121541576776293518415688547261498006090327476913556772896034049143463679713288994574816772804917331390301095922211963868193576039765977294511623605599725735564095218414482037450775497373459659268521898883697261937729670710805200549443635950054580194668751653361118720069953576421862123299641808300650348841333312446464157670067643181195734437039304945575891082767418401032510205296254764648147553934454346753751481998567040129719572932064417539125336186707312205936458788455992780187825663512292350302282024306642778641720459389440346212062354775900744351719192428948064060296834599138151791851563407251293873634353545435583837936614261279591802288730105030784903442989314309571198399026463584662442407854827150805118599131728234651897786240802583695471794196874429812229024075560664781228238002219376684047642457956619687518823214853760757019626927080783692664889419830789880389216958929606951181871762523880225860562164084097713754949096518453812549188688213179291825952092339988490381190036254601902914426376632478566556182293258622835442566698211295248183529929334895017750253909591492154947997138308438512337119830281177198692471804416998474809411268202378960945068428880053155411539111815751208340181428773195234947421468989090692646671386037017557502697585965380905779933015266521431934242978032475824906503084458488526318805195927270197408957563602264424964438873144359345233260459104901761334110962898715881781186834978846403917653184612293391454913178407385278394556916374526490543288432125625243763690367470188889689841358898502829336246194160553316330945029860972430893719177743779878538897707889474445069628916223095427473032289384559924282162318114079406397757715101818944848894460301829643714212988665724233147769046995996720224159008057401813237760000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(27) = 8567153977047340177911524098094249604282472016950947680918963648683057369713680954091666506565348084616075274384484241582483336322178570833490038563525329452266462360046622502923855605475348300652480408058229545645220741111883774466730668973748185838275691101005364467660718153524323919009206750967837593913703151668058691838727112358876481375828659476722679254855636114039835380811095462967115737352183370996193481230473355693861423506809137621499288485055706515513453883731394142126471169145963073527296320383592847448405295958058504633026372408035433050517988730699682817446239783188197420860503551826264929246430245749022443922143577276184582725473328041299550968247219376150688869029934946054315163065623816790980807613705028518810241735019944034172299309604100727292058398724111956609702080640374770042920956255408043568040826569242939091671691254980690099942104783488613787349486786417937092382620901674412824425296104791025842708032454266886480250401756749334240503405497677014468869026191989238697465218957104061901227522013696775482803600951566322259753169853496686845167235734380274443942266964539900475299048253890840160705195172334209583464088648374919246749880738471573812253454217635146897977602290689095298590333561879734701147972247838589946439254400576958995678338925301848778388426556013721853951403658419932707508787353946451962993413894600540582427729668508682829915081557350341890605151333816599318404795090328032843119737538439466138093807043556174231484327657097129667018740097843765275154624620136555966013062019100730129783668148250198914544094790957637884359462770209092483132902968095287630863004647285765931564505175229429876938611381311258132810621862575520974897770989563209127325828282201842464182738674269536913346731013830222201028669922912171101997939267852938080284277652597482754148895860653614999844423738317612139351785305183267205720732086201723103074421502993671547460033098373033912874526151692369334915576763508260680381979634273926163946979971705565421655463567676639375462991749084529097608720523026497536000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(28) = 2010902151940143680629101301580067113425268568193572350305262236380653725301579575803159184650490077986865807586918624560085850277658930337300883615296425725379884612475664966288744528913306541485597609077055151379985065212691143887615636549571944440148820667689390185151610313722101519503307538226829499400761540379737920992162251435578368711331708324249066935215717461777607060708058800427566386894619572471487455107535436966897270355115821958116166558318800932073455689974286925584879085933792301740727234292959110806881553045824321870619656090785929823591490026609093587643584308329301482144234972021546447262301095809850361890736935795355805366273103444908584123432078398107803015556065303455444575436239959138518754247467641284908971352850196612813187149798177020167806968067225768331563577819020052457111696813799026352623680248124848642966644484850341473811379057603312846824257081033917500948913377047043827801821909238743053277594936836928157669020210619772876953735725204903224765708286405149246548918446494435837048201787825856827784000143259803748684623582828298075391952929112496234901682521241833952139552835944943414204209496314388781083582988096653086511479773583026614925209498325493106087430521194360860506339851743090769044054370717410312908777659234501760813601000975263771257688034897609386760562791592604659163646317554394664979047486122756097798501874075318341811154928261287604782430800442975910909396601915368434036523683926401615374759538276414960138435510979763270179974903837361216224273783454624924843152753510403683349376025751654930562678750641239638217347639883075914883662203252266446471767616442839835845169494418518346099329519983597707729769631606973617682708096848545773867399005942829132613604536750086197119968130892975831248772020974065089039113352666991914356060296466604545405892330593658568917484666860870185806228235747546188365061597463633493582575298170791919765049260220213496667381573769022642104767417516586534979688295747994552711113642829435833064800451486147749749219449059177520171367547819583435147202713763178475481357786578806665879466338334206884169776364281467561147406603171346278050523229290629468098119168017121416547576044898952962654428343566336000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(29) = 105423143034307091577479047217327902556176088305639054968472024780665401949660238207710489593582367566377851285708594852935456785607683729231083545089958216503849958930701992206188154151178860754867234553810143802809807136979201134363775459806868993826914710561256141627716452199713149243442196242079849543663080962176023519521924063086760835921447839884345026666337142361565801442519849398887815932045614782808466547351010582688695871268647423552150962280377711002460928316026537954396134795693732009073127857103560112998298519762951289036942143169948066140893066811922093168891367256866394645370146823460759922327128437858974659127706747453541981186530538890337280085496234361408913352844558704851079557598751767537357713332744927468160646576970869002516954988062933749762228719455071078366951457137680207837216987543458019924945776194487511395533755782718979638255276236376955684651945393967778166829254734833692871212771147914594783203584218944229093926980792617626288947722589949068987184641916292385313689566986333097627864165676529230666383601806496988387546228384486411454383197831751460570379141840428145878661006495148447519054830694735977802498911574169324027223655400755787847139386868701534697688308905774809850841104180444084481081919809417954847175566084254208826111622619944197612018861388670844346462403534262251557442338280116300390351758343816773721337481911454541987604393761259974055084375102992673107326313811816105407553434575200335308153373198336092282823825748095267732318185755894012681913266577076132067868297330936215813567398265901451100298735041141930528097458572077097978254373673768153296769342483553602499436258768840235454630046720219639867974952486384476146860443112314087190586467479886721972895284117409144007157013018806906277852565067258524498225254554986209797777789796014682156333262335629415078704367599048723647320834629634231593628478959494996703569657932439581576243665900106172042852736167673913845956106441702051712111803540788955623424922559545812111964827448860378091658165016444807706380940589165967101490889906444210109460666240639882449672928310022925191629661482950404051686547994295289558317091989881843200090755714048352600949250194127667442720129381718566611299860921213068049038923432607347278909332512884929575935815587515776141519540663949156523375966531604828916879392997860711433382202900887367044764958457856000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(30) = 80339393006245040934764369612704580491107188440587678665408015257741566559818708381798825750897482011842286156629638754186229426134997465068511437508928257721908615107945686191983315464446513958470610417592265876467917508457756597749095042892885334271408855166417210812465434427927274175239886510681136019360395693400812503466736963501109785486809606367904137396481550217790907792599016323146553614436603346374777725156609384157548169756879945056955323347241361371368238758583995753828768672208399336850281913268167057627142138029103649767956432205834939568515596361742352366795127212166224004444107296518359374735678465061652637847966398052174333154630927951136433133849889813408028080773114293871306660771746002884656051854113220843866170772404626679840369101790655812729028060436701613330265871719988278843601321874327198748863276607332617975577837606919431225010562194357495972116901679391711211321478989183477846405990079600732862385852941274597787142122762366643798059791349460423361323733091568166745506736998484696848394300783592017261649687497395158178563454748392746927980877306675744622616546101603596399980127556452860950304139869831208528982371839643865006118994682038512008663999739427697886838258285244043357412522232098676902280953675155472095643175385488829847025728305489362547239833967672251123426369907649693035853531550614551666834848521679585218527499108366342406545439246820489173366788602662495186609478617518165463209973776908913098908859419579100050138450618637660814624979724513985588400227841056766008087357284264331024995738439446410073932304238323263625455744097387015357774480394012878457942245309007722631980673632230470552574752633427240418230221992963194942634498952813308775960039157406071214917308788791191448825648954528089287683552896686965281753954788975813340902052135709352337799694702068880730338140171274223096554291488150793896522598368460073900095547328786549989589605735673314723441469007173709657369866926512963167911026208801417157215108539827946968773083804936759862107645065138111957720748074379034751368604027679483538902100216995428596649550177168283619861578364517876795477139906276695713372399140719384424580210295693649980404075215861008342350144433329021711496469610891036071234940030372024982538796036466669744324509204381106630187306532158345908516562632117423120224913430825235331052765964613351082706115846867234904944496260215978089989342630337968037740062568161912814115800814767922065924897685029415668651493435750347562736106979771359876538119580476443093964795615580950364160000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(31) = 13674510438463642847319067217914804686648811728367323792567155213184660220296299279498799361970022528929005735173729509468929661322326748784010414349080815912341994211449735767184607305046587814307104929605694160305973105682185114914929451314797389194136208686828921906395054640935503776458708508524904831694188779896421578284586858315253531749404834067022781878600868928466741008686572771613362725183604850887927274047459376717314766269350723844454962832478319756583612435493767580974897598645792966656109885877280944206581493383421091278135922502973412557362699316692471147796677671965815250651469962624820894497149873546102707511123755684950186650177321370188977153656918488799808023076215316749252999737922553576864926636159581974980491799025552401363220055843551569695217434682469477468584336124904991760688857263991140895857003399136957155545389635753695603396374507430052186192710655397252613651064730442131047712806691935590580897853629012685670474116147614175793504590369917316979728045204916386474178024821198423000348063376937719103034658150676525705336400016094774370011736952311505860442331628983793002713570433546603124336142126578445843096751100830417862658917642912696214462387866115559175373861780863506643775229433095769286423266288325434130702995274590502360311489105894296849233878369940040171137193260334197618284214480280946889571411383382519014769703904642970867187661161270262229712124498645615224647699789373203258160090085074936200917523770019841320570998014266142807683736454005881389716989314450985951032687936307129385114033863541461122340361771521836029497140691973203501567653517322480188505566038731459914930421428407723671568879644737778075986732402419048474865964005214185771795972277207640619320377963201832592994381560622935930632762758785281326290814920330926877796333160716456179123871696823329031931844697473956229347135203539778491700257791180605624319986378789926156395534744628865591998330293179406365241215344262849801319414930571335680066132148662552441318895106394024241544996551532807123911177565661486860161877715981645953791934618321776151766737095780729235945076642579363794310999918823939345359157406251827405332862049261276916626231455770214913658200200141239499264055374960200855248672869571371484681780597682170454612412722219238753252146270410159018217476128410073638751057070201185335798147838832612147876003483152281042493547235743459866832703113284160320122458675522409829843304809703153555923269455854369029607028150064719188337435820226817195099348266169160465141810191331929948779415841909526879317850894237225467649614534093870146515050073385998149203290558164655721936694163936654060877874309203184353721344862493672912289405565236603636287421389209600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(32) = 33833162388357861215761712659524361394051394277470170652951058776000389795780865103207964926360587361796683708778338625234496295148381685136265114820783703903935222516207328106699335547120225608933941680294905728617152211806036384507184383244665563642105629525406654962825595898378345121993210183743033969362354802425523979157713693386764994010979394255142104832446338145997879223596435068628902686594549087501572932314715123982854196753625002580095710840908788963331269617748363523481023878835638198153925525581264346862647481528521891412355410488241706953564548824682428460218481252973789860618816413986126094352043798454140140236109237486503628443772595115364976572900174732183294907967857118028712672441758104348438781325265517955736696864614125264800825806559910597723913148735763629187309833830951467244093350042500018749227824605994438851149411541404269508701189234785289500485249072293033203695390013842829819646551004127479240268508761427627195719410385441311369438682810327658912398189561929464362788462336179456327266387414811039189055499488284633202721678542318937890666750681266442244695175193337866131310714610091290951739988775969606260930362674169638817350616331954397944749630254593049190701447198229974275524348631479333646939117793266904681350954853949938951313774315875498181123847427655418812393435628433595698248447950222507171604251240957901512066847349692905441281404281431262149502897149773185506566656393170541870777400264550158061775678298888483934574369492140847840388826063439109190700519418355273352173040641992336540072258867528126168025151976769708773828363288738223327022611985994466788262782982773019712154043056227733980478300938943011598856432585400713522941229360367853596334489194603826668236385651736816002772866061047764269760041673194570882082148070731492569417095003769188855536671109201019516855417966382731766037610216097591096362167840358922905117615786546278937533940250857376586938612351876755513628171720673973537632712804330968405378838182404189263601658655069769047260159718265247664911603920191085546550286878439075382706097033732591607985658349699333795354237025191209148339387795471668358797685337915974949793864157142173247424058955687335520863397950327440793849142009111279861836246346808946072562548234203577805125092937398529976641460392845486654661045614678768853453288332590740639999631883680796168168650206648749518626791623285535961379333914231927341231051236850005970219530811853621655574674451106994724613039954466808065190480033284230508203095196692543416779793677711502071254395424231110833929323718777654239026947149854115006272194200702979146343111242498687585682574878711833935454052975048275549285704668344068902951681994892464254252726861428944174887654857824760605780520882566813011331183516785277466892892873509066686257611781974272713889710424766180880853251260451964036775338919912641622472819250307911390979986460508160000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Permutations(33) = 18696661017127716111007156893925182193580853716692179089899478770943582489675190515395666720208824480551903354480259788238676247511303388257801174231854545181920331181004789261814745312182045845428762796414771202263258342463967030089505969241875171955882104131017084426143559735118060518958986032546827073268351150949094697082284068502185835024900202885137925851959016340960054511342239010486971915403874766402029227802835748445428637294107015987419019235281524947733483987031906228242703569319940723834006213661303657044973777054596850622339905549047180325875714611082107309813975377700695388649964156866557245696819820865952106810029808475650120048168612759312495915207278023591619310527178624145453299290756599161731653727119079148998832305431472444485003213105263921382138000630955405260355220227517849216389923063962296323617452629465245938888170333420277491482282387862650488506483916068477677335196983634154066662817054036913670631480843391896898095289197502976446886272288891843622751850435358314369040529181867906228157347964356931755058318697673475909861291319993495051618194556231765205307773436085376600106715382729811311151062297530013196922200169049899195720431633871659709082213265246913799573097369894307931440091696232658219286403011006986904930914555541057575986191269556649296413226169690126844072573402028618406572452754735339121404763059835851653622056009940485980506628450585478954375754263846566088288400306320232445244940783913062474755755488130952853589677385508812036155295909600334461009170449449778052716093328109091142332166748374529031504985039984798269090925239446796909703998296038551828223611028283564145599982456267463133573373321128804326697472846902824121049374652823783220742223223394089420032514643999552419194623064581621379214011303419818852542719254429825543782471134005876397941166969533163639878876446499347945222076636675398871360445887377678707339512978898238687044203220992043227913596034342041636421661001246729757424044266838735166992986182767776085773395737420226540902433660158218097026199645776512529095377708566186870345447176919169408888112689299155913979907842652145804922670912866078004529506494807248753864444966745599277582569274799190241357341381581960335827103553927828418095765419915227643833908629520789146019920225714247737997176858507095620234841064836606309188269924218687259884683401701072334549089443000087194667381009959427838747006234583718733105953535175498234170080426507673439005897219609158937590295438004056943776061638644300750980734901711410524662179876755109368371729499781279393654688077210089535820330346819309464620860354231280301068820707654881878957579038675971240125144885705305013547097918534219176279116639113062572023735338858537751174044436341628965370270802513903276155091115854505151811338182911347524669037687253200441469365288093913620244278033648511931271564309222494059464112137597042720525593895661580759680528992782512523966003611023682264889787017760092830059027287266422048371828092743026820043551356210109062588582398709328351588071955018182462349156223042237468751043507997638656000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

I hope no typos in my calculations, mainly not swapping Permutations(2) and Permutations(3) when doing the math.

------------------------

Calculating log10[Permutations(n)] from n = 2 up to n = 33:

Code: Select all

 n    log10[Permutations(n)]
----------------------------
 2           6.565158065
 3          19.636006227
 4          45.869301955
 5          74.451588337
 6         116.196322285
 7         160.290046887
 8         217.546219054
 9         277.151381876
10         349.918992264
11         425.035593306
12         513.314641913
13         603.942681175
14         707.733168002
15         813.872645484
16         933.174570531
17        1054.825486232
18        1189.638849499
19        1326.801203421
20        1477.126004907
21        1629.799797049
22        1795.636036756
23        1963.821267117
24        2145.168945043
25        2328.865613625
26        2525.724729771
27        2724.932836573
28        2937.303390939
29        3152.022935960
30        3379.904928546
31        3610.135911787
32        3853.529342593
33        4099.271764054

And fitting the data with a quadratic function with Excel, I get:

Code: Select all

log10[Permutations(n)] ~ 3.8778595550 * n² - 3.6230131391 * n - 2.9290557985

R² ~ 0.9999988433

Regards from Spain.

Ajedrecista.

[petero2]

Hello Peter:

It would be very interesting to know if their algorithm could actually be trained to learn how to solve a 17x17x17 cube. The state space is very large. Just the inner pieces can be arranged in (24!/4!^6)^56 ~= 10^868 ways. My guess is that their algorithm cannot solve 17x17x17 cubes, or else they probably would have mentioned larger cubes in the abstract.

I googled the state space of a n x n x n Rubik's cube ...

Code: Select all

 n     Permutations(n)
-----------------------
17    6.690926087e+1054

Thanks, that is roughly what I got from a very crude approximation so it looks reasonable to me.

If the quarter turn metric is used a 17x17x17 cube has 3*16*2 possible moves in any state, since there are 3 axes, you can turn between 1 and 16 layers, and you can turn in 2 directions. This means that if you start from the goal state and perform 530 moves, you can reach at most (3*16*2)^530 ~= 10^1050 different states, which is less than the total number of states. Therefore we can conclude that there are scrambles that require more than 530 moves to solve.

Based on a very rough extrapolation from a 3x3x3 cube, my guess is that there are scrambles that require more than 700 moves to solve.

I don't think weighted A* search can find such long solutions using the proposed heuristic function. I guess some sort of hierarchical planning would work better for finding very long solutions.

Also, thanks to Michel for finding a link to the full paper:

Maybe this link works?

https://www.nature.com/articles/s42256- ... izmodo.com

[Sven]

I think the speedcubing numbers are way too large, I have more confidence in the Wikipedia numbers. The speedcubing approach sees a 3x3x3 cube (for instance) as consisting of 27 pieces that can be moved. But in reality there is one "invisible" piece in the middle that is irrelevant, and furthermore the six central pieces always remain fixed relative to each other (from a viewer's perspective) so their movements are irrelevant as well. And as a third point, I think that there are many cases where two different move sequences lead to identical states of the cube for the viewer. Finally, the speedcubing approach also considers different orientations of each single piece which is irrelevant to the viewer (you can turn a red square by 90, 180, 270 degrees and it still looks the same) so it should also be irrelevant to permutation calculations.

[Sven]

Another question is, do n x n x n Rubik's cubes actually exist with even n? If so, how many "fixed" central pieces do they have (0 or 24)? If they only exist in mathematical theory then why should they be relevant for us?

[Ajedrecista]

Hello Sven:

I think the speedcubing numbers are way too large, I have more confidence in the Wikipedia numbers. The speedcubing approach sees a 3x3x3 cube (for instance) as consisting of 27 pieces that can be moved. But in reality there is one "invisible" piece in the middle that is irrelevant, and furthermore the six central pieces always remain fixed relative to each other (from a viewer's perspective) so their movements are irrelevant as well. And as a third point, I think that there are many cases where two different move sequences lead to identical states of the cube for the viewer. Finally, the speedcubing approach also considers different orientations of each single piece which is irrelevant to the viewer (you can turn a red square by 90, 180, 270 degrees and it still looks the same) so it should also be irrelevant to permutation calculations.

As I said in my previous post, if you feed n = {2, 3, 4, 5, 6, 7, 8} into that equation, it gives the same exact results than in Wikipedia:

Code: Select all

 n      Wikipedia full number
-----------------------------
 2      3,674,160
 3      43,252,003,274,489,856,000
 4      7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000
 5      282,870,942,277,741,856,536,180,333,107,150,328,293,127,731,985,672,134,721,536,000,000,000,000,000
 6      157,152,858,401,024,063,281,013,959,519,483,771,508,510,790,313,968,742,344,694,684,829,502,629,887,168,573,442,107,637,760,000,000,000,000,000,000,000,000
 7      19,500,551,183,731,307,835,329,126,754,019,748,794,904,992,692,043,434,567,152,132,912,323,232,706,135,469,180,065,278,712,755,853,360,682,328,551,719,137,311,299,993,600,000,000,000,000,000,000,000,000,000,000,000
 8      35,173,780,923,109,452,777,509,592,367,006,557,398,539,936,328,978,098,352,427,605,879,843,998,663,990,903,628,634,874,024,098,344,287,402,504,043,608,416,113,016,679,717,941,937,308,041,012,307,368,528,117,622,006,727,311,360,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

Or more less:

Code: Select all

 n      Wikipedia number
------------------------
 2      3.6742e+  6
 3      4.3252e+ 19
 4      7.4012e+ 45
 5      2.8287e+ 74
 6      1.5715e+116
 7      1.9501e+160
 8      3.5174e+217

OTOH, calculating again the powers of what I called c(n) and d(n) in my previous post, just for simplifying my task in Derive 6:

Code: Select all

n    Power of c(n)    Power of d(n)
-----------------------------------
2           0                0
3           0                0
4           2                6
5           3               12
6           6               24
7           8               36
5          12               54

Then:

Code: Select all

n = 2:



            0 
 3674160·24!  
______________
        0     
      4!



3674160



          6
3.67416·10

Code: Select all

n = 3:



       10     MOD(3, 2)     6     0 
 ((24·2  ·12!)         ·7!·3 )·24!  
____________________________________
                   0                
                 4!



43252003274489856000



              19
4.325200327·10

Code: Select all

n = 4:



       10     MOD(4, 2)     6     2 
 ((24·2  ·12!)         ·7!·3 )·24!  
____________________________________
                   6                
                 4!                 



7401196841564901869874093974498574336000000000



              45
7.401196841·10

Code: Select all

n = 5:



       10     MOD(5, 2)     6     3 
 ((24·2  ·12!)         ·7!·3 )·24!  
____________________________________
                  12                
                4!



282870942277741856536180333107150328293127731985672134721536000000000000000



              74
2.828709422·10

Code: Select all

n = 6:



       10     MOD(6, 2)     6     6 
 ((24·2  ·12!)         ·7!·3 )·24!  
____________________________________
                  24                
                4!



157152858401024063281013959519483771508510790313968742344694684829502629887168573442107637760000000000000000000000000



              116
1.571528584·10

Code: Select all

n = 7:



       10     MOD(7, 2)     6     8 
 ((24·2  ·12!)         ·7!·3 )·24!  
____________________________________
                  36                
                4!



19500551183731307835329126754019748794904992692043434567152132912323232706135469180065278712755853360682328551719137311299993600000000000000000000000000000000000



              160
1.950055118·10

Code: Select all

n = 8:



       10     MOD(8, 2)     6     12 
 ((24·2  ·12!)         ·7!·3 )·24!   
_____________________________________
                   54                
                 4!



35173780923109452777509592367006557398539936328978098352427605879843998663990903628634874024098344287402504043608416113016679717941937308041012307368528117622006727311360000000000000000000000000000000000000000000000000



              217
3.517378092·10

I have done 'Derive 6 number' - 'Wikipedia full number' in Derive 6 for 2 =< n =< 8, obtaining 0 in all cases, so the formula at speedcubing gives the same results than Wikipedia.

------------------------

Another question is, do n x n x n Rubik's cubes actually exist with even n? If so, how many "fixed" central pieces do they have (0 or 24)? If they only exist in mathematical theory then why should they be relevant for us?

It looks so, according to Wikipedia again:

Pocket Cube (2x2x2)

Rubik's Revenge (4x4x4)

V-Cube 6 (6x6x6)

V-Cube 8 (8x8x8)

According to the first paragraph of each article, these cubes do exist and have not fixed facets. YouTube searches might return videos of people solving 2x2x2 cubes, 4x4x4 cubes and so on.

Regards from Spain.

Ajedrecista.