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 random self-avoiding walks in Python and tkinter

The previous example Find self-avoiding walks that start and end at given positions in Python and tkinter finds and displays self-avoiding walks. If you watch the display, you can see that there's a definite pattern to how the walks are displayed. The paths start by going right as far as they can, then down as far as possible, then left, and so forth. Run that example a few times to see what I mean.

This example shows one way to generate a random self-avoiding walk. If you check the One Path checkbox and click Generate, the program displays a more or less random self-avoiding walk.

This requires only one relatively small change. When the current path is at a point, the program randomizes the list of that point's neighbors. When the program finds a complete self-avoiding walk, it has made a random selection of choices to get there so the result is fairly random.

The following code shows the revised find_walks method with the changes highlighted in blue.

def find_walks(end_at, num_points, walks, current_walk, current_x, current_y, width, height, visited, one_path=False): '''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: # This is a valid complete walk. 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), ] # Randomize the list of neighbors. random.shuffle(next_points) 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 # If point is end_at and it's not the last spot in the walk, # then this partial walk cannot lead to a solution. if (point == end_at) and (len(current_walk) != num_points - 1): continue # Try visiting this point. visited[point[0]][point[1]] = True current_walk.append(point) find_walks(end_at, num_points, walks, current_walk, point[0], point[1], width, height, visited, one_path) # If we only want one path and we have it, return. if one_path and (len(walks) > 0): return # We're done visiting this point. visited[point[0]][point[1]] = False current_walk.pop()

Later, after the recursive call to find_walks returns, the code checks one_path and the length of the walks list. If we only want one path and we have found it, the method returns without looking for more paths.

If you use the program to find a single path, the result is pretty random. If you search for all paths between the start and end points, things are less random because paths found near each other tend to share initial partial paths. The result is more random than before but not all that random.

If you want to generate all of the paths completely randomly, build the walks list as usual and then use random.shuffle to randomize it.

If you only want to find one path, then this program can sometimes solve larger problems in a reasonable amount of time. For example, the program found the path in the 5×5 lattice shown in the picture at the top of this post in about 1.6 seconds.

However, in some cases there is no solution and then the program must visit every possible path before it gives up. For example, if you try to find a path from (1, 1) to (5, 5) on a 5×5 lattice, the program takes around 47 seconds to decide that there is no such path.

Download the example to see additional details.