Start._ _ |_|_| (2x2) |_|_| 'FinishHow many ways of travelling along the lines, from Start to Finish, without retracing steps?
How about a (n*n) square? He did not state whether each walk would have to visit all the points. This made me think about my counting program. I have addapted it in such a way that it can also count walks from a certain point in the first row to a certain point in the last row.
This problem is also known as the chess/rook.path problem in the rec.puzzle FAQ.
Let M(n,m)
be the number of paths from one corner to the other
corner in P_n x P_m
.
The the following results were known:
M(n,m) = M(m,n) M(1,m) = 1 M(2,m) = 2^(m-1)I found the following other results:
M(3,3) = 12 M(3,4) = 38 M(3,m) = 4M(3,m-1) - 3 M(3,m-2) + 2M(3,m-3) + M(3,m-4) (for m > 4) M(4,4) = 184 M(4,5) = 976 M(4,6) = 5382 M(4,7) = 29739 M(4,8) = 163496 M(4,9) = 896476 M(4,10) = 4913258 M(4,11) = 26932712 M(4,12) = 147657866 M(4,n) = 12M(4,m-1) - 54M(4,m-2) + 124M(4,m-3) - 133M(4,m-4) - 16M(4,m-5) + 175M(4,m-6) - 94M(4,m-7) - 69M(4,m-8) + 40M(4,m-9) + 12M(4,m-10) - 4M(4,m-11) - M(4,m-12) (for m > 12) M(5,1) = 1 M(5,2) = 16 M(5,3) = 125 M(5,4) = 976 M(5,5) = 8512 M(5,6) = 79384 M(5,7) = 752061 M(5,8) = 7110272 M(5,9) = 67005561 M(5,10) = 630588698 M(5,11) = 5933085772 M(5,12) = 55827318685 M(5,13) = 525343024814 M(5,14) = 4943673540576 M(5,15) = 46521924780255 M(5,16) = 437788749723725 M(5,17) = 4119750109152730 M(5,18) = 38768318191017931 M(5,19) = 364823700357765771 M(5,20) = 3433121323699285343 M(5,21) = 32306898830469680384 M(5,22) = 304019468350280601960 M(5,23) = 2860931888452842047170 M(5,24) = 26922391858409506569346 M(5,25) = 253349332040459400463497 M(5,26) = 2384107785665647075602841 M(5,27) = 22435306570786253414376286 M(5,m) = 30M(5,m-1) - 383M(5,m-2) + 2772M(5,m-3) - 12378M(5,m-4) + 33254M(5,m-5) - 40395M(5,m-6) - 44448M(5,m-7) + 239776M(5,m-8) - 274256M(5,m-9) - 180404M(5,m-10) + 678758M(5,m-11) - 301650M(5,m-12) - 542266M(5,m-13) + 492472M(5,m-14) + 184306M(5,m-15) - 225284M(5,m-16) - 102314M(5,m-17) + 25534M(5,m-18) + 97396M(5,m-19) + 10392M(5,m-20) - 40292M(5,m-21) - 13218M(5,m-22) + 5328M(5,m-23) + 5376M(5,m-24) + 1822M(5,m-25) + 319M(5,m-26) + 24M(5,m-27).For information about how I found these results, please look at my Hamilton counting page. Or in table form:
| 1 2 3 4 5 6 7 8 ---+---------------------------------------------------------------- 1 | 1 1 1 1 1 1 1 1 2 | 1 2 4 8 16 32 64 128 3 | 1 4 12 38 125 414 1369 4522 4 | 1 8 38 184 976 5382 29739 163496 5 | 1 16 125 976 8512 79384 752061 7110272 6 | 1 32 414 5382 79384 1262816 20562673 336067810 7 | 1 64 1369 29739 752061 20562673 575780564 16230458696 8 | 1 128 4522 163496 7110272 336067810 16230458696 789360053252Simular results are found by Christoph Dürr and others. Recently, Steve Finch has started a page about the subject of rook paths.
To find solutions for this problem my program needs to be modified to a greater extend.