Title: Generate self-avoiding walks one at a time in C#

The example Generate random self-avoiding walks in C# uses a timer to display self-avoiding walks at regular intervals. It generates each walk randomly as it is needed. That's great if you want to display random walks, but what if you want to display the walks in order?

The problem is that the self-avoiding walks are generated deep inside a sequence of recursive method calls. If the lattice has N vertices, then a complete walk is only discovered at the bottom of N - 1 levels of recursion. So the question is, how can you return a walk to the top-level code but stay inside the recursion?

One approach is to find all of the walks ahead of time, save them all in a list, and then display them as needed. That's the approach taken by the example Find self-avoiding walks in C#.

Unfortunately that requires you to find all of the walks before displaying any of them, and that can take a while.

This example uses a different approach. The following code shows the main method that generates self-avoiding walks.

// Generate all self-avoiding walks. private IEnumerable<List<Point>> FindWalks(int width, int height) { // 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. return FindWalks(num_points, current_walk, 0, 0, width, height, visited); }

This method returns an IEnumerable<List<Point>> so the main program can loop through the list of returned walks. After some set up, the code calls the following overloaded version of FindWalks to do the recursive work.

// Extend the walk that is at (current_x, current_y). private IEnumerable<List<Point>> FindWalks(int num_points, Stack<Point> current_walk, int current_x, int current_y, int width, int height, bool[,] visited) { // If we have visited every position, and the // last point is in the lower right corner, // then this is a complete walk. if (current_walk.Count == num_points) { #if CORNER_WALKS if ((current_x == width) && (current_y == height)) yield return current_walk.ToList(); #else yield return current_walk.ToList(); #endif } 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), }; // Try the moves. 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); foreach (List<Point> walk in FindWalks(num_points, current_walk, point.X, point.Y, width, height, visited)) yield return walk; // We're done visiting this point. visited[point.X, point.Y] = false; current_walk.Pop(); } } }

This code works much as the versions used in previous examples with two differences. First, it returns an IEnumerable<List<Point>>. Again this is so the main program can iterate through the self-avoiding walks that it generates.

The second difference is, when it finds a new walk, the method uses a yield return to return it. This statement returns the new walk to the enumerator used by the main program and then saves the current state of execution. When the enumerator needs another walk, the program resumes execution at the saved state of execution, deep inside the recursive calls. Basically the program crawls down into the sequence of recursive calls and then takes a time out while it returns the discovered walk. When it's ready, it resumes where it left off inside the recursion so it can look for more walks.

The last part of the example is the code that uses the enumerator. The program uses the following code to declare an enumerator to loop through the returned self-avoiding walks.

private IEnumerator<List<Point>> Walker = null;

The enumerator is declared at the class level so it is visible throughout the program.

When you click the Generate button, the program uses the following code to create the enumerator.

WalkWidth = int.Parse(txtWidth.Text); WalkHeight = int.Parse(txtHeight.Text); IEnumerable<List<Point>> walks = FindWalks(WalkWidth, WalkHeight); Walker = walks.GetEnumerator();

This code gets the desired lattice dimensions and then calls the FindWalks method, saving the result in the variable walks.

If you step through the code, you'll find that the program doesn't actually generate any walks at this point. It enters the first call to FindWalks but it skips over the call to the overloaded version. All it really does at this point is save the program state and create an enumerator that can resume execution at that state later.

The code then calls the walks variable's GetEnumerator method to get the enumerator and saves it in the variable Walker for later use.

Later, when the program's timer ticks, the program executes the following code.

// Generate and display the next walk. private void tmrShowWalk_Tick(object sender, EventArgs e) { if (Walker == null) tmrShowWalk.Enabled = false; else DisplayNextWalk(); }

This code just calls the following DisplayNextWalk method, which contains the last really interesting piece of code.

private void DisplayNextWalk() { lblWalkNum.Text = "Walk " + WalkNumber.ToString(); WalkNumber++; if (!Walker.MoveNext()) { btnGenerate.Text = "Generate"; Walker = null; } else { using (Pen pen = new Pen(Color.Blue, 2)) { List<Point> walk = Walker.Current; Bitmap bm = DrawWalk(walk, WalkWidth, WalkHeight, picCanvas.ClientSize.Width, picCanvas.ClientSize.Height, Color.White, Brushes.Green, pen); picCanvas.Image = bm; } } }

This method calls the Walker object's MoveNext method. That method makes the enumerator try to generate the next item in the enumeration. In this example, that's the next self-avoiding walk. The code resumes execution at the saved program state until a yield return statement sends a walk back to the enumerator. The recursive code saves its state again and control returns to the DisplayNextWalk method.

If the enumerator code is unable to find a new walk because it is finished listing them, then the Walker object's MoveNext method returns false. In that case the DisplayNextWalk resets its button's caption to Generate, sets the Walker to null, and returns.

Otherwise if the recursive code does find a new walk, the MoveNext method returns true and the DisplayNextWalk method calls DrawWalk to display it. Download the example and look at the code to see how DrawWalk works.

To summarize, here are the steps for iterating through the results of a method as the results are generated.

1. Make the method return an IEnumerable of something.
2. Make the method use the yield return statement to return results to the enumerator.
3. Make the main program iterate through the result returned by the method. It can do this by using an enumerator object as in this example, or by using a foreach loop.
4. If the method calls another method, as in this example where the main method calls a recursive version, make the called method also return an IEnumerable and make it also use yield return to return results.

I wouldn't say this is exactly simple, but it does let you do something that would otherwise be fairly complicated. It lets you step through the results of the recursive call as they are generated. This can be particularly useful, for example, if you don't know how many results you'll need. Then this method lets you stop enumerating the results at any time.

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