# 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?

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 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