login
Table of Non-Overlapping Rook Paths

Table of Non-Overlapping Rook Paths

From: 	  Heiner Marxen 
Subject:  Re: Self-Avoiding Walks of a Rook on a Chessboard
To: 	  sfinch@.com (Steven Finch)
Date: 	  Mon, 9 Sep 96 20:47:01 +0200
Cc:       nl3242t@nlccmail.snads.philips.nl
...
----- snip -----

This is a table of results regarding a puzzle from the rec.games.puzzle FAQ:

> ==> competition/games/chess/rook.paths.p <==
> How many non-overlapping paths can a rook take from one corner to the opposite
> on an MxN chess board?

Computed Jul-9-1994 by heiner@drb.insel.de (Heiner Marxen) on an Apollo
HP9000-710.  Computation stopped, when the number length exceeded 63 decimal
places.  In brackets is given floor(log10(W)) (i.e. length-1).  Up to W(8,8)
the results have been confirmed by andreas@hit.ordina.nl (Andreas Gammel).

W(1, N) is not given, it is proven to be 1.
W(2, N) is not given, it is proven to be 2^(N-1).
W(M, N) is given below for M=3..12 up to some appropriate N.
Timing:	W( 3,*)  <  1 sec
	W( 4,*)  <  1 sec
	W( 5,*)  <  1 sec
	W( 6,*)  <  1 sec
	W( 7,*)  <  1 sec
	W( 8,*)  <  3 sec
	W( 9,*)  < 11 sec
	W(10,*)  < 51 sec,   using  0.7 MB
	W(11,*)  <  4.5 min, using  3.2 MB
	W(12,*)  < 28   min, using 14.7 MB
While it is relatively cheap to compute larger N, current methods do not
extend beyond M=12.  M=13 is expected to take 7.5 times the time and space
as M=12.

W(3, 1) =                                                               1 [ 0]
W(3, 2) =                                                               4 [ 0]
W(3, 3) =                                                              12 [ 1]
W(3, 4) =                                                              38 [ 1]
W(3, 5) =                                                             125 [ 2]
W(3, 6) =                                                             414 [ 2]
W(3, 7) =                                                            1369 [ 3]
W(3, 8) =                                                            4522 [ 3]
W(3, 9) =                                                           14934 [ 4]
W(3,10) =                                                           49322 [ 4]
W(3,11) =                                                          162899 [ 5]
W(3,12) =                                                          538020 [ 5]
W(3,13) =                                                         1776961 [ 6]
W(3,14) =                                                         5868904 [ 6]
W(3,15) =                                                        19383672 [ 7]
W(3,16) =                                                        64019918 [ 7]
W(3,17) =                                                       211443425 [ 8]
W(3,18) =                                                       698350194 [ 8]
W(3,19) =                                                      2306494009 [ 9]
W(3,20) =                                                      7617832222 [ 9]
W(3,21) =                                                     25159990674 [10]
W(3,22) =                                                     83097804242 [10]
W(3,23) =                                                    274453403399 [11]
W(3,24) =                                                    906458014440 [11]
W(3,25) =                                                   2993827446721 [12]
W(3,26) =                                                   9887940354604 [12]
W(3,27) =                                                  32657648510532 [13]
W(3,28) =                                                 107860885886198 [14]
W(3,29) =                                                 356240306169125 [14]
W(3,30) =                                                1176581804393574 [15]
W(3,31) =                                                3885985719349849 [15]
W(3,32) =                                               12834538962443122 [16]
W(3,33) =                                               42389602606679214 [16]
W(3,34) =                                              140003346782480762 [17]
W(3,35) =                                              462399642954121499 [17]
W(3,36) =                                             1527202275644845260 [18]
W(3,37) =                                             5044006469888657281 [18]
W(3,38) =                                            16659221685310817104 [19]
W(3,39) =                                            55021671525821108592 [19]
W(3,40) =                                           181724236262774142878 [20]
W(3,41) =                                           600194380314143537225 [20]
W(3,42) =                                          1982307377205204754554 [21]
W(3,43) =                                          6547116511929757800889 [21]
W(3,44) =                                         21623656912994478157222 [22]
W(3,45) =                                         71418087250913192272554 [22]
W(3,46) =                                        235877918665734054974882 [23]
W(3,47) =                                        779051843248115357197199 [23]
W(3,48) =                                       2573033448410080126566480 [24]
W(3,49) =                                       8498152188478355736896641 [24]
W(3,50) =                                      28067490013845147337256404 [25]
W(3,51) =                                      92700622230013797748665852 [25]
W(3,52) =                                     306169356703886540583253958 [26]
W(3,53) =                                    1011208692341673419498427725 [27]
W(3,54) =                                    3339795433728906799078537134 [27]
W(3,55) =                                   11030594993528393816734039129 [28]
W(3,56) =                                   36431580414314088249280654522 [28]
W(3,57) =                                  120325336236470658564576002694 [29]
W(3,58) =                                  397407589123726063943008662602 [29]
W(3,59) =                                 1312548103607648850393601990499 [30]
W(3,60) =                                 4335051899946672615123814634100 [30]
W(3,61) =                                14317703803447666695765045892801 [31]
W(3,62) =                                47288163310289672702418952312504 [31]
W(3,63) =                               156182193734316684803021902830312 [32]
W(3,64) =                               515834744513239727111484660803438 [32]
W(3,65) =                              1703686427274035866137475885240625 [33]
W(3,66) =                              5626894026335347325523912316525314 [33]
W(3,67) =                             18584368506280077842709212834816569 [34]
W(3,68) =                             61379999545175580853651550820975022 [34]
W(3,69) =                            202724367141806820403663865297741634 [35]
W(3,70) =                            669553100970596042064643146714199922 [35]
W(3,71) =                           2211383670053594946597593305440341399 [36]
W(3,72) =                           7303704111131380881857423063035224120 [36]
W(3,73) =                          24122496003447737592169862494546013761 [37]
W(3,74) =                          79671192121474593658367010546673265404 [37]
W(3,75) =                         263136072367871518567270894134565809972 [38]
W(3,76) =                         869079409225089149360179692950370695318 [38]
W(3,77) =                        2870374300043138966647809972985677895925 [39]
W(3,78) =                        9480202309354506049303609611907404383094 [39]
W(3,79) =                       31310981228106657114558638808707891045209 [40]
W(3,80) =                      103413145993674477392979526038031077518722 [41]
W(3,81) =                      341550419209130089293497216922801123601374 [41]
W(3,82) =                     1128064403621064745273471176806434448322842 [42]
W(3,83) =                     3725743630072324325113910747342104468569899 [42]
W(3,84) =                    12305295293838037720615203418832747854032540 [43]
W(3,85) =                    40641629511586437486959521003840348030667521 [43]
W(3,86) =                   134230183828597350181493766430353791946035104 [44]
W(3,87) =                   443332180997378488031440820294901723868772832 [44]
W(3,88) =                  1464226726820732814275816227315058963552353598 [45]
W(3,89) =                  4836012361459576930858889502240078614525833625 [45]
W(3,90) =                 15972263811199463606852484734035294807129854474 [46]
W(3,91) =                 52752803795057967751416343704345963035915397049 [46]
W(3,92) =                174230675196373366861101515847073183914876045622 [47]
W(3,93) =                575444829384178068334720891245565514780543533914 [47]
W(3,94) =               1900565163348907571865264189583769728256506647362 [48]
W(3,95) =               6277140319430900783930513459996874699550063475999 [48]
W(3,96) =              20731986121641609923656804569574393826906697075360 [49]
W(3,97) =              68473098684355730554900927168720056180270154702081 [49]
W(3,98) =             226151282174708801588359586075734562367717161181604 [50]
W(3,99) =             746926945208482135319979685395923743283421638246892 [50]

