Math Is Fun Forum

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,996

Website

Self Avoiding Walk

There is a 10*10 chessboard with all white squares

I want an algorithm to enumerate all possible ways to color them with black such that there is a path from every black square to every black square through edge connection.

There must be atleast one black square to fulfill this criterion.

Is a good example. (Forget the red tile)

Last edited by Agnishom (2014-10-07 00:43:42)

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

neizan

Member

Registered: 2014-10-20

Posts: 1

Re: Self Avoiding Walk

I think you're interested in calculating the number of lattice animals or polyominoes that can fit inside a square section of the square lattice, see http://en.wikipedia.org/wiki/Polyomino

The best way to count these is via transfer matrix methods, and the longest enumerations have been done by Iwan Jensen: http://www.ms.unimelb.edu.au/~iwan/animals/Animals_ser.html (He may well have even longer series that he just hasn't got around to posting on the web.)

There's also a paper on the topic here: http://arxiv.org/abs/cond-mat/0007238 , and the oeis page is: https://oeis.org/A001168

Unfortunately, these counts are for the total number of polyominoes with n squares, and so don't directly answer your question. However, the number of polyominoes inside a square is an intermediate step in the above transfer matrix calculation.

If you let me know what you need these counts for perhaps I can be of more help. Implementing a transfer matrix calculation takes a bit of time and effort, but for what it's worth the enumeration of polyominoes is on the easier end of the spectrum of problems that are studied this way.

Edit: this is a much better paper to read on the enumeration method: http://arxiv.org/abs/cond-mat/0007239

Last edited by neizan (2014-10-20 11:33:30)

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,996

Website

Re: Self Avoiding Walk

Thank You. Will look into that

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Matir

Member

Registered: 2016-10-08

Posts: 22

Re: Self Avoiding Walk

Does rotations/reflections count?