This site is supported by donations to The OEIS Foundation.

# Self-avoiding walks

A self-avoiding walk (SAW) is a lattice path (sequence of moves between adjacent lattice nodes) that does not visit any lattice node more than once.

SAWs were first introduced by the chemist Paul Flory in order to model the real-life behavior of chain-like entities such as solvents and polymers, whose physical volume prohibits multiple occupation of the same spatial point. Very little is known rigorously about the self-avoiding walk from a mathematical perspective, although physicists have provided numerous conjectures that are believed to be true and are strongly supported by numerical simulations.

## Hamiltonian lattice walks

A Hamiltonian lattice walk is a Hamiltonian path on a lattice that visits each lattice node exactly once.

A Hamiltonian lattice cycle is a Hamiltonian cycle (or Hamiltonian circuit) on a lattice, i.e. a closed Hamiltonian lattice walk.

Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

## Lattice graphs vs grid graphs

Lattice graphs have their values located at the corners of grid cells. Lattice graph edges join the corners of grid cells.

Grid graphs have their values located at the centers of grid cells. Grid graph edges join the centers of grid cells.

An (m+1) X (n+1) square lattice constitutes the cell corners (coordinates (0,0) to (m,n)) of an m X n square grid.

## Self-avoiding walks on a 0-dimensional lattice

Trivial, the point lattice (a single node) has only the null walk (staying put on that single node).

## Self-avoiding walks on a 1-dimensional lattice

Trivial, a path lattice of length n has only one walk from nodes (0) to (n-1).

## Self-avoiding walks on a 2-dimensional lattice

### Self-avoiding walks on a 2-dimensional square lattice

#### Self-avoiding walks of length n on a 2-dimensional square lattice

Self-avoiding walks of length ${\displaystyle \scriptstyle n\,}$ on a 2-dimensional square lattice which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y.
${\displaystyle \scriptstyle n\,}$ Self-avoiding walks of length ${\displaystyle \scriptstyle n\,}$
1
 ⦁ ⎪ ⦁ ⎪ ⎪ ⦁ ⎪ ⦁
2

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁
3

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

A046170 Number of self-avoiding walks on a 2-D lattice of length ${\displaystyle \scriptstyle n,\,n\,\geq \,1,\,}$ which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y.

{1, 2, 5, 12, 30, 73, 183, 456, 1151, 2900, 7361, 18684, 47652, 121584, 311259, 797311, 2047384, 5260692, 13542718, 34884239, 89991344, 232282110, 600281932, 1552096361, 4017128206, 10401997092, 26957667445, 69892976538, ...}

#### Self-avoiding walks on an (m+1) X (n+1) square lattice starting from (0,0) and ending at (m,n)

The apex of the triangle (${\displaystyle \scriptstyle m\,=\,n\,=\,0\,}$) corresponds to the 0-dimensional lattice with only the null walk.

The first column (${\displaystyle \scriptstyle n\,=\,0\,}$) corresponds to 1-dimensional lattices (path lattice of length ${\displaystyle \scriptstyle m\,}$) with only one walk from nodes (0) to (m).

 ${\displaystyle \scriptstyle m\,}$ = 0 1 1 1 2 2 1 4 12 3 1 8 38 184 4 1 16 125 976 8512 5 1 32 414 5382 79384 1262816 6 1 64 ? ? ? ? 575780564 7 1 128 ? ? ? ? ? 789360053252 8 1 256 ? ? ? ? ? ? 3266598486981642 9 1 512 ? ? ? ? ? ? ? 41044208702632496804 10 1 1024 ? ? ? ? ? ? ? ? 1568758030464750013214100 ${\displaystyle \scriptstyle n\,}$ = 0 1 2 3 4 5 6 7 8 9 10

##### Self-avoiding walks on an (n+1) X (n+1) square lattice starting from (0,0) and ending at (n,n)
Self-avoiding walks on an (n+1) X (n+1) square lattice starting from (0,0) and ending at (n,n)
${\displaystyle \scriptstyle n\,}$ Self-avoiding walks starting from (0,0) and ending at (n,n)
1

 ⦁ ⎪ ⦁ ⎪ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⎪ ⦁ ⎪ ⦁
2

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

A007764 Number of self-avoiding walks from (0,0) to (n,n), n ≥ 0, of a (n+1) X (n+1) square lattice. Number of nonintersecting (or self-avoiding) rook paths joining opposite corner cells of an n X n grid. (should it be (n+1) X (n+1) grid, since rooks move from center to center of adjacent grid cells? — Daniel Forgues 06:06, 3 January 2012 (UTC))

{1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, ...}

#### Hamiltonian self-avoiding walks on a 2-dimensional square lattice

##### Example of a Hamiltonian self-avoiding walk on a 9 X 9 square lattice (corners of cells of an 8 X 8 square grid)

 ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁ ⎪ ⦁

##### Example of a Hamiltonian self-avoiding walk on a 15 X 15 square lattice (corners of cells of a 14 X 14 square grid)

Template:Self-avoiding walk

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)

(...)