W(4, 1) =                                                               1 [ 0]
W(4, 2) =                                                               8 [ 0]
W(4, 3) =                                                              38 [ 1]
W(4, 4) =                                                             184 [ 2]
W(4, 5) =                                                             976 [ 2]
W(4, 6) =                                                            5382 [ 3]
W(4, 7) =                                                           29739 [ 4]
W(4, 8) =                                                          163496 [ 5]
W(4, 9) =                                                          896476 [ 5]
W(4,10) =                                                         4913258 [ 6]
W(4,11) =                                                        26932712 [ 7]
W(4,12) =                                                       147657866 [ 8]
W(4,13) =                                                       809563548 [ 8]
W(4,14) =                                                      4438573234 [ 9]
W(4,15) =                                                     24335048679 [10]
W(4,16) =                                                    133419610132 [11]
W(4,17) =                                                    731487691902 [11]
W(4,18) =                                                   4010463268476 [12]
W(4,19) =                                                  21987818897998 [13]
W(4,20) =                                                 120550710615560 [14]
W(4,21) =                                                 660932932108467 [14]
W(4,22) =                                                3623639655071710 [15]
W(4,23) =                                               19867014742102743 [16]
W(4,24) =                                              108923158053332350 [17]
W(4,25) =                                              597183548805361659 [17]
W(4,26) =                                             3274126433946876296 [18]
W(4,27) =                                            17950768950492095067 [19]
W(4,28) =                                            98417123591603463702 [19]
W(4,29) =                                           539583025251001060895 [20]
W(4,30) =                                          2958325040532073565578 [21]
W(4,31) =                                         16219352047588503102931 [22]
W(4,32) =                                         88924434346993487396018 [22]
W(4,33) =                                        487538281475956033249386 [23]
W(4,34) =                                       2672983839031408908893916 [24]
W(4,35) =                                      14654936597168716548095928 [25]
W(4,36) =                                      80347349479245087653282074 [25]
W(4,37) =                                     440513442384128454230014613 [26]
W(4,38) =                                    2415164833424179619327303842 [27]
W(4,39) =                                   13241414702442720218413491702 [28]
W(4,40) =                                   72597555618379554849853118946 [28]
W(4,41) =                                  398024319923418028799874399486 [29]
W(4,42) =                                 2182213407890434581197668112870 [30]
W(4,43) =                                11964232131576855889677682759218 [31]
W(4,44) =                                65595257540202524866505250371022 [31]
W(4,45) =                               359633427740791094233174799503049 [32]
W(4,46) =                              1971730993956723856944164669063190 [33]
W(4,47) =                             10810238461291424483325071391724948 [34]
W(4,48) =                             59268356559875272059272626241138728 [34]
W(4,49) =                            324945476631869566441981252258628354 [35]
W(4,50) =                           1781550373795873303046713142646399904 [36]
W(4,51) =                           9767551674424287869585654837546753491 [36]
W(4,52) =                          53551708172737889118984976149020490376 [37]
W(4,53) =                         293603304472623945552890943383774309553 [38]
W(4,54) =                        1609713365616383912308859851071670622980 [39]
W(4,55) =                        8825435817550996535425583680276951174743 [39]
W(4,56) =                       48386451298357329879562930164488161283378 [40]
W(4,57) =                      265284198723909326010530260334192363603579 [41]
W(4,58) =                     1454450661377099111998484352537278610029664 [42]
W(4,59) =                     7974190458972193232276413494739024904035175 [42]
W(4,60) =                    43719402221425103400219631051992513835552796 [43]
W(4,61) =                   239696573643804342555403482756570411438692093 [44]
W(4,62) =                  1314163609227566871627401045217315241219245708 [45]
W(4,63) =                  7205050808879866983229734138168052327879819646 [45]
W(4,64) =                 39502506989257958949229300006423441433947940968 [46]
W(4,65) =                216576967994895917886491309999855977545519956240 [47]
W(4,66) =               1187407753098236361825775237145885246834124153838 [48]
W(4,67) =               6510097473296561785818236153147375605099451792511 [48]
W(4,68) =              35692346627549762778296694042467212171999382378068 [49]
W(4,69) =             195687332333607524724325619649009538171416821980512 [50]
W(4,70) =            1072877959957001642510955492475520008145421812677274 [51]
W(4,71) =            5882174912575126770545069198885225692099460671417212 [51]
W(4,72) =           32249690079862283655389057301327920860488527689575482 [52]
W(4,73) =          176812577950330447532667716843020938774666605024948768 [53]
W(4,74) =          969394981595903209253602872718018527127931582396345810 [53]
W(4,75) =         5314817764872508909440911901788699733363068719878363267 [54]
W(4,76) =        29139090267726828672101491129568926164985894708877166896 [55]
W(4,77) =       159758362223187186115178951141088305982105151431979627194 [56]
W(4,78) =       875893312582340209091675503057602610992285820401216578964 [56]
W(4,79) =      4802184275992258467685155546646227537411153018593911630510 [57]
W(4,80) =     26328519112217101072702784576501163145680120126686374204632 [58]
W(4,81) =    144349087582472991120586287593712757432209074233139096049251 [59]
W(4,82) =    791410219355015665893496929969521863582820793544444873396002 [59]
W(4,83) =   4338996150160658424307562918695547774468533439918803080849363 [60]
W(4,84) =  23789037759017784414170843912582277633825901413761601754767642 [61]
W(4,85) = 130426093482249307737692978033716384106914364975908009829969139 [62]
W(4,86) = 715075827503448965720246577184436431183396047561961739178927508 [62]

