Title: Find self-avoiding walks in C#

This is the first post in a short series that find and display self-avoiding walks. In general, self-avoiding walks are paths that don't cross themselves. You could call them non-self intersecting paths if you like.

Usually self-avoiding walks have movement restrictions. For example, often the walk must visit the vertices in a lattice as shown in the picture shown here.

The most straightforward method for generating self-avoiding walks is quite easy, although it may be slow depending on the problem size. The program starts at a lattice vertex. It then recursively visits each of the four neighboring vertices that are to the left, right, up, and down from that vertex without moving outside of the lattice's boundaries. If the recursive method visits every vertex in the lattice, then it has found one of the self-avoiding walks.

This example uses the following method to begin a recursive search for self-avoiding walks.

// Generate all self-avoiding walks. private List<List<Point>> FindWalks(int width, int height) { List<List<Point>> walks = new List<List<Point>>(); // Make an array to show where we have been. bool[,] visited = new bool[width + 1, height + 1]; // Get the number of points we need to visit. int num_points = (width + 1) * (height + 1); // Start the walk at (0, 0). Stack<Point> current_walk = new Stack<Point>(); current_walk.Push(new Point(0, 0)); visited[0, 0] = true; // Search for walks. FindWalks(num_points, walks, current_walk, 0, 0, width, height, visited); return walks; }

This method returns a list of lists of points. The smaller lists give the points in the self-avoiding walks.

The method starts by creating a list to hold the walks. It also creates an array of Booleans to indicate which lattice vertices have been visited, and it calculates the number of vertices in the lattice.

Next the code creates a stack to hold the vertices as it visits them. It pushes the start point onto the stack and then calls the following overloaded version of the FindWalks method.

// Extend the walk that is at (current_x, current_y). private void FindWalks(int num_points, List<List<Point>> walks, Stack<Point> current_walk, int current_x, int current_y, int width, int height, bool[,] visited) { // If we have visited every position, // then this is a complete walk. if (current_walk.Count == num_points) { walks.Add(current_walk.ToList()); if (walks.Count % 1000 == 0) { lblResults.Text = "... " + walks.Count.ToString() + " ..."; Application.DoEvents(); } } else { // Try the possible moves. Point[] next_points = new Point[] { new Point(current_x - 1, current_y), new Point(current_x + 1, current_y), new Point(current_x, current_y - 1), new Point(current_x, current_y + 1), }; foreach (Point point in next_points) { if (point.X < 0) continue; if (point.X > width) continue; if (point.Y < 0) continue; if (point.Y > height) continue; if (visited[point.X, point.Y]) continue; // Try visiting this point. visited[point.X, point.Y] = true; current_walk.Push(point); FindWalks(num_points, walks, current_walk, point.X, point.Y, width, height, visited); // We're done visiting this point. visited[point.X, point.Y] = false; current_walk.Pop(); } } }

This method takes as an input the stack that holds the points in the current walk so far. It then extends that walk by recursively visiting the last point's neighbors.

The method first checks the size of the stack. If the stack includes every point in the lattice, then this is a complete walk so the method adds it to the walks list.

If this isn't a complete walk, then the method makes an array containing the points adjacent to the current walk's last point. The method then calls itself recursively to try adding each of those points to the end of the current walk. For each of those points, it sets the point's visited value to true, pushes the point onto the stack, and then calls the FindWalks method.

After the recursive call returns, the method removes the point from the stack and resets its visited value to false so other walks can try to use the path.

That's about all there is to finding self-avoiding walks with an exhaustive search. The rest of the program starts the process and lets you use the track bar to display the walks that it found. Download the example to see additional details.

In the next few posts, I'll explain how you can generate self-avoiding walks that end at the lower right corner of the lattice (or any other desired position for that matter), how to generate the walks in a more random order, and how to generate walks randomly.

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