Number of Knight's Tours
 ------------------------



below I give some counts for the numbers of knight's tours
on rectangular boards.
Most numbers are unconfirmed and in that case some digits are missing.
When someone sends the complete number to sterten@aol.com
subject line:#tours {series} (recommended) or I find it published elsewhere,
and if the number matches with the previous unconfirmed number,
then the number here will be completed and the sender
acknowledged (if he/she wants).
So, all numbers without missing digits (".") here are confirmed.
You can also submit counts from new {series}. (except the obvious ones ;-))
In that case I will post it here but replace some digits with "." 
until the number is confirmed.
This way I want to encourage people to verify the counts, since such
computations are sometimes erraneous.

estimated probability that all numbers on this page are correct: 20%
estimated probability that >50% of the numbers on this page are correct: 80%







(1) : number of closed knight's tours (Hamilton cycles) on rectangular boards:
      ------------------------------------------------------------------------
a cycle and its reversed cycle are considered equal and are only counted once


ktc3*4:0 Euler A070030
ktc3*6:0 Euler
ktc3*8:0 (Euler)
ktc3*10:16 Bergholt+Moore
ktc3*12:176 Elkies,Knuth
ktc3*14:1536 Elkies,Knuth
ktc3*16:15424 Elkies,Knuth
ktc3*18:147728 Elkies,Knuth
ktc3*20:1448416 Elkies,Knuth
ktc3*50:960786342292812728320 Elkies,Knuth
ktc3*100:4861943174181138724903568742746024250554974208 Elkies,Knuth
periodic for b>10(97,84)
ktc(3,2*b)~9.731220709786^b*0.000189864488
generating function see below


ktc4*3:0 Euler,Sainte Marie
ktc4*4:0 Euler,Sainte Marie
ktc4*5:0 Euler,Sainte Marie
ktc4*6:0 Euler,Sainte Marie
...
period 8(380)



ktc5*4:0 Euler,Sainte Marie
ktc5*6:8 
ktc5*8:442.2
ktc5*10:13311..8
ktc5*12:455770...2
ktc5*14:149513551...4
ktc5*16:4918570357....0
ktc5*18:1615141015685....6
ktc5*20:530348536620122....8
ktc5*50:29480822008610165640366673187145643815025394715094471....2
ktc5*100:23868230600048119402190619954877805613239208872251753676194314337546391820173818908915360509360869243566319756436840....6
period 8(22645,20823)
ktc(5,b)~328.345618569^b*0.00000364132089



ktc6*3:0 Euler
ktc6*4:0 Euler,Sainte Marie
ktc6*5:8 (Euler)
ktc6*6:9862 Duby,A001230
ktc6*7:1067..8
ktc6*8:55488..2
ktc6*9:337496...0
ktc6*10:23918724...4
ktc6*11:153601345....6
ktc6*12:9647306066....6
ktc6*13:619896834454....8
ktc6*14:40057167171822....6
ktc6*15:2559678925530306....0
ktc6*16:163789985062246970....8
ktc6*17:10505046872496837717....2
ktc6*18:673514496747714712161....6
ktc6*19:43141512467521660997284....8
ktc6*20:2764535221472733092540297....6
ktc6*50:4402880176728914497973505586882321945393721588899426578266508958286969588777349....6
ktc6*100:9561641627334426081859262175378699466738316912784683032719985964136223302385010663468523463582548972199336614293336291868092850766481134130436939650008801526046883208979....0
period 10(509681)


ktc7*4:0 Euler,Sainte Marie
ktc7*6:1067..8
ktc7*8:3452443...6
ktc7*10:12500632799....4
ktc7*12:383504272051946....4
ktc7*14:12549349863992373462....4
ktc7*16:401577731886007946943660....6
ktc7*18:12931534238966885713142110862....6
ktc7*20:415756893783157956017491946540169....4
ktc7*50:
ktc7*100:
period 8(10189911,9062913)


ktc8*3:0 Euler
ktc8*4:0 Euler,Sainte Marie
ktc8*5:442.2
ktc8*6:55488..2
ktc8*7:3452443...6
ktc8*8:13267364410352 McKay(1997),Loebbing+Wegener,A001230
ktc8*9:
...
ktc8*100: I estimate that this should only take some days on
       a 10GHz computer with 16GB Ram which can do 100 million
       Ram-accesses per second (non-consecutive,badly cached).


(2) total number of open tours (Hamilton paths)
    -------------------------------------------
