[seqfan] Re: Quick question about self-avoiding walks

Jon Wild wild at music.mcgill.ca
Sat Dec 10 15:30:51 CET 2011

On Sat, 10 Dec 2011, Alonso Del Arte wrote:

> Does the OEIS have the sequence of the number of distinct self-avoiding
> walks possible on an n^2 lattice where every vertex is visited? Here is an
> example of what I'm talking about:
> http://oeis.org/wiki/File:Walks_on_8_by_8_SqLattice.png I would look it up
> myself but I don't know the proper word for it nor have I thought about how
> to calculate terms.

Look for Hamiltonian cycles on a square grid. They're only possible for 
squares of even side. Sequence A003763 is the main version and it 
references A120443, A140519 and A140521.

I looked for these once before and found the OEIS didn't have the version 
of the sequence reduced for symmetry i.e. where rotations and reflections 
are not counted as distinct. I have the first few terms if anyone wants to 
submit the sequence:

2x2: 1 rook's tour
4x4: 2 rook's tours
6x6: 149 rooks tours
8x8: 580717 rook's tours


More information about the SeqFan mailing list