| Polya's coloring theorem (which was devised for counting organic
chemical compounds) *may* be able to help, but I'm only guessing
and have not thought about it. At the least, it will reduce the
work by taking account of symmetries, and usually you find in
the analysis that one term dominates so you can get an asymptotic
estimate. There may be some kind of generating function way to
attack it also...
- Jim
|
|
Thanks very much for your replies.
>I think this will prove to be a very tough problem.
and
> I agree with Lynn -- its likely to be very tough.
Yes, I thought it was very difficult too.
>Does this situation
>
> +---+---+---+
> | | | |
> +---+---+---+
> | | X | |
> +---+---+---+
> | | | |
> +---+---+---+
>
>Where square X is surrounded by other squares in a solution set, count as
>one solution (with X) or two (with and without X)? It makes a big
>difference.
I would count them as two solutions.
> The difficulty is
> that attempts to enumerate configurations are likely to overcount
> because of symetries of some, but not other configurations.
I was not differentiating between symetrical solutions.
Hence in evaluating, say, F(4,3) (number of ways of selecting three connected
unit squares from a 4*4 grid) both of the following would contribute:
+---+---+---+---+
| X | X | | |
+---+---+---+---+
| | X | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
and
+---+---+---+---+
| | | | |
+---+---+---+---+
| | | | |
+---+---+---+---+
| | X | | |
+---+---+---+---+
| X | X | | |
+---+---+---+---+
Even discounting symetries it still seems tough.
> Polya's coloring theorem (which was devised for counting organic
> chemical compounds) *may* be able to help, but I'm only guessing
> and have not thought about it. At the least, it will reduce the
> work by taking account of symmetries, and usually you find in
> the analysis that one term dominates so you can get an asymptotic
> estimate.
I have had a looked at assigning a "checkerboard" colour scheme to the
grid, (with same colours running diagonally) to the grid. If c is number
of colors used, this provides a usefull categorisation of solutions
with c selected
2 <= c <= m
and c <= N
Solutions then get a categorisation depending on their parity with respect
to of each of the colors they use. (A related technique has been used to
identify "impossible" situations/prune search trees in polyomino fitting
problems which have some similarity). Is this at all the same? Where would I
find information on Polya's colouring theorem?
> There may be some kind of generating function way to
> attack it also...
Problem does seem to have this sort of a feel to it. For example
solutions involving selecting say 5 unit squares in a sense are built upon
solutions involving 4 unit squares, etc. etc. (Just extend on earlier solution
by adding one square to each edge of previous solution). However the rules
for uniqueness, and the constraints of the edge of the grid make it very
difficult. But perhaps there is some pattern like Pascal's triangle or the
Bell numbers waiting to be found.
Another approach I have used is to develope various forms of recursive
lists to describe the "connectivity" of unit squares on the grid, and then
to search the lists or map the lists against certain patterns corresponding
to solutions. I suppose this no more than a re-formulation of the problem but
I was hoping some pattern or algorithm might appear that it is more difficult
to see in the actual problem.
---------------------------------------------------------------------------
The problem is interesting to program or otherwise solve.
Would any one care to calculate F(5,5), F(6,6), F(7,7) and F(8,8)?
Richard.
|
|
A closely related problem is:
Count the number of ways m colored squares can be connected in the
plane lattice.
For many m, this is equivalent to your question, but your question constrains
the larger m to "fit" in the square.
Perhaps this second question is a bit easier since we're only dealing with m
and not N. But perhaps it's still "too hard".
/Eric
|