W(5, 1) =                                                               1 [ 0]
W(5, 2) =                                                              16 [ 1]
W(5, 3) =                                                             125 [ 2]
W(5, 4) =                                                             976 [ 2]
W(5, 5) =                                                            8512 [ 3]
W(5, 6) =                                                           79384 [ 4]
W(5, 7) =                                                          752061 [ 5]
W(5, 8) =                                                         7110272 [ 6]
W(5, 9) =                                                        67005561 [ 7]
W(5,10) =                                                       630588698 [ 8]
W(5,11) =                                                      5933085772 [ 9]
W(5,12) =                                                     55827318685 [10]
W(5,13) =                                                    525343024814 [11]
W(5,14) =                                                   4943673540576 [12]
W(5,15) =                                                  46521924780255 [13]
W(5,16) =                                                 437788749723725 [14]
W(5,17) =                                                4119750109152730 [15]
W(5,18) =                                               38768318191017931 [16]
W(5,19) =                                              364823700357765771 [17]
W(5,20) =                                             3433121323699285343 [18]
W(5,21) =                                            32306898830469680384 [19]
W(5,22) =                                           304019468350280601960 [20]
W(5,23) =                                          2860931888452842047170 [21]
W(5,24) =                                         26922391858409506569346 [22]
W(5,25) =                                        253349332040459400463497 [23]
W(5,26) =                                       2384107785665647075602841 [24]
W(5,27) =                                      22435306570786253414376286 [25]
W(5,28) =                                     211124255357254403803629035 [26]
W(5,29) =                                    1986754718952099249909705783 [27]
W(5,30) =                                   18696072161887025777926174219 [28]
W(5,31) =                                  175936722811233879876002194230 [29]
W(5,32) =                                 1655627458297809088928561146142 [30]
W(5,33) =                                15580046262485573366602344892679 [31]
W(5,34) =                               146613805131471376745432664782147 [32]
W(5,35) =                              1379688320110304714211546245580297 [33]
W(5,36) =                             12983360325051785394010690753755824 [34]
W(5,37) =                            122178062155844407644383553938446977 [35]
W(5,38) =                           1149739243033589421875218557417568767 [36]
W(5,39) =                          10819457303924976036891705581751397328 [37]
W(5,40) =                         101814961140745872340842375048060231946 [38]
W(5,41) =                         958115182757920062930691301192563148820 [38]
W(5,42) =                        9016206391929460524310669044081210076821 [39]
W(5,43) =                       84845725404196114901576363520487874379017 [40]
W(5,44) =                      798428608046062434880163743522733414588407 [41]
W(5,45) =                     7513498636607157729408193670863232681920390 [42]
W(5,46) =                    70704708214864950083606947513647345537262118 [43]
W(5,47) =                   665356580939853752053276134819021418639396968 [44]
W(5,48) =                  6261243288843657065357857850224698884802176769 [45]
W(5,49) =                 58920537716352105174088000259119255665492079697 [46]
W(5,50) =                554463323757096922520674423477990122778083506296 [47]
W(5,51) =               5217698094877483315102286426467829236802676569144 [48]
W(5,52) =              49100404378080664911893537773290991329131770825243 [49]
W(5,53) =             462052358387296083996390535982583964471803842259664 [50]
W(5,54) =            4348077874213379753210582213331364334190995696757907 [51]
W(5,55) =           40916967216033474439392434831868055709765577197806606 [52]
W(5,56) =          385043289147814764671944162318304565362251761032381066 [53]
W(5,57) =         3623395002249142164514054390586296632495523620963741656 [54]
W(5,58) =        34097442319749028372310159050866684931685088503458994545 [55]
W(5,59) =       320869121922101159215665175346923664922094331427493512823 [56]
W(5,60) =      3019493146658339323244254859288829893628462954690802111431 [57]
W(5,61) =     28414509966247661726751143332414281043429575467454819233066 [58]
W(5,62) =    267390696851064779318845260078933906991615238282107051472837 [59]
W(5,63) =   2516242048426211709667710768894843343869700246318618288763345 [60]
W(5,64) =  23678737221716939195460736230952396136448836826924249211488495 [61]
W(5,65) = 222825382306047707107147110468051060454712279103671557540920124 [62]

