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

[self-avoiding walks]

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:


With this one:

if ((current_x == width) && (current_y == height))

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 Example   Follow me on Twitter   RSS feed   Donate

About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, drawing, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.