There are 2 self-avoiding (non-self-intersecting) paths from the southwest corner of a 1 × 1 grid to the northeast corner, using only steps north, east, south, or west):

(In only this case, it turns out to be the same as the number of shortest paths.)

12 self-avoiding paths through a 2 × 2 grid:

(Of these 12 paths: the first 6 take 4 steps; the next 4 paths take 6 steps; and the last 2 paths take 8 steps.)

184 paths through a 3 × 3 grid:

(Of these 184 paths: 20 of them take 6 steps; 36 take 8 steps; 48 take 10 steps; 48 take 12 steps; and 32 take 14 steps.)

This 2-D case is sequence A007764 in The On-Line Encyclopedia of Integer Sequences.

While we’re on the subject, there seem to be 18 self-avoiding paths through a 1 × 1 × 1 lattice:

(Of these 18 paths: 6 of them take 3 steps; 6 paths take 5 steps; and 6 paths take 7 steps.)

156 paths through a 2 × 1 × 1 lattice:

There are 5,698 paths through a 2 × 2 × 1 lattice; here are some of the 30 shortest and 314 longest:

Copyright © 1998–2018 by Robert Dickau.

[ home ] || [ 2011-02-06 ]

www.robertdickau.com/allpaths.html