W(6, 1) =                                                               1 [ 0]
W(6, 2) =                                                              32 [ 1]
W(6, 3) =                                                             414 [ 2]
W(6, 4) =                                                            5382 [ 3]
W(6, 5) =                                                           79384 [ 4]
W(6, 6) =                                                         1262816 [ 6]
W(6, 7) =                                                        20562673 [ 7]
W(6, 8) =                                                       336067810 [ 8]
W(6, 9) =                                                      5493330332 [ 9]
W(6,10) =                                                     89803472792 [10]
W(6,11) =                                                   1468381290905 [12]
W(6,12) =                                                  24012936982592 [13]
W(6,13) =                                                 392716580997352 [14]
W(6,14) =                                                6422777815120738 [15]
W(6,15) =                                              105043595925333255 [17]
W(6,16) =                                             1717976646746942760 [18]
W(6,17) =                                            28097347987645295129 [19]
W(6,18) =                                           459529700981496318610 [20]
W(6,19) =                                          7515570007661530339293 [21]
W(6,20) =                                        122916531487036730334780 [23]
W(6,21) =                                       2010289859051351461718841 [24]
W(6,22) =                                      32878127252299185360551934 [25]
W(6,23) =                                     537719101299048122399217869 [26]
W(6,24) =                                    8794352250919537166665750722 [27]
W(6,25) =                                  143830917261013287829855929053 [29]
W(6,26) =                                 2352342978307852368872254574110 [30]
W(6,27) =                                38472378495706095194731534070125 [31]
W(6,28) =                               629212627935457125950913558054726 [32]
W(6,29) =                             10290721464101586255448326254366900 [34]
W(6,30) =                            168303914369885958800758915526318474 [35]
W(6,31) =                           2752596860300114955964065429361536989 [36]
W(6,32) =                          45018498254837163421818726088041699166 [37]
W(6,33) =                         736273885345044284085688553892457204990 [38]
W(6,34) =                       12041699640279371326340375422350041719446 [40]
W(6,35) =                      196941020336151050199143987475335247318191 [41]
W(6,36) =                     3220954404252653214796052011262240269847376 [42]
W(6,37) =                    52678447875240888447093955411712504021593807 [43]
W(6,38) =                   861551739720563513304275975426292082337631174 [44]
W(6,39) =                 14090608781288751611582325118090142798190478571 [46]
W(6,40) =                230450763051941815978795941071686604125891198442 [47]
W(6,41) =               3769003526784804976816338101329440702079133017666 [48]
W(6,42) =              61641746795668086369885223391335280193549793452454 [49]
W(6,43) =            1008145766120479656207584228935637479155797947389803 [51]
W(6,44) =           16488142185777157345793212901099082094584264689337958 [52]
W(6,45) =          269662227303264323330785234671779693565559562284410182 [53]
W(6,46) =         4410303842290033896172439105038616399715156984924650402 [54]
W(6,47) =        72130161409086529608951854829851816002712963801157839787 [55]
W(6,48) =      1179682935903881340573479585181430128337758733576064749582 [57]
W(6,49) =     19293618675966098340238272567572020098236154654850930308513 [58]
W(6,50) =    315545567613362204775242670274937424600545170340425654393866 [59]
W(6,51) =   5160722149260222882522006042304141173305206572051170726255899 [60]
W(6,52) =  84403191917113277982043589954202883741227100622483260510931370 [61]

