approximation of possible self-avoiding walks
 

I've been recently about [url=http://mathworld.wolfram.com/Self-AvoidingWalk.html]self-avoiding walks[/url] recently, and I've noticed that the number of possible paths increases rapidly as the size of the lattice increases. However, it also seems very hard to calculate the exact number of possible paths.

Does anyone know any formulas for [b]approximating[/b] the number of self-avoiding walks in an arbitrary lattice? For example, how many possible paths should I expect for a three-dimensional 20 x 20 x 20 lattice, or a five-dimensional 4 x 4 x 4 x 4 x 4 lattice?

I guess we should try some original research. I'm assuming that you mean I need to set a bit everytime I enter a square/cube/whatever, and then randomly chose a nonconflicting path until I am surrounded. You can represent this as an array of bits, and run a large amount of trial runs. Unfortunately, this is a 'hard' problem... It is likely in other words intractable. You'de be trying to create a function that approximates the statistical result.

There is also a subtle relationship between what you're describing and (at least):
Nonrepeating n-digit sequences like 000100111 where if you look at any three digits in a row, you'll only see that combination once. These are called "De Bruijn" sequences. There are inperfect sequences that are longer then 9 bits that will repeat some 2-bit combinations and others that don't contain all 2-bit combinations. These could be considered an analogy of uncrossed and multicrossed 'squares' in the first paragraph. If you write a program to evaluate one, you should be able to use that strategy to attack the other.
Euler circuits
Hamiltonian paths
"Snake-in-the-Box" problems are like the first paragraph but deal with the edges connecting the corners of a box.

You'll notice that most of them are linking to each other on Wikipedia. The common theme is paths - rather it's a geometric or digital path. Reading about these subjects should be quite interesting or absolutely mind numbing. :devil:

[url]http://en.wikipedia.org/wiki/De_Bruijn_sequence[/url]
[url]http://en.wikipedia.org/wiki/Eulerian_path[/url]
[url]http://en.wikipedia.org/wiki/Hamiltonian_path[/url]
Especially read: [url]http://en.wikipedia.org/wiki/Snake-in-the-box[/url]
Running those names through any search engine should be enlightning.