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 with start and end points more efficiently in Python and tkinter

[A self-avoiding walk]

The previous example Find self-avoiding walks that start and end at given positions in Python and tkinter finds self-avoiding walks. To do that, it enumerates all of the possible walks and then saves those that visit every lattice position.

Sometimes considering solutions in a different order or in a different way can improve performance. In this example, think about what happens when the program adds the end point to the current walk. If the walk has not yet visited every other lattice point, then it cannot end at the end point without visiting it again, which makes the walk self-intersecting.

We can take advantage of that fact by checking whether the newly added point is the end point. If it is and we have not visited all of the other points, then we can abandon the current partial walk. The current partial walk could head in many directions, so stopping it now might let us skip a lot of work.

The following code shows the new version of the 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): '''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):~~ # 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), ] 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) # We're done visiting this point. visited[point[0]][point[1]] = False current_walk.pop()

This version of the method only has two changes. First, when the walk's length equals num_points, the code no longer needs to check whether the walk's end point matches end_at. The walk cannot reach length num_points unless end_at is placed at the end. If that point appears somewhere earlier in the walk, then the next change would have stopped the method from continuing to follow the current walk.

The second change is the addition of another test to see if recursion should continue. If we are considering adding end_at to the current walk and the walk isn't complete, the code uses a continue statement to skip adding that point and it continues looking at the points in the next_points list.

Here are some times for the original and improved code.

Without Improvement: 4x4, (0, 0) -> (4, 4): 0.0934000015258789 seconds 4x5, (0, 0) -> (4, 4): 1.090010404586792 seconds 5x5, (0, 0) -> (4, 4): 21.230018377304077 seconds 5x5, (0, 0) -> (1, 1): 21.19418954849243 seconds With Improvement: 4x4, (0, 0) -> (4, 4): 0.0495908260345459 seconds 4x5, (0, 0) -> (4, 4): 0.33052492141723633 seconds 5x5, (0, 0) -> (4, 4): 4.511371612548828 seconds 5x5, (0, 0) -> (1, 1): 4.0410542488098145 seconds

The amount of time saved depends on the number of walks that can be eliminated by the new test. The number of paths grows exponentially with the size of the lattice, so the savings is much greater for larger lattices.

I can imagine other tests that you might try to eliminate partial walks that cannot be complete. For example, if a walk touches the left and right sides of the lattice, and there are unvisited points both above and below the walk so far, then there's no way it can visit all of the remaining points. Those kinds of tests would be more complicated so they would take some time and therefore wouldn't save as much time, at least for small problems, but for larger lattices they might be worth the trouble.

Download the example to see additional details.