W(7, 1) =                                                               1 [ 0]
W(7, 2) =                                                              64 [ 1]
W(7, 3) =                                                            1369 [ 3]
W(7, 4) =                                                           29739 [ 4]
W(7, 5) =                                                          752061 [ 5]
W(7, 6) =                                                        20562673 [ 7]
W(7, 7) =                                                       575780564 [ 8]
W(7, 8) =                                                     16230458696 [10]
W(7, 9) =                                                    459133264944 [11]
W(7,10) =                                                  13021391001373 [13]
W(7,11) =                                                 369886375079581 [14]
W(7,12) =                                               10516022622412960 [16]
W(7,13) =                                              299104709252534435 [17]
W(7,14) =                                             8509249843020438582 [18]
W(7,15) =                                           242108399244641421526 [20]
W(7,16) =                                          6888987223916209602814 [21]
W(7,17) =                                        196026708756588099010848 [23]
W(7,18) =                                       5578053961718932115597017 [24]
W(7,19) =                                     158728232358841952835386863 [26]
W(7,20) =                                    4516767757061854076293758285 [27]
W(7,21) =                                  128529392946828650026263986056 [29]
W(7,22) =                                 3657444470628097260059276129911 [30]
W(7,23) =                               104076657765409856754477709745139 [32]
W(7,24) =                              2961618386677007033270145520935213 [33]
W(7,25) =                             84276199971056311916655735952493374 [34]
W(7,26) =                           2398174816704752797880344822184042261 [36]
W(7,27) =                          68242787100453955377302714478054648107 [37]
W(7,28) =                        1941926041419538974702064193716647084705 [39]
W(7,29) =                       55259712700067457288109534327783675144232 [40]
W(7,30) =                     1572477945946381248285033609383989297686043 [42]
W(7,31) =                    44746647790998627587080956886160310005281831 [43]
W(7,32) =                  1273316740806483427313381046105817307586846279 [45]
W(7,33) =                 36233675692409546441709234287707870915534849271 [46]
W(7,34) =               1031070442214508266274915132931315543866586325969 [48]
W(7,35) =              29340281846986110522947656665859832241205885310805 [49]
W(7,36) =             834911082471996636214835976970788344507895569395788 [50]
W(7,37) =           23758344222309014069307120706577255213069748966360167 [52]
W(7,38) =          676070700298502294742505635302397334395963883959746576 [53]
W(7,39) =        19238360532925369429324082506655154157817860293909785086 [55]
W(7,40) =       547449424796172337585875033769696541620043771522378195680 [56]
W(7,41) =     15578295884357565376851837864957286643179170407188712931097 [58]
W(7,42) =    443298123387175906645334539013271126629214319094846266510703 [59]
W(7,43) =  12614552172957266162754921884082628317178368107658852162942435 [61]
W(7,44) = 358961426023118212075880447781043309190930699711987637234825422 [62]

