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 that start and end at given positions in Python and tkinter

[A self-avoiding walk]

This example uses a relatively small variation on the previous example Find self-avoiding walks in Python and tkinter. This version lets you specify the location of the walk's desired start and end points.

The following code shows the revised find_all_walks method with the modified code highlighted in blue.

def find_all_walks(width, height, start_at=(0, 0), end_at=None): '''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 start_at. current_walk = [] current_walk.append(start_at) start_x = start_at[0] start_y = start_at[1] visited[start_x][start_y] = True # Search for walks. find_walks(end_at, num_points, walks, current_walk, start_x, start_y, width, height, visited) return walks

This version creates the walks list as before. It then sets the visited entry for start_at to True and calls find_walks passing it the start point's coordinates.

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

def find_walks(end_at, 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: # Accept if end_at is None or the walk ends at end_at. if (end_at is None) or (current_walk[-1] == end_at): 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(end_at, 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()

This version of the method takes the new end_at point as a parameter. When it finds a complete walk, the code checks whether end_at is None (indicating any end point is okay) or the walk's last point is end_at. If either any end point is okay or the walk ends at end_at, the code adds the walk to the walks list.

NOTE: A complete walk is not necessarily possible for every start and end point. For example, if the lattice's width or height is even, then there is no complete walk from (0, 0) to (0, 1).

The rest of the program is mostly similar to the previous one. Download the example to see all of the details.