Self-taught AI solves Rubik's cube

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
petero2
Posts: 587
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: Self-taught AI solves Rubik's cube

Post by petero2 » Thu Jul 18, 2019 7:46 pm

Daniel Shawul wrote:
Thu Jul 18, 2019 3:24 pm
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.
Daniel Anulliero wrote:
Thu Jul 18, 2019 3:32 pm
Daniel Shawul wrote:
Thu Jul 18, 2019 3:24 pm
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
Posts: 2050
Joined: Sun Sep 28, 2008 11:50 pm

Re: Self-taught AI solves Rubik's cube

Post by Michel » Thu Jul 18, 2019 8:17 pm

Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

User avatar
Ovyron
Posts: 2746
Joined: Tue Jul 03, 2007 2:30 am

Re: Self-taught AI solves Rubik's cube

Post by Ovyron » Thu Jul 18, 2019 9:03 pm

petero2 wrote:
Thu Jul 18, 2019 7:46 pm
Daniel Anulliero wrote:
Thu Jul 18, 2019 3:32 pm
Daniel Shawul wrote:
Thu Jul 18, 2019 3:24 pm
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.
Great spirits have always encountered violent opposition from mediocre minds.

Daniel Shawul
Posts: 3758
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Self-taught AI solves Rubik's cube

Post by Daniel Shawul » Fri Jul 19, 2019 2:12 am

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
Posts: 2134
Joined: Tue Apr 03, 2012 2:28 pm

Re: Self-taught AI solves Rubik's cube

Post by chrisw » Fri Jul 19, 2019 7:04 am

petero2 wrote:
Thu Jul 18, 2019 7:46 pm
Daniel Shawul wrote:
Thu Jul 18, 2019 3:24 pm
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.
Daniel Anulliero wrote:
Thu Jul 18, 2019 3:32 pm
Daniel Shawul wrote:
Thu Jul 18, 2019 3:24 pm
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.

User avatar
Ajedrecista
Posts: 1400
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Self-taught AI solves Rubik's cube.

Post by Ajedrecista » Sat Jul 20, 2019 12:18 pm

Hello Peter:
petero2 wrote:
Thu Jul 18, 2019 7:46 pm
[...]

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
Posts: 587
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: Self-taught AI solves Rubik's cube.

Post by petero2 » Sun Jul 21, 2019 8:51 am

Ajedrecista wrote:
Sat Jul 20, 2019 12:18 pm
Hello Peter:
petero2 wrote:
Thu Jul 18, 2019 7:46 pm
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:
Michel wrote:
Thu Jul 18, 2019 8:17 pm
Maybe this link works?

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

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Self-taught AI solves Rubik's cube

Post by Sven » Sun Jul 21, 2019 10:42 am

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 Schüle (engine author: Jumbo, KnockOut, Surprise)

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Self-taught AI solves Rubik's cube

Post by Sven » Sun Jul 21, 2019 11:09 am

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?
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
Ajedrecista
Posts: 1400
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Self-taught AI solves Rubik's cube.

Post by Ajedrecista » Sun Jul 21, 2019 12:21 pm

Hello Sven:
Sven wrote: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.

------------------------
Sven wrote: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.

Post Reply