Title: Find corner-to-corner self-avoiding walks in C#

The example Find self-avoiding walks in C# shows how to find self-avoiding walks. This example modifies that one so it only picks self-avoiding walks that start in the upper left corner and that end in the lower right corner.

This is actually quite simple. When it finds complete self-avoiding walks, the program just replaces this statement:

walks.Add(current_walk.ToList());

With this one:

if ((current_x == width) && (current_y == height)) walks.Add(current_walk.ToList());

Now the program only adds a walk to the result list if its final point is at position (width, height).

You can easily modify the example to make it only pick complete self-avoiding walks that end at some other position.

Note that the program cannot find any corner-to-corner self-avoiding walks if the width and height of the lattice are both odd. To understand why, note that each move changes either the row or the column from odd to even or vice versa.

Also note that a lattice with width w and height h contains h + 1 rows of vertices numbered from 0 to h and w + 1 columns of vertices numbered from 0 to w. For example, the lattice in the picture above has width and height 4 so it has 5 rows and columns of vertices.

Finally note that a lattice with width w and height h contains a total of (h + 1) * (w + 1) vertices so a self-avoiding walk must make (h + 1) * (w + 1) - 1 moves.

Now suppose w and h are both odd. The goal is to find a walk that starts at (0, 0) and ends at (h, w). That means we would need to make an even number of moves to change the current row and column from both even values (0, 0) to both odd values (h, w). However if h and w are both odd, then h + 1 and w + 1 are even, so the number of moves (h + 1) * (w + 1) - 1 is odd. We need to move an even number of times but the walk must use an odd number of steps so we can't end at the lower right corner.

For a concrete example, consider a lattice with h = 3 and w = 3. Then there are 4 vertices in each row and column for a total of 16 vertices. Therefore the walk must have 15 steps. But any 15 step path from (0, 0) will leave one of the row or column odd and the other even.

To understand why you can find corner-to-corner walks if either w or h is even, consider the cases. If both are even, then (h + 1) * (w + 1) is odd so (h + 1) * (w + 1) - 1 is even. We need to get from (0, 0) to (h, w) where h and w are both even, so this is plausible.

Now suppose h is odd and w is even. Then h + 1 is even and w + 1 is odd, so (h + 1) * (w + 1) is even and therefore (h + 1) * (w + 1) is odd. We need to go form the even/even position (0, 0) to the even/odd position (h, w), so again this is plausible.

In both of those cases, you can easily construct a walk that zigzags across the odd dimension to end in the lower right corner.

Download the example to experiment with it and to see additional details.