W(8, 1) =                                                               1 [ 0]
W(8, 2) =                                                             128 [ 2]
W(8, 3) =                                                            4522 [ 3]
W(8, 4) =                                                          163496 [ 5]
W(8, 5) =                                                         7110272 [ 6]
W(8, 6) =                                                       336067810 [ 8]
W(8, 7) =                                                     16230458696 [10]
W(8, 8) =                                                    789360053252 [11]
W(8, 9) =                                                  38603590450777 [13]
W(8,10) =                                                1896597558069886 [15]
W(8,11) =                                               93467039444263314 [16]
W(8,12) =                                             4614618337661429084 [18]
W(8,13) =                                           228073604373821861695 [20]
W(8,14) =                                         11279473113082310507710 [22]
W(8,15) =                                        558044223844519272676141 [23]
W(8,16) =                                      27615252735468871470811414 [25]
W(8,17) =                                    1366753277825934668137076421 [27]
W(8,18) =                                   67649988491247877009826179754 [28]
W(8,19) =                                 3348630780028864342606939528796 [30]
W(8,20) =                               165760096281759281320462505161838 [32]
W(8,21) =                              8205416825208627070745138116189675 [33]
W(8,22) =                            406187052394187392981104614349928914 [35]
W(8,23) =                          20107328500402658550260618474407661259 [37]
W(8,24) =                         995369653976679229916147394744461631862 [38]
W(8,25) =                       49273731974940819821278920458508202878484 [40]
W(8,26) =                     2439198484184433596893476728623799086885414 [42]
W(8,27) =                   120747792943791055034522895801327511963432478 [44]
W(8,28) =                  5977388544335051496416595326191182018457058058 [45]
W(8,29) =                295899279840505530094389836812405244881667389490 [47]
W(8,30) =              14647935233496589129036456010199652559263277836688 [49]
W(8,31) =             725118462492647692988084722278893003659985608641076 [50]
W(8,32) =           35895627062566388083935009671515920695904074372155822 [52]
W(8,33) =         1776945646150852533075668101575409311770674152575813774 [54]
W(8,34) =        87964361270723890578982618813196559425922915921058696490 [55]
W(8,35) =      4354510778019048249754424714679316431911711590512399671822 [57]
W(8,36) =    215561893595098859119198477042428878229923922076695648446616 [59]
W(8,37) =  10670987531642199733767344184779455758812607825620208530754289 [61]
W(8,38) = 528247239655076022639138626026596710475391145777374640581299248 [62]

W(9, 1) =                                                               1 [ 0]
W(9, 2) =                                                             256 [ 2]
W(9, 3) =                                                           14934 [ 4]
W(9, 4) =                                                          896476 [ 5]
W(9, 5) =                                                        67005561 [ 7]
W(9, 6) =                                                      5493330332 [ 9]
W(9, 7) =                                                    459133264944 [11]
W(9, 8) =                                                  38603590450777 [13]
W(9, 9) =                                                3266598486981642 [15]
W(9,10) =                                              278065795198022522 [17]
W(9,11) =                                            23771282378421890188 [19]
W(9,12) =                                          2037735840792349459408 [21]
W(9,13) =                                        174984693167026909838637 [23]
W(9,14) =                                      15043327348304711749778561 [25]
W(9,15) =                                    1294228007560478044464188014 [27]
W(9,16) =                                  111401146002669479384505121978 [29]
W(9,17) =                                 9591952169949534737730355918193 [30]
W(9,18) =                               826065710868247080536084489862479 [32]
W(9,19) =                             71150993564506741272339856061929630 [34]
W(9,20) =                           6128943783062333876582603620198505730 [36]
W(9,21) =                         527977306544125135454395294504563125572 [38]
W(9,22) =                       45484259345514485351068027777025301545897 [40]
W(9,23) =                     3918479546539241769759398250012944054510834 [42]
W(9,24) =                   337583285634430860804615268053379664145921966 [44]
W(9,25) =                 29083641153528380527459094396248923993016340645 [46]
W(9,26) =               2505645019079261238922247609702313958466238144018 [48]
W(9,27) =             215869961362426587102675423311604136568954170008975 [50]
W(9,28) =           18597994903505429719479007252265636491707991905764589 [52]
W(9,29) =         1602288968361241067618077777520322003452542320827440669 [54]
W(9,30) =       138043539684264894073780318033790199928833447987641095721 [56]
W(9,31) =     11893006976190049707367325260692275966419374243112121329050 [58]
W(9,32) =   1024630981725134896354010679789518697887157202045987313308025 [60]
W(9,33) =  88276161108401674474605358278807467284382800622036425378560849 [61]