a path and it's reversed path are considered different and are counted
twice. So each closed tour on an a*b board gives a*b*2 open tours.


kto3*3:0 Euler
kto3*4:16 Euler
kto3*5:0 Euler,Willis
kto3*6:0 Euler,Willis
kto3*7:104 Papa
kto3*8:792 Jelliss
kto3*9:1120 Knuth
kto3*10:6096 Knuth
kto3*11:21344 Knuth
kto3*12:114496 Knuth
kto3*13:257728 Knuth
kto3*14:1292544 Knuth
kto3*15:3677568 Knuth
kto3*16:17269264 Knuth (this number is given on Jelliss' page)
kto3*16:17273..0
kto3*17:46801984 Knuth
kto3*18:211731..6
kto3*19:611507..0
kto3*20:264569...4
kto3*50:432428932783081531521....0
kto3*100:343425703207524821250421224765212384956644658619....6
periodic for b>11 (617,651) , size of TM,b even:145  b odd:145
kto(3,b)~0.055785482*3.450592112^b
generating function see below


kto4*3:16 Euler
kto4*4:0 Euler
kto4*5:164 Sainte-Marie
kto4*6:1488 Sainte-Marie
kto4*7:12756 Sainte-Marie
kto4*8:62176 Sainte-Marie
kto4*9:379376 Kraitchik
kto4*10:2426224 Jelliss
kto4*11:13367704 A079137 Kraitchik,Poenitz
kto4*12:72972656 A079137
kto4*13:402564940 A079137
kto4*14:2167170608 A079137
kto4*15:11412234916 A079137
kto4*16:59638462576 A079137
kto4*17:308861005448 A079137
kto4*18:1581575598752 A079137
kto4*19:8029891390392 A079137
kto4*20:40482609620976 A079137
kto4*50:86251962723305153855310064804....6
kto4*100:69491765442137201891403252215896677256770171634023479037828301....4
period 8(4009,3430)
kto(4,b)~4.476415^b*68.725

kto5*3:0 Euler,Willis
kto5*4:164 Sainte-Marie
kto5*5:1728 Planck
kto5*6:37568 Poenitz,A083386
kto5*7:1245736 A083386
kto5*8:36122108 A083386
kto5*9:529791280 A083386
kto5*10:15772235644 A083386
kto5*11:256823853904 A083386
kto5*12:7223647288012 A083386
kto5*13:112696196976792 A083386
kto5*14:3096568872305596 A083386
kto5*15:49071820312352200 A083386
kto5*16:1300913780682552676 A083386
kto5*17:20729832217975340048 A083386
kto5*18:534852062807466925252 A083386
kto5*19:86193325094047835....2
kto5*20:2166143036521377572....4
kto5*50:1268476994530886444449901636308258263893219122665958838445....6
kto5*100:24216187760089374193458955425176851797445972329524604481158568470512005368180569624224160397113222689179667003910459596663....6
period 8(169136,184020)   [period 142858,161942]

kto6*3:0 Euler,Willis
kto6*4:1488 Sainte-Marie
kto6*5:37568 Poenitz,A083386
kto6*6:6637..0
kto6*7:779938..2
kto6*8:4992978...8
kto6*9:354126241...4
kto6*10:2876553146....6
kto6*11:213360309842....6
kto6*12:15279118248042....2
kto6*13:1107645511894577....6
kto6*14:80169122266371702....8
kto6*15:5706593169560165423....2
kto6*16:404066490116184960650....6
kto6*17:28516950952826652121631....6
kto6*18:2002074563238290585825439....6
kto6*19:13981448064535457862610407441308 
kto6*20:9727546085520001596812425427....0
kto6*50:
kto6*100:
period 10(3729317), 1804360(4sym,b even)

kto7*3:104 Papa
kto7*4:12756 Sainte-Marie
kto7*5:1245736 A083386
kto7*6:779938..2
kto7*7:16557521...0
kto7*8:
kto7*9:
kto7*10:

kto8*8:~1.8e16
kto8*9:





(3) number of open knight's tours on rectangular boards from
    lower left corner to lower right corner
    ---------------------------------------------------------
in our notation an a*b rectangle has height b and width a, 
the two lower corners are a-1 units apart


ktu3*3:0 Euler
ktu3*5:0 Euler,Willis
ktu3*7:0 Papa
ktu3*9:.6
ktu3*11:1.4
ktu3*13:13.4
ktu3*15:136.2
ktu3*17:130..2
ktu3*19:1289..0
ktu3*21:12462..0
ktu3*49:8532874486364687....8
ktu3*99:43179585430870789238399271416613163215015....0
period 84,97

ktu4*3:0 Euler
ktu4*4:0 Euler
ktu4*5:12 Sainte Marie
ktu4*6:64 Sainte Marie
ktu4*7:436 Sainte Marie
ktu4*8:1860 Sainte Marie
ktu4*9:92.6
ktu4*10:505.2
ktu4*11:240..0
ktu4*12:1137..4
ktu4*13:5551..6
ktu4*14:26591..0
ktu4*15:125098..6
ktu4*16:589686..2
ktu4*17:277371...8
ktu4*18:1294926...4
ktu4*19:6024935...2
ktu4*20:27979160...6
ktu4*50:148590255165383530267187762....0
ktu4*100:58351689381930224487911166761481677849213879094645023513265....2
period 1372

ktu5*3:.
ktu5*4:.
ktu5*5:.0
ktu5*7:270.8
ktu5*9:8060..0
ktu5*11:275663...4
ktu5*13:89302813...2
ktu5*15:2944074731....8
ktu5*17:965305830411....6
ktu5*19:317074133648516....0
ktu5*21:104098775952812844....4
ktu5*49:17623479918934766334364659045708363740041511485277738....8
ktu5*99:14268302374935211816313814786594225939897767124647878439586907881808311955516255224073802683909881248821512345897618....8
period 20823 22645

ktu6*3:.
ktu6*4:.4
ktu6*5:10.2
ktu6*6:836.6
ktu6*7:9088..8
ktu6*8:508075..2
ktu6*9:2977425...6
ktu6*10:201403413...6
ktu6*11:1327051576....6
ktu6*12:83187144917....4
ktu6*13:5318179041058....8
ktu6*14:343109193020458....2
ktu6*15:21991835344631160....8
ktu6*16:1406036568745541484....8
ktu6*17:90145348749308529299....0
ktu6*18:5779904615121184161558....4
ktu6*19:370316506603888884393065....6
ktu6*20:23726741708539968082724418....0
ktu6*50:
ktu6*100:
period 509681

ktu7*3:.
ktu7*5:385.4
ktu7*7:259733...2
ktu7*9:622135320....8
period ?

ktu8*3:.4
ktu8*4:18.2
ktu8*5:769..4
ktu8*6:485667..2
ktu8*7:40486484...4
ktu8*8:1524879908....0



(4) number of open knight's tours on rectangular boards from
    lower left corner to upper left corner
    ---------------------------------------------------------
in our notation an a*b rectangle has height b and width a, 
the two left corners are b-1 units apart


ktr3*3:.
ktr3*4:.
ktr3*5:.
ktr3*6:.
ktr3*7:.
ktr3*8:.4
ktr3*9:.0
ktr3*10:.0
ktr3*11:4.4
ktr3*12:18.4
ktr3*13:54.6
ktr3*14:180.8
ktr3*15:670.6
ktr3*16:236..8
ktr3*17:790..4
ktr3*18:2719..6
ktr3*19:9517..4
ktr3*20:32886..2
ktr3*50:4489254651408401308....6
ktr3*100:3522536450285799535879442542689910199557272538....8

ktr4*3:0 
ktr4*4:0 
ktr4*6:.4
ktr4*8:18.2
ktr4*10:504.4
ktr4*12:1138..0
ktr4*14:26365..4
ktr4*16:582006..2
ktr4*18:1269740...6
ktr4*20:27254539...2
ktr4*50:122796642856541434732385390....8
ktr4*100:28694773539998675516957478028277385612012083024563369745460....6

ktr5*3:0 
ktr5*4:.2
ktr5*5:.0
ktr5*6:10.2
ktr5*7:385.4
ktr5*8:769..4
ktr5*9:11967..2
ktr5*10:244935..6
ktr5*11:499397...2
ktr5*12:9621158...0
ktr5*13:178485558...8
ktr5*14:348645706....8
ktr5*15:6762433760....0
ktr5*16:130416531032....4
ktr5*17:2493821987496....0
ktr5*18:48146893258882....6
ktr5*19:928336311602862....8
ktr5*20:17892413449908990....0
ktr5*50:6198104730494490586086268302262378876649098177852763479....2
ktr5*100:106069649690887316223132926812886791003687773798078123482220207497593551505166984227980616444856727409480665770481608261....2

ktr6*4:.4
ktr6*6:836.6
ktr6*8:485667..2
ktr6*10:181000170...6
ktr6*12:72303328354....4

ktr7*3:.
ktr7*4:4.6
ktr7*5:270.8
ktr7*6:9088..8
ktr7*7:259733...2
ktr7*8:40486484...4
ktr7*9:
ktr7*10:
ktr7*11:


ktr8*4:1860 Sainte Marie
ktr8*6:508075..2
ktr8*8:1524879908....0




(5) number of (open) tours on rectangular board 
   from one fixed corner to opposite corner


ktd3*3:0 
ktd3*4:1 
ktd3*5:0 
ktd3*6:0 
ktd3*7:0 
ktd3*8:.5
ktd3*9:.0
ktd3*10:.0
ktd3*11:4.4
ktd3*12:18.5
ktd3*13:54.6
ktd3*14:180.8
ktd3*15:670.6
ktd3*16:236..9
ktd3*17:790..4
ktd3*18:2719..6
ktd3*19:9517..4
ktd3*20:32886..3
ktd3*50:4489254651408401308....6
ktd3*100:3522536450285799535879442542689910199557272538....9

ktd4*3:1 
ktd4*5:.2
ktd4*7:4.1
ktd4*9:93.2
ktd4*11:240..1
ktd4*13:5519..2
ktd4*15:123882..7
ktd4*17:272727...3
ktd4*19:5889951...3
ktd4*25:5557711637....1
ktd4*49:27474595595865217259950787....0
ktd4*99:6488546485314432592074535089319136565402737701741939607173....9

ktd5*3:0 
ktd5*4:.2
ktd5*5:.6
ktd5*6:10.4
ktd5*7:400.6
ktd5*8:774..9
ktd5*9:12197..4
ktd5*10:245778..9
ktd5*11:501751...7
ktd5*12:9622773...0
ktd5*13:179350600...7
ktd5*14:348693067....0
ktd5*15:6768428427....1
ktd5*16:130393394244....3
ktd5*17:2496481803563....4
ktd5*18:48142477122337....4
ktd5*19:928528410498913....3
ktd5*20:17890971452591718....9
ktd5*50:6198104679769625519754629260357732407526763106589272262....8
ktd5*100:106069649690887257459041289111820338477486962216511888586376422742175499708041576405555660477911370258712771140152758617....2

ktd6*3:0 
ktd6*5:10.4
ktd6*7:8107..5
ktd6*9:2751170...8
ktd6*11:1158979805....3
ktd6*13:4507544601819....4
ktd6*15:17882310649767890....1
ktd6*17:70499565462702393880....3
ktd6*19:278228690327962255132539....5
ktd6*49:
ktd6*99:

ktd7*3:0 
ktd7*4:4.1
ktd7*5:400.6
ktd7*6:
ktd7*7:


(6) number of (open) tours from-to
    ------------------------------------
kt3*4,a1b1:1 Euler
kt3*4,a1c4:1 Euler
kt3*4,b1b4:2 Euler

kt8*8,a1b1:545522562....9
kt8*8,a1c2:13267364410532 McKay,Loebbing+Wegener
kt8*8,a1d1:535136239....6
kt8*8,a1d3:181697179....6
kt8*8,a1e2:220283413....2
kt8*8,a1e4:321118436....3
kt8*8,a1f1:383192639....7
kt8*8,a1f3:118988302....4
kt8*8,a1g2:245454172....7
kt8*8,a1g4:197610535....3
kt8*8,a1h1:1524879908....0
kt8*8,a1h3:362603243....2
kt8*8,a2e3:636789694...2
kt8*8,a2f2:388987138...7
kt8*8,a2f4:609497663...7
kt8*8,a2g3:225768266...6
kt8*8,a2h2:190389784....8
kt8*8,a2h4:183016132....9
kt8*8,a3e4:747422435...9
kt8*8,a3f3:279867835...8
kt8*8,a3g4:447513698...7
kt8*8,a3h3:875339047...6
kt8*8,a4f4:614454736...6
kt8*8,a4h4:183473389....8
kt8*8,b1a3:118372443....4
kt8*8,b1b2:953285204...4
kt8*8,b1b4:747981711...7
kt8*8,b1c1:137155320....9
kt8*8,b1c3:491611605...5
kt8*8,b1d2:978136842...5
kt8*8,b1d4:113807491....0
kt8*8,b1e1:197877845....0
kt8*8,b1e3:651939118...7
kt8*8,b1f2:394898733...9
kt8*8,b1f4:634625470...0
kt8*8,b1g1:196964379....8
kt8*8,b1g3:396361686...5
kt8*8,b1h2:184527588....1
kt8*8,b1h4:187634148....0
kt8*8,b2b3:181896443...0
kt8*8,b2d3:315695634...4
kt8*8,b2e2:338200993...0
kt8*8,b2e4:528871028...7
kt8*8,b2f3:195571865...1
kt8*8,b2g2:409210585...6
kt8*8,b2g4:323642226...3
kt8*8,b2h3:619928046...4
kt8*8,b3e3:118683353...9
kt8*8,b3f4:122835554...0
kt8*8,b3g3:75223826...8
kt8*8,b3h4:331622412...2
kt8*8,b4e4:433467527...3
kt8*8,b4g4:262339076...0
kt8*8,c1a4:130346025....8
kt8*8,c1b3:305801415...0
kt8*8,c1c2:259475336...0
kt8*8,c1c4:446848638...0
kt8*8,c1d1:130280148....3
kt8*8,c1d3:474290583...7
kt8*8,c1e2:689656449...3
kt8*8,c1e4:780302330...5
kt8*8,c1f1:919943108...0
kt8*8,c1f3:301731143...1
kt8*8,c1g2:614171899...5
kt8*8,c1g4:489393190...2
kt8*8,c1h3:882017329...3
kt8*8,c2b4:139817746...3
kt8*8,c2c3:86312935...4
kt8*8,c2d2:139389199...8
kt8*8,c2d4:225768266...6
kt8*8,c2e3:135890775...3
kt8*8,c2f2:78477409...6
kt8*8,c2f4:128196463...2
kt8*8,c2g3:75928081...2
kt8*8,c2h4:390136800...3
kt8*8,c3c4:144851632...3
kt8*8,c3e4:256186154...3
kt8*8,c3f3:92705087...4
kt8*8,c4d4:384189359...3
kt8*8,c4f4:203940279...4
kt8*8,d1b2:101104080....8
kt8*8,d1b4:713295143...1
kt8*8,d1c3:418740212...5
kt8*8,d1d2:739707905...0
kt8*8,d1d4:112539247....2
kt8*8,d1e1:194131354....2
kt8*8,d1e3:704233626...1
kt8*8,d1f2:519458236...0
kt8*8,d1f4:633259590...5
kt8*8,d1g3:332255644...5
kt8*8,d1h4:190078601....5
kt8*8,d2c4:223798220...1
kt8*8,d2d3:238820993...7
kt8*8,d2e2:275102050...4
kt8*8,d2e4:461865154...3
kt8*8,d2f3:160198468...9
kt8*8,d2g4:256252999...9
kt8*8,d2h3:498888179...6
kt8*8,d3e3:207043631...4
kt8*8,d3f4:208323588...4
kt8*8,d3h4:588503110...1
kt8*8,d4e4:673706702...0
kt8*8,e1a2:196808103....1
kt8*8,f3b4:153667515...7



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

(7) others

 ktc,8*8,different 4*8-halftours of closed tours:70432060
 ktc,8*8,different 4*8-pathstructures of halftours of closed tours:7934366
  compatible pairs of pathstructures (thus giving one or more closed tours):
  ~1.5e11 (too many to store on HD, maybe:for each PS give intervals
   for compatible PSs .. 4e6*2e4 entries)

kt 8*8,rank4-pathstructures:10266..3
kt 8*8,compatible pairs of halftour-pathstructures:
kt 8*8,compatible pairs of halftours:






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



many of the numbers are not yet confirmed by independent sources.
So, if you can confirm some of them or have different
counts, please send email to sterten@aol.com, subject line:#tours

Some other counts will be added the next days
and from time to time.





further ideas to be included:
(symmetric tours)
(tours starting at vertex v, ending anywhere)
(halftours)
(path structures)
(nodes of the searchtree)
(triangular boards)
(Aztec diamonds)
(toroidal boards)
(cylindrical boards)
(3-dimensional)
((semi-)magic tours)
(other leapers)


notation:
closed: ktc  , open:kto , from to
e.g.: 
ktc,5,8=44202  
kto,4,5=164  
kta1f1,6,7=9088598
kta1,6,7=57968982
kta1b1,6,7=3595288




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

See Jelliss' page for the history of enumerating knight's tours.

http://www.ktn.freeuk.com/sitemap.htm
and then see the section "smaller rectangles"

These pitiable people had to do it without computers !
So the methods descibed by Jelliss are somehow "expired".
A description of fast methods to enumerate knight's tours
by computer will be given later on a separate page.
See http://magictour.free.fr/method for a first version.

Actually, I'm not yet sure what is the fastest way to count
knight's tours on an 8*8 board !
With Brendan McKay's method it took me 52 hours on a 2.6GHz
computer. With the program used to generate the numbers
here (version from 26.Jan.2005) it takes >10 hours but maybe
upto 100 hours, I don't know. Improvements are possible.
It needs >20GB of fast HD-space but it didn't
work correctly since my C-compiler (gcc) doesn't support
files larger than 4GB, so I'll have to split them...
For the a*b boards there is usually a point a when the
computation becomes almost linear(b), this is typically
reached between b=1.5*a or b=2*a



on the a*b rectangle (b large) let #ps(a) be the number of
possible pathstructures (as defined in the McKay-paper) for
the 2*a cells which are reachable from the rest of the k*a subrectangle.
Then #ps(a)=SUM[i=0..a] (2a)!*2^(2a-3i)/(2a-2i)!/i!

#ps(a)^2  is an upper bound for the complexity and should be the
asymptotic size of the (sparse) transition matrix (matrices)
needed to calculate #tours(a,b) from #tours(a,b-1)

to summarize:
computing the knumber of (closed) knight's tours on an a*b rectangle
(with this method)
takes O(b*b*a*(#ps(a)) time and O(log(b)*#ps(a)+a*#ps(a))*log(#ps(a) space




timings in 1/100 sec for (1) with 2.6GHz, program version from 2005-02-05:

 b\a      3      4       5        6          7
----------------------------------------------------------------------
   4     88    131     170      214        270
   8    198    286     450     4624     136638
  16    445    615    1401    29204   (1042700)
  32    928   1280    3603    95054
  64   1895   2609    9178   298339
 128   3845   5322   25101   998260
 256   7844  11062   78450
 512  16549  24365  327527
1024  39046  64724
2048
4096


quotients time(a,b)/time(a,b/2):

 b\a      3      4       5        6          7  
-----------------------------------------------
   4                                             
   8   2.25   2.18    2.65    21.61     506.07     
  16   2.25   2.15    3.11     6.32       7.63       
  32   2.09   2.08    2.57     3.25 
  64   2.04   2.04    2.55     3.14 
 128   2.03   2.04    2.73     3.35 
 256   2.04   2.08    3.13 
 512   2.11   2.20    4.17 
1024   2.36   2.66


see also http://magictour.free.fr/method 
for a first desciption of the methods how to
count knight's tours. (to be updated in the next
weeks/months)




Guenter Stertenbrink  ,  2005/02/24





  100   ' ------Ubasic program to print the numbers of closed knight's tours              on a 3*2b rectangular board, b=0,1,2,...  . N,D below are viewed               as polynomials and N/D is the generating function, see A070030
  110   dim D(33),N(33)
  120   data 1,5,-34,-116,505,616,-3179,-4,9536,-8176,-13392,15360,13888,2784,-3328,-22016,5120,2048
  130   data 1,-6,-64,200,1000,-3016,-3488,24256,-23776,-104168,203408,184704,-443392,-14336,151296,-145920,263424,-317440,-36864,966656,-573440,-131072
  140   for I=5 to 22:read A:N(I)=A*16:next
  150   for I=0 to 21:read A:D(I)=A:next
  155   ' ----------------------------------------------------------------
  160   for I=0 to 20
  170   A=N(0):for J=0 to 30:N(J)=N(J+1)-A*D(J+1):next
  180   print I;A:
  190   next






   90   ' ------Ubasic program to print the numbers of open knight's tours               on a 3*2b rectangular board, b=4,5,.... D,N below are viewed as                 polynomials and N/D is the generating function. Thanks to                       Noam D. Elkies for computing the polynomials
  100   data 1,-4,-26,4,-43,-116,888,1224,10292,6052,-7088,111280,-16192,-204080,407232,-681472,66432,-699392,-943104,-126976,98304
  110   data 1,-6,-64,200,1000,-3016,-3488,24256,-23776,-104168,203408,184704,-443392,-14336,151296,-145920,263424,-317440,-36864,966656,-573440,-131072
  120   data 1,-9,-82,505,1590,-11215,2266,88975,-242131,323168,-480860,-4375016,34372144,-77217528,-7974176,444800704,-1012839760,1207719152,-399062000,-6231752320,14603764160,-16581634816,5139428992,47381573376,-55332587008,205403258624
  130   data -99585032960,-444863641600,-108086281216,-1438448672768,837770571776,2490215694336,-1857042202624,3720094285824,-2823629176832,-2636932448256,10246285688832,-10406850461696,5303788634112,-6106071957504,577266253824,2297740394496,-674125316096,2386122768384,-2053464129536,-318901321728,706522120192,-85899345920,17179869184
  140   data 99,-1713,-5530,223273,-311845,-11672254,39639552,282790140,-1617946333,-1421367267,31255787172,-96730512045,-146480240281,2601619637366,-6373954742870,-24042471384500,146858830474752,-74584242841620,-1183416990768828,3311094993329668,-1135769219514432,-13762067882041752,70267598270676560,-247102183156854016,158796425103663632
  150   data 2690879510742326080,-10185496762458487328,3922767298257597312,68554801931985793088,-201573370168325958912,99457281195961113856,860761587279350745088,-2962604018126256240128,4563541603975026552064,3399727414299208786944,-44919087288807589316096,118297386331109543161344,-41389777514130496336896,-624637927602882189483008,1795804033649590695449600
  160   data -926372040927706433126400,-6505544934589620409829376,18359352896224038675771392,-12595172344977885605416960,-45787255814673550658285568,143581444264406287458361344,-138862142627938942262099968,-210603249663658413809565696,907460293915483454822039552,-1113659913395107176682848256,-555484246506539523171155968,4149008879926265096965062656,-6307217925773986207688753152
  170   data 1502657181611442778706149376,11418813721174250098903220224,-26534071679390992877942996992,26634793664620971403708727296,7806949592128421199294234624,-62933050383055821881780207616,132057328506169029963241488384,-182686076882869252628989083648,51279396666959021260419366912,448344562498027521076015136768,-1244369543011417116778013130752,1144635654828274361534079041536
  180   data 945309687794333121674532093952,-3933006302289707099339760861184,6030713619804668048510482907136,-1771044916709607010571338645504,-10779951468955419296180970979328,17523277230458932219735688871936,-11059151052088951533917865771008,-7815932993585715718467488841728,38612644199636643630394137116672,-45289950406259260822437322817536,1778155906152096733722767785984,50786871690348163266682697023488
  190   data -71475604823351282973390766342144,52985302893719172997785304694784,12209054101054958199324582871040,-93946430077535339971994166755328,108221681220474976175870212833280,-41458091700499348629644113870848,-38278458098467163968498061803520,91514104321786919976995198599168,-92529413704116435596875034263552,41837805398024832335413856174080,17198513383634074775801798066176
  200   data -61154714521031465230122212130816,75471525387839824897689897664512,-49397470378134889781142178758656,11178339235027716481718656434176,10211384794884627621175554473984,-21626818804119750245827863379968,21008048866444388248971343036416,-6308861732050815247351663296512,-777754554741373885666381791232,2186017979971812008050164760576,-6254996467172426472953823100928,3391054528756863614111528779776
  210   data 2335582748884277479039553241088,-1970518298522007230192805740544,-259469239095037096024946507776,371827276195012279243439603712,-953154186761064168053276672,-12693780135534642204980019200,469497675726900127145656320,-180772188964250018780282880,-58330670796405857679572992,-604462909807314587353088
  220   word -200
  230   dim P20(20),P21(21),P48(48),D(111),N(111)
  240   restore 100
  250   for I=0 to 20:read P20(I):next
  260   for I=0 to 21:read P21(I):next
  270   for I=0 to 48:read P48(I):next
  280   for I=0 to 109:read A:D(I)=8*A:next
  290   for I=0 to 20:for J=0 to 21:for K=0 to 21:for L=0 to 48
  300   N(I+J+K+L)+=P20(I)*P21(J)*P21(K)*P48(L)
  310   next L:next K:next J:next I
  320   for I=0 to 21
  330   A=D(0):for J=0 to 110:D(J)=D(J+1)-A*N(J+1):next
  340   print I*2+8;A:
  350   next:end