The "naive" implementation to compute the rook paths is quite simple. An example C program is shown in the puzzle archive. It uses a simple recursive backtracking, marking the squares which are already part of the current path, and avoids to include (visit) them again. Unfortunately, with this method we will not compute many values beyond W(6,6).
Hence, improvement was necessary in order to at least compute W(8,8). First, the normal speed-up techniques can be used. As it turned out, the most important speed up was achieved, when literally all recursive subjobs (and their result) were cached. This allowed to compute W(8,8) in less than 8 minutes.
Unfortunately, this improved method still was not fast enough to do W(10,10) within reasonable time. Fortunately, I found a much faster computation method, at the cost of needing much memory. With this method I was able to compute W(15,20) in 16.5 hours, using 33.36 MB memory (for more than a million numbers, each 32 bytes in size). As far as I am aware, there is no other method of computation which yields comparable results.
This faster method of computation is quite different from the improved naive approach. I give a very rough sketch of this method. Basically, the grid is sliced in rows of width M. At each border between two adjacent slices we observe all possibilities, how a path can walk through this border line. Since the start and the finish of any solution path are at opposite sides of such a border line, any path must cross the border line at least once. More generally: it must cross it an odd number of times. The directions of the crossing alternate each time, and each crossing occurs at a different point of the border line. Therefore the width of the border line limits the number of crossings.
Assume some solution path, and let us look at one of the slicing rows somewhere in the middle of the path. There are two border lines surrounding the slicing row, one nearer to the start of the path, one further away and therefore nearer to the finish of the path. As a convention, let us assume the start to be on the top, and the finish to be at the bottom of our grid. We want to concentrate on the slice, and how it connects the two border lines, and therefore forget about the details outside the slicing row, as far as possible. What we still must know, is: which border line segment is connected with the start, the finish, or which other border line segment.
Below each border line we reduce the path to a certain pattern, containing one direct connection with the finish (we call this an I), and zero or more connections between two border line segments (we call these Us). All of these must not cross each other. We call such a collection of one I and several U an IUU (of width M). Now, we may enumerate all possible IUU for a certain width. For larger widths the number of IUUs becomes prohibitive. For width 15 there are already 542895 of them.
Now we classify all possible paths by IUUs in the following way: each path is associated with the IUU which represents that part of this path, which is below some fixed border line. And for each IUU we just count, how many paths are associated with it. Given such a collection of path counts for all possible IUUs for a border line at the upper border of a slicing row, we find an effective method to compute that same path count collection for the lower border of that slicing row. This accounts for "what can happen inside the slicing row".
Now we can iteratively move our border line towards the finish. We are still left with the construction of the very first path count collection, and the final interpretation of the last computed path count collection. The very first collection is for depth 0. It contains zeroes in all places (for all IUUs) except for one, which consists of an I at the start column, and no U at all. This special IUU gets a count of 1, representing the one possibility of the empty path to be continued. From the final collection we pick exactly one path counter, which is associated with the IUU consisting of an I at the finish column and no Us at all. This final IUU represents those paths which can be completed by the empty connection with the finish.
Ok, fine. But how do we map one path count collection to the next? Well, there is an easy way, and there is a more complex way (you already guessed that). Here is the easy way: First, set all target counts to zero. Then, for all pairs of IUUs we just test, whether the first maps to second, and if so, add the old counter for the first IUU to the new counter of the second IUU.
We still need the map test function. It is given an IUU below the upper border line, and an IUU below the lower border line of a slicing row, and has to decide, whether both border lines can be connected inside the slicing row in such a way, that the lower IUU together with the row-internal connections in fact exactly implement the upper IUU. If there is a way to do this, then there is exactly one way to do it.
Within the connecting row there is not much space to build the necessary connection. This helps a lot. This is how we construct the only candidate connection: We travel along the row, say from left to right, and observe, where (at which segments) we meet the ends of Is and Us of either IUU. When we encounter the first such end, we pick it up, since it must be connected, to some other end further right... to exactly the next one. When we encounter two ends at the same time, we connect them immediately. When we encounter two ends at the same time, while we search for a connection point, we immediately know, that there is no valid connection, not even a candidate.
We are still not ready. The above connection construction just builds a candidate. It may still be an invalid connection. This can be tested by following the connections and validating that both ends of all the Us of the upper IUU are in fact connected via inner-row connections and Us of the lower IUU. And the I of the upper IUU must be connected to the I of the lower IUU via via inner-row connections and Us of the lower IUU. And all of the Us of the lower IUU must be used in that way. Fortunately, we need not test for crossing Is and/or Us. By construction this cannot happen. All further details are left for the inspired reader.
Unfortunately, this mapping test is done quite often (quadratically in the number of IUUs), and in most of the cases the mapping test says "no". A better, but much more complex method avoids all of this by directly and constructively enumerating all pairs of IUUs, for which the map test would say "yes". This method is not (yet) described here.
The above was written in late 1997. In Jan-2004 I found this interesting paper about "meanders". Obviously I have "used" that theory without knowing about it. I have not yet really studied that paper. I'll come back here, when I have.