For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Find self-avoiding walks in Python and tkinter

This is the first post in a short series of articles 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.

The most straightforward method for generating self-avoiding walks is quite easy, although it may take a while 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 north, east, south, and west of that vertex, assuming the new vertex isn't outside of the lattice's boundaries and we haven't visited that vertex before. If the recursive method visits every vertex in the lattice, then it has found a complete self-avoiding walk.

There's a fair amount of tkinter and Python detail in this example. For example, the program uses after to display one walk after another. Use the Scale widget to control the display speed. Download the example to see those kinds of details. Here I'm just going to talk about the code that generates the walks.

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

def find_all_walks(width, height): '''Generate all self-avoiding walks.''' walks = [] # Make a list to show where we have been. visited = [[False for h in range(height + 1)] for w in range(width + 1)] # Get the number of points we need to visit. num_points = (width + 1) * (height + 1) # Start the walk at (0, 0). current_walk = [] current_walk.append((0, 0)) visited[0][0] = True # Search for walks. find_walks(num_points, walks, current_walk, 0, 0, width, height, visited) return walks

The method starts by creating a list to hold the walks. It also creates a list of lists of Booleans to indicate which lattice vertices have been visited. For example, visited[x][y] is True if we have already visited the lattice at position (x, y).

The code creates a current_walk list to hold the current walk's points and adds the point (0, 0) to it to indicate that this path starts in the lattice's upper left corner. (You could start at some other point if you like.)

The code then calls the following find_walks method to extend the initial walk.

def find_walks(num_points, walks, current_walk, current_x, current_y, width, height, visited): '''Extend the walk that is at (current_x, current_y).''' # If we have visited every position, # then this is a complete walk. if len(current_walk) == num_points: walks.append(current_walk.copy()) if len(walks) % 1000 == 0: print(f'{len(walks)}') else: # Try the possible moves. next_points = [ (current_x - 1, current_y), (current_x + 1, current_y), (current_x, current_y - 1), (current_x, current_y + 1), ] for point in next_points: if point[0] < 0: continue if point[0] > width: continue if point[1] < 0: continue if point[1] > height: continue if visited[point[0]][point[1]]: continue # Try visiting this point. visited[point[0]][point[1]] = True current_walk.append(point) find_walks(num_points, walks, current_walk, point[0], point[1], width, height, visited) # We're done visiting this point. visited[point[0]][point[1]] = False current_walk.pop()

First, the code checks the length of the partial walk. If that walk is as long as the number of points in the lattice, then it has visited every point. In that case, the code copies the walk and adds it to the walks list.

If this is not a complete walk, the code makes a list of the points that are adjacent to the last point in the partial walk and then loops through those points.

If a point falls outside of the lattice or it we have already visited that point, the program uses continue to skip it and continue examining the other neighboring points.

If a neighbor point is valid, the code marks it as visited (so we don't try to visit it again later) and adds the point to the current walk. The find_walks method then recursively calls itself to find walks that begin with the newly extended walk.

After the recursive call ends, we have examined any possible walk that begins with the current partial walk. The code marks the most recently added neighbor as not visited (so other walks can use it later), pops that neighbor from the walk, and continues its loop to check the other neighbor points.

That's the gist of finding self-avoiding walks with an exhaustive search. The rest of the program starts the process, displays the walks, and lets you use the Scale widget to control the display speed.

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.