Self Avoiding Walks

In my previous post titled Random Walks, I made mention of self-avoiding walks and for this post I asked Gemini 2.5 Pro to implement the following program:

Write a program in Python that will generate and display a random but self avoiding walk on a square grid of points. The size of the grid can be 100 x 100 points but this should be easily modifiable. The walk should start at the bottom left hand side and proceed to the top right hand side. Each step can be up or down from one point to the next or left or right from one point to the next but movement is contrained within the grid of points. The number of steps required to complete the walk should be prominently displayed at the top or bottom of the display.

It dutifully did this and here is the Canvas link. Here was Gemini's thinking about the desired program.

Okay, I'll provide you with a Python program that generates and displays a random self-avoiding walk on a square grid. This program uses a recursive backtracking algorithm to find a path from the bottom-left corner to the top-right corner. The grid size is easily modifiable.

Here's how the program works:

1. Grid and Path Representation: The grid is implicitly defined by its size. The path is stored as a list of (x, y) coordinate tuples.
2. Self-Avoiding Walk Generation:
   • It starts at (0,0) (bottom-left).
   • The target is (grid_size-1, grid_size-1) (top-right).
   • A recursive function attempts to find a path:
     • It marks the current cell as visited and adds it to the path.
     • If the current cell is the target, the path is found.
     • Otherwise, it randomly shuffles the possible directions (Up, Down, Left, Right).
     • For each valid direction (within bounds and not previously visited in the current path), it makes a recursive call.
     • If a recursive call returns success, the path is propagated up.
     • If all directions from the current cell lead to dead ends, it backtracks by removing the cell from the path and unmarking it as visited.
   • Due to the potential for deep recursion, especially on large grids (like 100x100), the program attempts to increase Python's recursion limit. Note that for very large grids, this process can still be computationally intensive and take some time.
3. Display:
   • matplotlib is used to visualize the walk.
   • The path is plotted on the grid.
   • Start and end points are highlighted.
   • The number of steps taken is displayed in the plot title.

I will now generate the Python code for you.

Self-Avoiding Random Walk Generator

This Python script defines two main functions: generate_self_avoiding_walk to create the path and display_walk to visualize it using matplotlib.

To use this code:

1. Save it as a Python file (e.g., saw_generator.py).
2. Make sure you have matplotlib installed (pip install matplotlib).
3. Run it from your terminal: python saw_generator.py.
4. You can easily change the GRID_SIZE variable in the if __name__ == "__main__": block to generate walks on grids of different sizes. Keep in mind that larger grids (e.g., 100x100) will take significantly longer to compute and may require a high recursion limit, which the script attempts to set.

The generated plot will show the random walk, and the title will include the number of steps taken.

I should try to implement this program myself using SageMathCell. Running the program on SageMathCell using only for a 20m x 20 grid will often cause it to time out and even in my Jupyter notebook I often needed to terminate the process because it was taking too long. However, the program often generates a walk quite quickly and Figures 1 and 2 show typical outputs.

Figure 1: permalink

Figure 2: permalink

The difference between Figures 1 and 2 in this post compared to Figure 9 in my previous post is that the latter traverses every point in the grid and not just a random selection of them. Gemini will write a program to do this but as it explains:

Finding a Hamiltonian path is an NP-complete problem. This means that for larger grids, the time required to find such a path can grow extremely rapidly. The provided recursive backtracking algorithm will explore many possibilities. For a small grid (e.g., 3x3, 4x4, maybe 5x5), it might find a solution in a reasonable time.

Here is a Canvas link to the code. Figure 3 shows a typical output using a 4 x 4 grid.

Figure 3