Figure 5: Self-avoiding walks on the lattice

Relaxing the requirement that a path be among the shortest possible leads to a dramatic increase in the number of paths. Here the 12 diagonal paths across a 2-by-2 lattice are shown; for the 3-by-3 lattice the number jumps to 184. The only constraint on these paths is that they may not pass through any vertex more than once. (If this last constraint were removed, what would happen to the number of paths?)