Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2014-10-07 00:39:41

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,722
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.

3DwC4aa.jpg

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.

Offline

#2 2014-10-20 11:28:43

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)

Offline

#3 2014-10-20 12:51:26

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,722
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.

Offline

#4 2016-10-08 22:48:52

Matir
Member
Registered: 2016-10-08
Posts: 22

Re: Self Avoiding Walk

Does rotations/reflections count?

Offline

Board footer

Powered by FluxBB