W(10, 1) =                                                               1 [ 0]
W(10, 2) =                                                             512 [ 2]
W(10, 3) =                                                           49322 [ 4]
W(10, 4) =                                                         4913258 [ 6]
W(10, 5) =                                                       630588698 [ 8]
W(10, 6) =                                                     89803472792 [10]
W(10, 7) =                                                  13021391001373 [13]
W(10, 8) =                                                1896597558069886 [15]
W(10, 9) =                                              278065795198022522 [17]
W(10,10) =                                            41044208702632496804 [19]
W(10,11) =                                          6089404268345231341903 [21]
W(10,12) =                                        906580953466894744400498 [23]
W(10,13) =                                     135288601620380186876749340 [26]
W(10,14) =                                   20221960762421426978177915020 [28]
W(10,15) =                                 3026065681121995657331049388171 [30]
W(10,16) =                               453185482144046050100591881851156 [32]
W(10,17) =                             67906377136138785860332269950994237 [34]
W(10,18) =                          10179082557233479970303228344175800420 [37]
W(10,19) =                        1526228176156908710986332283696378704075 [39]
W(10,20) =                      228880101898341785124844342319833252034368 [41]
W(10,21) =                    34328133980704869751128957847492962027086339 [43]
W(10,22) =                  5149075772858876772566186868242636225227785322 [45]
W(10,23) =                772384965220063796353652440454914953517385724185 [47]
W(10,24) =             115865960644277193428781102926511290847321363256944 [50]
W(10,25) =           17381609739197519526053951623488735699982848662415477 [52]
W(10,26) =         2607548759432666745290988842316475496639723282284945054 [54]
W(10,27) =       391183572947515020996899765778041431530387519057393739900 [56]
W(10,28) =     58685758842883064736798327346461808492522248662328214646778 [58]
W(10,29) =   8804152510176938170406818598810538332506462124299587477196407 [60]

W(11, 1) =                                                               1 [ 0]
W(11, 2) =                                                            1024 [ 3]
W(11, 3) =                                                          162899 [ 5]
W(11, 4) =                                                        26932712 [ 7]
W(11, 5) =                                                      5933085772 [ 9]
W(11, 6) =                                                   1468381290905 [12]
W(11, 7) =                                                 369886375079581 [14]
W(11, 8) =                                               93467039444263314 [16]
W(11, 9) =                                            23771282378421890188 [19]
W(11,10) =                                          6089404268345231341903 [21]
W(11,11) =                                       1568758030464750013214100 [24]
W(11,12) =                                     405769626908332575325415852 [26]
W(11,13) =                                  105254779101613880966774835935 [29]
W(11,14) =                                27359159340297390348383198021785 [31]
W(11,15) =                              7122279869660711072637404183374811 [33]
W(11,16) =                           1856142093992389592553419995975884802 [36]
W(11,17) =                         484113693792985461605880230438107747321 [38]
W(11,18) =                      126337279423591171925726036967916419191362 [41]
W(11,19) =                    32983315991883281531834136292768362227121240 [43]
W(11,20) =                  8613620105239316668434905938544164592578613427 [45]
W(11,21) =               2249933301163550920289224253384142773479790084977 [48]
W(11,22) =             587787195612441867174772624756700112451411013427747 [50]
W(11,23) =          153574263854157949295238694815398240054569577197118620 [53]
W(11,24) =        40128336079541729364546167294577728230493220863041951121 [55]
W(11,25) =     10485969151009714664954623915756804637031982438632780525770 [58]
W(11,26) =   2740209439452757438166514486341433373341552521899494619474776 [60]
W(11,27) = 716096746061120221627388772630197996466023391473373548188553526 [62]

W(12, 1) =                                                               1 [ 0]
W(12, 2) =                                                            2048 [ 3]
W(12, 3) =                                                          538020 [ 5]
W(12, 4) =                                                       147657866 [ 8]
W(12, 5) =                                                     55827318685 [10]
W(12, 6) =                                                  24012936982592 [13]
W(12, 7) =                                               10516022622412960 [16]
W(12, 8) =                                             4614618337661429084 [18]
W(12, 9) =                                          2037735840792349459408 [21]
W(12,10) =                                        906580953466894744400498 [23]
W(12,11) =                                     405769626908332575325415852 [26]
W(12,12) =                                  182413291514248049241470885236 [29]
W(12,13) =                                82268836815726830679889460105219 [31]
W(12,14) =                             37193725396722922783032448209106010 [34]
W(12,15) =                          16846202313728151287180674479245984129 [37]
W(12,16) =                        7640727338151282172126324003660331010496 [39]
W(12,17) =                     3469100388909590205715294900257993390563552 [42]
W(12,18) =                  1576284772533300863581687076502683539033501838 [45]
W(12,19) =                716642916765212333854968453908978776402603450901 [47]
W(12,20) =             325954856930969667989728262086849968817540859838588 [50]
W(12,21) =          148303348279908186931630991269722589449346216313412255 [53]
W(12,22) =        67491295363568713863906352429499974689304367833264451136 [55]
W(12,23) =     30720012839495700528737852549579220081913228189938181470886 [58]
W(12,24) =  13984666944967076917330642396948362451680659502211894069905088 [61]

----- snip -----
Later I could add:
----- snip -----

##	Computed on an SGI IRIX workstation (R4400, 45 MHz)
##	@ 20.May.1995

NUM_WORDS        =   8
sizeof(Number  ) =  32
sizeof(Umap    ) = 256
sizeof(DUUdef  ) =  52
sizeof(DIUUdef ) =  92

