# The rook path problem

D.P. Chan posted the following question on sci.math:
A puzzle that's had the better of me for ages:
```Start._ _
|_|_|  (2x2)
|_|_|
'Finish
```
How many ways of travelling along the lines, from Start to Finish, without retracing steps?

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 789360053252
```
Simular results are found by Christoph Dürr and others. Recently, Steve Finch has started a page about the subject of rook paths.

## Another problem

Later D.P. Chan mailed me to explain that he looked for the number of trails between the two points. In a trail each edge can be visited at most once, but a vertex can be visted more than once. This is a different problem then the one discussed above.

To find solutions for this problem my program needs to be modified to a greater extend.

Counting page | home