This question caught my atention recently. Most (if not all) of the answers aproached the problem via a brute force attack. Surely there is a more elegant way to deal with this, given the inherent symmetry.

My question is can this be generalised to an $n$ dimensional lattice? Clearly the placement of the nearest neighbour is critical in this problem (ie, it is unclear where $n=5$ in $2$ dimensions would be places in terms of the classical Descatrian coordinate system), but it could also be generalised to $n$ in any dimension. Is this a Hamiltonian path (ie NP hard problem), or can the symmetry be utilised to present a more analytic solution?


If standard MSE policy of questions being self-contained is desired, please note, and I will alter.

  • $\begingroup$ What exactly do you mean by symmetry? $\endgroup$ – Matt Samuel Dec 2 '15 at 23:50
  • $\begingroup$ @MattSamuel Clearly one vertec needs to be consisered and mutliplied by 4. The same goes of the mid- sides, and the centre is the exception. The problem lies of course in the topological issue of not retracing your steps. $\endgroup$ – martin Dec 2 '15 at 23:52
  • $\begingroup$ Surely there is a more elegant way to deal with this, given the inherent symmetry. - Surely there is a God, given the inherent order present in the Universe. $\endgroup$ – Lucian Dec 3 '15 at 2:18
  • $\begingroup$ @Lucien oh, the irony ;) $\endgroup$ – martin Dec 3 '15 at 2:19

In general your "dots" form the vertices of a graph, and I think you're asking for the number of self-avoiding walks of a given length on this graph. There is a huge literature on self-avoiding walks. In general, counting self-avoiding walks is #P-complete, and thus very difficult: see e.g. this paper.

  • $\begingroup$ this is an interesting comment. I suppose the question of how to apply it will rely on my own research - made easier by the link you provided - many thanks :) $\endgroup$ – martin Dec 2 '15 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.