TIME(13,13)	real 1:07:39.69	user 1:06:44.30	sys  6.15
TIME(13,20)	real 1:43:49.92	user 1:42:31.51	sys  9.23
Memory:		4.45 MB

W(13, 1) =                                                        1
W(13, 2) =                                                     4096
W(13, 3) =                                                  1776961
W(13, 4) =                                                809563548
W(13, 5) =                                             525343024814
W(13, 6) =                                          392716580997352
W(13, 7) =                                       299104709252534435
W(13, 8) =                                    228073604373821861695
W(13, 9) =                                 174984693167026909838637
W(13,10) =                              135288601620380186876749340
W(13,11) =                           105254779101613880966774835935
W(13,12) =                         82268836815726830679889460105219
W(13,13) =                      64528039343270018963357185158482118
W(13,14) =                   50750325376483472808082060840001661852
W(13,15) =                39998656352715392458211293438906385119970
W(13,16) =             31576310786416112227691519471158189108721865
W(13,17) =          24958818638415495836841739030575979692614256862
W(13,18) =       19747257240041545726918596816733037839421460249574
W(13,19) =    15635505553916576127200056066433174366794262435841915
W(13,20) = 12386943669551230803145944623665136996719815206609431897

----- snip -----
From: Heiner Marxen 
Subject: W(14,20) and W(15,20)
To: sfinch@.com (Steven Finch)
Date: Fri, 13 Sep 96 2:29:33 +0200
Cc: nl3242t@nlccmail.snads.philips.nl

...I currently have access to a faster and larger machine... 

----- snip -----
 
## Computed on HP9000/819 
## Tue Sep 10 1996

NUM_WORDS        =   8
sizeof(Number  ) =  32
sizeof(Umap    ) = 256
sizeof(DUUdef  ) =  52
sizeof(DIUUdef ) =  92

TIME(14,20)	real 3:32:42.8 user 3:31:55.9 sys 13.2
Memory:		12.088 MB (196938 slots)

W(14, 1) =                                                            1
W(14, 2) =                                                         8192
W(14, 3) =                                                      5868904
W(14, 4) =                                                   4438573234
W(14, 5) =                                                4943673540576
W(14, 6) =                                             6422777815120738
W(14, 7) =                                          8509249843020438582
W(14, 8) =                                      11279473113082310507710
W(14, 9) =                                   15043327348304711749778561
W(14,10) =                                20221960762421426978177915020
W(14,11) =                             27359159340297390348383198021785
W(14,12) =                          37193725396722922783032448209106010
W(14,13) =                       50750325376483472808082060840001661852
W(14,14) =                    69450664761521361664274701548907358996488
W(14,15) =                 95262966612892063156874389817827456761021038
W(14,16) =             130909894803647282919756617695448131233103278776
W(14,17) =          180157634504083966622313860098254618575340454467000
W(14,18) =       248216244130010747317113802567503531005799632575522258
W(14,19) =    342293437654879699827408687514517113078005631286155981913
W(14,20) = 472360617372958252809412594672907599431812810074227874196332

## Computed on HP9000/819 
## Wed Sep 11 1996

NUM_WORDS        =   8
sizeof(Number  ) =  32
sizeof(Umap    ) = 256
sizeof(DUUdef  ) =  52
sizeof(DIUUdef ) =  92

TIME(15,20)	real 16:34:22.6 user 16:29:16.5 sys 1:07.6
Memory:		33.357 MB (542895 slots)

W(15, 1) =                                                                 1
W(15, 2) =                                                             16384
W(15, 3) =                                                          19383672
W(15, 4) =                                                       24335048679
W(15, 5) =                                                    46521924780255
W(15, 6) =                                                105043595925333255
W(15, 7) =                                             242108399244641421526
W(15, 8) =                                          558044223844519272676141
W(15, 9) =                                      1294228007560478044464188014
W(15,10) =                                   3026065681121995657331049388171
W(15,11) =                                7122279869660711072637404183374811
W(15,12) =                            16846202313728151287180674479245984129
W(15,13) =                         39998656352715392458211293438906385119970
W(15,14) =                      95262966612892063156874389817827456761021038
W(15,15) =                  227449714676812739631826459327989863387613323440
W(15,16) =               544153218633291055333005955373503380344455231720156
W(15,17) =           1303949463726800479567050586474874803419007600650103638
W(15,18) =        3128711042823236250260024108446485968800356758589577016646
W(15,19) =     7514901779717963705978192506823563289469102955658338970126326
W(15,20) = 18065251836996975790472937289751595742358854920978934398187863788

----- snip -----

Please, let me be informed of additional results.  

Best regards,
--
Heiner Marxen			heiner@drb.insel.de

Return to Self-Avoiding Walks of a Rook on a Chessboard.

Copyright © 1995-2001 by Steven Finch.
All rights reserved.